Uniform generation of forests of restricted height (Q1330666)

Tree structures occur throughout the theory of information storage. Typically each tree node contains some data information and some pointers to other tree nodes. In most cases the number \(k\) of pointer fields is fixed and the structure is referred to as a \(k\)-way tree. More formally, a \(k\)-way tree can be defined as being either empty (having no nodes) or as consisting of a root node together with an ordered sequence of \(k\) \(k\)-way trees. For developing and testing algorithms which manipulate forests it is useful to have methods for generating them in a uniform manner (so that each forest is generated with the same probability). Many methods have been given in the case of binary trees (2-way trees with one component). Some of these methods extend to \(k\)-way trees but there has been little previous work on uniformly generating trees of a fixed or bounded height. This paper considers \(k\)-way forests of fixed size \(n\), height \(h\), and number of components \(c\). A generator is given for producing such forests uniformly at random thereby answering an open problem posed by Lee, Lee, and Wong. Each random forest is generated in a linear number of operations in its size. The algorithm computes a table of values in a pre-processing phase. This table occupies \(O(hn^ 2)\) locations and takes \(O(hn^ 3)\) time to produce.