The level of nodes in heap ordered trees
Abstract.
A heap ordered tree with n nodes ("size n")
is a planted plane tree
together with a bijection from the nodes to the set {1,...,n}
which is monotonically increasing
when going from the root to the leaves.
We consider the level of the node j in a (random)
heap ordered tree of size n \ge j.
This distribution does not
depend on n. Precise expressions are derived for the expectation, the variance, and the
probability distribution.
Related papers:
Path length, etc.
Descendants
helmut@gauss.cam.wits.ac.za,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)