On generating all binary trees

被引：0

作者：

Skarbek, Wladyslaw ^{[1
]}

机构：

[1] Warsaw Univ Technol, Fac Elect & Informat Technol, PL-02665 Warsaw, Poland

来源：

FUNDAMENTA INFORMATICAE | 2007年 / 75卷 / 1-4期

关键词：

Pawlak's machine; binary tree; ordered tree; generating trees;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In context of Pawlak's machine a general iterative meta scheme for generating of combinatorial objects is introduced and applied to proof the correctness of ASR (Arm Switching and Rotation) algorithm generating all binary trees on k nodes. The average time complexity of the ASR algorithm and B* are analyzed and compared to the B algorithm discussed by Knuth. The analyzed algorithms are all obtained by various natural correspondences from author's DCP (Degrade and Compress Path) algorithm for generating all ordered trees on k + 1 nodes.

引用

页码：505 / 536

页数：32