Weakly protected nodes in random binary search trees

DOI10.1051/ita/2022002zbMath1483.05022OpenAlexW4210895409MaRDI QIDQ5037204

Ezzat Mohammad Nezhad, Ramin Imany Nabiyyi, Mehri Javanian

Publication date: 28 February 2022

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2022002

zbMATH Keywords

limiting distributioncontraction methodrandom binary search treeZolotarev metricweakly protected nodes

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-protected vertices in binary search trees
• Asymptotic distribution of two-protected nodes in random binary search trees
• Protected nodes and fringe subtrees in some random trees
• Weakly protected points in ordered trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Asymptotic distribution of two-protected nodes in ternary search trees
• Refined quicksort asymptotics
• A limit theorem for “quicksort”

This page was built for publication: Weakly protected nodes in random binary search trees