uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
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
Random Records and Cuttings in Binary Search Trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2010 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 19, no 3, p. 391-424Article in journal (Refereed) Published
Abstract [en]

We study the number of random records in a  binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

Place, publisher, year, edition, pages
2010. Vol. 19, no 3, p. 391-424
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-112233DOI: 10.1017/S096354830999068XISI: 000277473600004OAI: oai:DiVA.org:uu-112233DiVA, id: diva2:285445
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 first 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 infinitely divisible distributions. It was shown that with modifications, 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 infinity. 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., finite), 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
National Category
Mathematics
Research subject
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)
Opponent
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

Other links

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
Combinatorics, probability & computing
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 494 hits
CiteExportLink to record
Permanent link

Direct link
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