@article{EJP1723,
author = {Cecilia Holmgren},
title = {Novel characteristics of split trees by use of renewal theory},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {17},
year = {2012},
keywords = {Random Trees, Split Trees, Renewal Theory},
abstract = {We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e.g., binary search trees, $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees. More precisely: We use 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 data) to a subset of nodes of an infinite tree. One of our main results is a relation between the deterministic number of balls n and the random number of nodes N. In Devroye [SIAM J Comput 28, 409-432, 1998] there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth $\ln n/\mu+O(\ln n)^{1/2})$, 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 nodes with depths $\geq \mu^{-1}\ln n-(\ln n)^{1/2+\epsilon}$ or depths $\leq\mu^{-1}\ln n+(\ln n)^{1/2+\epsilon}$ for any choice of $\epsilon>0$. We also find the first asymptotic of the variances of the depths of the balls in the tree.},
pages = {no. 5, 1-27},
issn = {1083-6489},
doi = {10.1214/EJP.v17-1723},
url = {http://ejp.ejpecp.org/article/view/1723}}