A rawa tree is a binary search tree for an ordinary random walk 0,S1 ,S2,S3,..., where Sn=\sumi=1n Xi and the Xi 's are i.i.d. distributed as X. We study the height Hn of the rawa tree, and show that if X is absolutely continuous with bounded symmetric density, if X has finite variance, and if the density of X is bounded away from zero near the origin, then Hn / \sqrt{2n} tends to the Erdõs-Kac-Rényi distribution.
Keywords and phrases. Random binary search tree, probabilistic analysis, random walk, Catalan constant, limit distributions.
CR Categories: 3.74, 5.25, 5.5.
Back to the publications