uu.seUppsala University Publications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Novel Characteristics of Split Trees by use of Renewal Theory
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2012 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 17, p. 5-Article in journal (Refereed) Published
##### Abstract [en]

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 [5] 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, p. 5-
##### Keyword [en]
Random Trees, Split Trees, Renewal Theory
##### National Category
Discrete Mathematics
Mathematics
##### Identifiers
ISI: 000301061600001OAI: oai:DiVA.org:uu-112234DiVA, id: diva2:285449
Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2017-12-12Bibliographically approved
##### In thesis
1. Split Trees, Cuttings and Explosions
Open this publication in new window or tab >>Split Trees, Cuttings and Explosions
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”.

In the ﬁrst paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to inﬁnitely divisible distributions. It was shown that with modiﬁcations, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees.

In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to inﬁnity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees.

In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution.

In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., ﬁnite), there is the same type of expression for the number of vertices as for normal split trees.

##### Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, 2010. p. 52
##### Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 67
##### Keyword
Random Graphs, Random Trees, Split Trees, Renewal Theory, Binary Search Trees, Cuttings, Records, Tree Algorithms, Markov Chains, Galton-Watson Processes
Mathematics
Mathematics
##### Identifiers
urn:nbn:se:uu:diva-112239 (URN)978-91-506-2124-2 (ISBN)
##### Public defence
2010-02-19, Polhemssalen, Ångströmslaboratoriet, Lägerhyddsv. 1, Uppsala, 13:15 (English)
##### Supervisors
Available from: 2010-01-29 Created: 2010-01-12 Last updated: 2010-01-29Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

Publisher's full text

#### Authority records BETA

Holmgren, Cecilia

#### Search in DiVA

##### By author/editor
Holmgren, Cecilia
##### By organisation
Analysis and Applied Mathematics
##### In the same journal
Electronic Journal of Probability
##### On the subject
Discrete Mathematics

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 507 hits

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf