Novel Characteristics of Split Trees by use of Renewal Theory

Abstract

We investigate characteristics of random split trees introduced by Devroye; split trees include for example binary search trees, $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees. More precisely: We introduce the use of renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality $n$ is constructed by distributing $n$ "balls" (which often represent "key numbers") in a subset of vertices of an infinite tree. One of our main results is to give a relation between the deterministic number of balls $n$ and the random number of vertices $N$. Devroye has found a central limit law for the depth of the last inserted ball so that most vertices are close to $\frac{\ln n}{\mu }+\mathcal{O}\left(\sqrt{\ln n}\right)$, where $\mu$ is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of vertices with depths $\ge \frac{\ln n}{\mu }+{\ln }^{0.5+\epsilon }n$ or depths $\le \frac{\ln n}{\mu }+{\ln }^{0.5+\epsilon }n$ for any choice of $\epsilon >0$. We also find the first asymptotic of the variances of the depths of the balls in the tree.

49 pages, 2 figures

References in corpus (1)

• A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees

Cited by in corpus (2)

• A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees
• On the asymptotic internal path length and the asymptotic Wiener index of random split trees