Novel Characteristics of Split Trees by use of Renewal Theory
2012 (English)In: Electronic Journal of Probability, ISSN 1083-6489, Vol. 17, 5- p.Article in journal (Refereed) Published
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  there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth lnn/mu + O(root lnn), 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 >= lnn/mu - ln(1/2+epsilon) n or depths <= lnn/mu + ln(1/2+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.
Place, publisher, year, edition, pages
2012. Vol. 17, 5- p.
Random Trees, Split Trees, Renewal Theory
Research subject Mathematics
IdentifiersURN: urn:nbn:se:uu:diva-112234DOI: 10.1214/EJP.v17-1723ISI: 000301061600001OAI: oai:DiVA.org:uu-112234DiVA: diva2:285449