Mathematics – Probability
Scientific paper
2010-05-25
Mathematics
Probability
49 pages, 2 figures
Scientific paper
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}\Big(\sqrt{\ln n}\Big)$, 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 $\geq\frac{\ln n}{\mu}+\ln^{0.5+\epsilon} n$ or depths $\leq\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.
No associations
LandOfFree
Novel Characteristics of Split Trees by use of Renewal Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Novel Characteristics of Split Trees by use of Renewal Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Novel Characteristics of Split Trees by use of Renewal Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-298439