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

DOI10.1016/J.AML.2012.06.005MaRDI QIDQ714563zbMATH OpenOpenAlexFDO

Authors 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

asymptotic analysisrandom structurecombinatorial probabilitybinary search trees

Mathematics Subject Classification ID

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

Recommendations

• Weakly protected nodes in random binary search trees
• On the subtrees of random binary search trees
• Distribution of distances in random binary search trees.
• Asymptotic distribution of two-protected nodes in ternary search trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees

Cites work

• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1540682 (Why is no real title available?)
• Limit laws for local counters in random binary search trees
• Normal convergence problem? Two moments and a recurrence may be the clues
• Notes on protected nodes in digital search trees
• Polya Urn Models
• Protected points in \(k\)-ary trees
• Protected points in ordered trees
• The Expected Distribution of Degrees in Random Binary Search Trees
• The central limit theorem for dependent random variables

Cited in

(20)

• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• On the peel number and the leaf-height of Galton–Watson trees
• Distribution of distances in random binary search trees.
• Maximal clades in random binary search trees
• \(k\)-protected vertices in binary search trees
• Asymptotic properties of protected nodes in random recursive trees
• Limiting theorems for the nodes in binary search trees
• Degree profile of \(m\)-ary search trees: a vehicle for data structure compression
• 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
• Asymptotic distribution of two-protected nodes in ternary search trees
• Spanning tree size in random binary search trees.
• scientific article; zbMATH DE number 2127734 (Why is no real title available?)
• Protection numbers in simply generated trees and Pólya trees
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• The distribution of the maximum protection number in simply generated trees
• Weakly protected nodes in random binary search trees
• Mean and variance of balanced Pólya urns
• Limiting probabilities for vertices of a given rank in 1-2 trees
• On 2-protected nodes in random digital trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714563)