Generating binary trees of bounded height (Q1064071)

From MaRDI portal
Revision as of 00:08, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
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
    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

    Identifiers