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

DOI10.1016/j.aml.2012.06.005zbMath1251.05033OpenAlexW2016653708MaRDI 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 structureasymptotic analysisbinary search treescombinatorial probability

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

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

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

This page was built for publication: Asymptotic distribution of two-protected nodes in random binary search trees