On Generating All Binary Trees

• Autorzy: Skarbek W.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 505--536
• Opis fizyczny: bibliogr. 9 poz. rys.

Twórcy

autor

Skarbek W.

• Faculty of Electronics and Information Technology, Warsaw University of Technology, Nowowiejska 16/19, Warsaw, Poland,

Bibliografia

• [1] Knuth, D. E.: The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd edition, Addison-Wesley, 1997.
• [2] Knuth, D. E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1997.
• [3] Knuth, D. E.: The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998.
• [4] Knuth, D. E.: The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees; History of Combinationatorial Generation, Addison-Wesley, 2006.
• [5] Korsh, J. E.: Generating T-ary Trees in Linked Representation, The Computer Journal, 48(4), 2005, 488-497.
• [6] Korsh, J. E.: Skarbek's Algorithm for t-Ary Trees, The Computer Journal, 49(3), 2006, 351-357.
• [7] Pawlak, Z.: Theory of Digital Computers, Mathematical Machines, 10, 1969, 4-31.
• [8] Pawlak, Z.: A Mathematical Model of Digital Computer, Proc. of the Conference on Automata and Formal Languages, Bonn, 1973, 24-37.
• [9] Skarbek, W. K.: Generating Ordered Trees, Theoretical Computer Science, 57, 1988, 153-159.