Note on the heights of random recursive trees and random m-ary search trees |
| |
Authors: | Boris Pittel |
| |
Abstract: | A process of growing a random recursive tree Tn is studied. The sequence {Tn} 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 Tn 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 γe1+γ = 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. |
| |
Keywords: | |
|
|