Weakly protected nodes in random binary search trees

DOI10.1051/ITA/2022002MaRDI QIDQ5037204zbMATH OpenOpenAlexFDO

Authors Ezzat Mohammad Nezhad, Mehri Javanian, Ramin Imany Nabiyyi

Publication date 28 February 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

contraction methodlimiting distributionrandom binary search treeweakly protected nodesZolotarev metric

Mathematics Subject Classification ID

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

Recommendations

• Asymptotic distribution of two-protected nodes in random binary search trees
• Protected nodes and fringe subtrees in some random trees
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• Limiting theorems for the nodes in binary search trees
• On the subtrees of random binary search trees

Cites work

• k-protected vertices in binary search trees
• A limit theorem for “quicksort”
• Asymptotic distribution of two-protected nodes in random binary search trees
• Asymptotic distribution of two-protected nodes in ternary search trees
• scientific article; zbMATH DE number 49698 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Protected nodes and fringe subtrees in some random trees
• Refined quicksort asymptotics
• Weakly protected points in ordered trees

Cited in

(8)

• On weighted depths in random binary search trees
• Weakly protected points in ordered trees
• Limiting theorems for the nodes in binary search trees
• Asymptotic distribution of two-protected nodes in ternary search trees
• k-protected vertices in binary search trees
• scientific article; zbMATH DE number 1552323 (Why is no real title available?)
• Asymptotic distribution of two-protected nodes in random binary search trees
• Protected nodes and fringe subtrees in some random trees

This page was built for publication: Weakly 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 Q5037204)