<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
The Height of Increasing Trees
Michael Drmota
Institut f\"ur Diskrete Mathematik und Geometrie, TU Wien, Wiedner Hauptstrasse 8-10/118,\break A-1040 Wien, Austria
Annals of Combinatorics 12 (4) pp.369-398 December, 2008
AMS Subject Classification: 05C05, 05A16
Increasing trees have been introduced by Bergeron, Flajolet, and Salvy \cite{BFS}. This kind of notion covers several well-know classes of random trees like binary search trees, recursive trees, and plane oriented (or heap ordered) trees. We consider the height of increasing trees and prove for several classes of trees (including the above mentioned ones) that the height satisfies $\E H_n \sim \gamma \log n$ (for some constant $\gamma>0$) and ${\bf Var}\, H_n = O(1)$ as $n\to\infty$. The methods used are based on generating functions.
Keywords: recursive trees, height, average case analysis


1. F. Bergeron, P. Flajolet, and B. Salvy, Varieties of increasing trees, In: Lecture Notes in Comput. Sci. Vol. 581, Springer, Berlin, (1992) pp. 24–-48.

2. B. Chauvin and M. Drmota, The random multisection problem, travelling waves and the distribution of the height of m-ary search trees, Algorithmica 46 (3-4) (2006) 299–-327.

3. L. Devroye, A note on the height of binary search trees, J. Assoc. Comput. Mach. 33 (3) (1986) 489–-498.

4. L. Devroye, Branching processes in the analysis of the height of trees, Acta Inform. 24 (3) (1987) 277–-298.

5. L. Devroye and B. Reed, On the variance of the height of random binary search trees, SIAM J. Comput. 24 (6) (1995) 1157–-1162.

6. N. Broutin, L. Devroye, E. McLeish, and M. de la Salle, The height of increasing trees, Random Structures Algorithms 32 (4) (2008) 494-–518.

7. M. Drmota, The saturation level in binary search trees, In: Mathematics and Computer Science, Birkh¨user, Basel, (2000) pp. 41-–51.

8. M. Drmota, An analytic approach to the height of binary search trees, Algorithmica 29 (1-2) (2001) 89–-119.

9. M. Drmota, An analytic approach to the height of binary search trees, II, J. ACM 50 (3) (2003) 333–-374.

10. M. Drmota, Concentration properties of extremal parameters in random discrete structures, In: Proceedings of the 4th Colloquium on Mathematics and Computer Science, DMTCS Proc., Nancy, France, (2006) pp. 1–-30.

11. Z. Katona, Width of a scale-free tree, J. Appl. Probab. 42 (3) (2005) 839-–850.

12. T. Mori, The maximum degree of the Barab´asi-Albert random tree, Combin. Probab. Comput. 14 (3) (2005) 339–-348.

13. A. Panholzer and H. Prodinger, Level of nodes in increasing trees revisited, Random Structures Algorithms 31 (2) (2007) 203–-226.

14. B. Pittel, Note on the height of recursive trees and m-ary search trees, Random Structures Algorithms 5 (2) (1994) 337–-348.

15. B. Reed, The height of a random binary search tree, J. ACM 50 (3) (2003) 306-–332.

16. R.T. Smythe and H.M. Mahmoud, A survey of recursive trees, Theory Probab. Math. Statist. 51 (1995) 1-–27.