Premium
Note on the heights of random recursive trees and random m ‐ary search trees
Author(s) -
Pittel Boris
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050207
Subject(s) - mathematics , tree (set theory) , combinatorics , random tree , connection (principal bundle) , sequence (biology) , random binary tree , discrete mathematics , branching (polymer chemistry) , branching process , limit (mathematics) , binary tree , computer science , geometry , mathematical analysis , motion planning , artificial intelligence , biology , robot , composite material , genetics , materials science
A process of growing a random recursive tree T n is studied. The sequence { T n } is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T n is asymptotic, with probability one, to c log n . In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ) −1 , where γ e 1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m ‐ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union‐find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.