wcn@cs.brown.edu (Wen-Chun Ni) (11/27/90)
I am interested in the following problem:
In the paper by Meir and Moon ("On the Altitude of Nodes in Random Trees,"
Canadian J. Math, XXX, 5, 1978, p997-1015), there is a tree closely
related to heap-ordered trees: the "recursive tree.(p 1012)" The
average altitude (or level) of such kind of tree was solved. What I
am interested is the average height (or maximum level) of recursive
trees. To my best knowledge, Flajolet and Odlyzko solved the similar
problems for Binary Trees and other kinds of Simple Families of Trees.
The height of Binary Search Trees was solved in Devroye's 1986 paper
(JACM) using probabilistic methods. Because recursive trees are not
in the simply generated family, I doubt it has not yet been solved
though the average height can be O(log n) with height probability.
Remark:
1) There is an isomorphism between the set of (n+1)-node recursive
trees and the set of n-permutations. For example,
If n=2, the set of 3-node recursive trees should be
1 and 1
| / \
2 2 3
|
3
2) The enumeration of recursive tree is easy: solve y'=exp(y).
But if we use this differential equation to solve the height
problem, I think it's difficult to solve a recurrence relation
like y_n' = exp(y_{n-1}) (in TeX form).
If anybody knows the related references or the source of solution,
please email to "wcn@cs.brown.edu." Thank you very much.
Wen-Chun Ni, Department of Computer Science, Brown University.