Asymptotic distribution of two-protected nodes in ternary search trees
2015 (English)In: Electronic Journal of Probability, ISSN 1083-6489, Vol. 20, 9Article in journal (Refereed) Published
We study protected nodes in m-ary search trees, by putting them in context of generalised Pólya urns. We show that the number of two-protected nodes (the nodes that are neither leaves nor parents of leaves) in a random ternary search tree is asymptotically normal. The methods apply in principle to m-ary search trees with larger m as well, although the size of the matrices used in the calculations grow rapidly with m; we conjecture that the method yields an asymptotically normal distribution for all m≤26. The one-protected nodes, and their complement, i.e., the leaves, are easier to analyze. By using a simpler Pólya urn (that is similar to the one that has earlier been used to study the total number of nodes in m-ary search trees), we prove normal limit laws for the number of one-protected nodes and the number of leaves for all m≤26.
Place, publisher, year, edition, pages
2015. Vol. 20, 9
Random trees; Polya urns; Normal limit laws; M-ary search trees
IdentifiersURN: urn:nbn:se:su:diva-114313DOI: 10.1214/EJP.v20-3577ISI: 000350287500001OAI: oai:DiVA.org:su-114313DiVA: diva2:791153