On generating all binary trees
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.
binary tree pawlak's machine ordered tree generating trees