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.

This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)