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

DOI10.1016/J.AML.2012.06.005zbMATH Open1251.05033OpenAlexW2016653708MaRDI QIDQ714563FDOQ714563

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

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

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)

Cites Work

• Title not available (Why is that?)
• The central limit theorem for dependent random variables
• Polya Urn Models
• Limit laws for local counters in random binary search trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Protected points in ordered trees
• The Expected Distribution of Degrees in Random Binary Search Trees
• 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

Cited In (17)

• \(k\)-protected vertices in binary search trees
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• On 2-protected nodes in random digital trees
• On the peel number and the leaf-height of Galton–Watson trees
• Distribution of distances in random binary search trees.
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment 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
• Central limit theorems for additive functionals and fringe trees in tries
• Limiting theorems for the nodes in binary search trees
• Spanning tree size in random binary search trees.
• The distribution of the maximum protection number in simply generated trees
• Protection numbers in simply generated trees and Pólya trees
• Mean and variance of balanced Pólya urns
• Weakly protected nodes in random binary search trees
• Title not available (Why is that?)
• DEGREE PROFILE OF m-ARY SEARCH TREES: A VEHICLE FOR DATA STRUCTURE COMPRESSION

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)