Answers are grounded in this paper and cite their sources.
The depth of insertion and the internal path length of recursive trees are studied. Luc Devroye has recently shown that the depth of insertion in recursive trees is asymptotically normal. We give a direct alternative elementary proof of this fact. Furthermore, via the theory of martingales, we show that I n , the internal path length of a recursive tree of order n , converges to a limiting distribution. In fact, we show that there exists a random variable I such that ( I n – n I n n )/ n → I almost surely and in quadratic mean, as n → α. The method admits, in passing, the calculation of the first two moments of I n .
No takes yet. Share an insight, caveat, or question.
Hosam M. Mahmoud (1991) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: