Generating binary trees of bounded height (Q1064071): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 00:08, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generating binary trees of bounded height |
scientific article |
Statements
Generating binary trees of bounded height (English)
0 references
1986
0 references
We present a new encoding scheme for binary trees with n internal nodes whose heights are bounded by a given value h, \(h\geq \lceil \log_ 2(n+1)\rceil\). The scheme encodes the internal nodes of the tree level by level and enables us to develop an algorithm for generating all binary trees within this class in a certain predetermined order. Specifically, the trees are generated in decreasing height and for trees of the same height they are generated in lexicographically increasing order. The algorithm can be easily generalized to encompass t-ary trees with bounded height. It is then shown that the average generation time per tree is constant (independent of n and h).
0 references
encoding scheme for binary trees
0 references
internal nodes
0 references
algorithm
0 references