Asymptotic distribution of two-protected nodes in random binary search trees

DOI10.1016/j.aml.2012.06.005zbMath1251.05033MaRDI QIDQ714563

Hosam M. Mahmoud, Mark Daniel Ward

Publication date: 11 October 2012

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aml.2012.06.005

zbMATH Keywords

random structure; asymptotic analysis; binary search trees; combinatorial probability

Mathematics Subject Classification ID

05C05: Trees

68P10: Searching and sorting

68R10: Graph theory (including graph drawing) in computer science

Related Items

Mean and variance of balanced Pólya urns, Weakly protected nodes in random binary search trees, On a random search tree: asymptotic enumeration of vertices by distance from leaves, DEGREE PROFILE OF m-ARY SEARCH TREES: A VEHICLE FOR DATA STRUCTURE COMPRESSION, On 2-protected nodes in random digital trees, \(k\)-protected vertices in binary search trees, Central limit theorems for additive functionals and fringe trees in tries, Limiting probabilities for vertices of a given rank in 1-2 trees, Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Notes on protected nodes in digital search trees
• Protected points in \(k\)-ary trees
• Normal convergence problem? Two moments and a recurrence may be the clues
• Protected points in ordered trees
• The central limit theorem for dependent random variables
• Limit laws for local counters in random binary search trees
• Polya Urn Models
• The Expected Distribution of Degrees in Random Binary Search Trees