Weakly Protected Nodes in Random Binary Search Trees
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 2

Here, we derive the exact mean and variance of the number of weakly protected nodes (the nodes that are not leaves and at least one of their children is not a leaf) in binary search trees grown from random permutations. Furthermore, by using contraction method, we prove normal limit law for a properly normalized version of this tree parameter.

DOI : 10.1051/ita/2022002
Classification : 05C05, 05C80, 60F05
Keywords: Random binary search tree, Weakly protected nodes, Zolotarev metric, Contraction method, limiting distribution 
@article{ITA_2022__56_1_A2_0,
     author = {Mohammad Nezhad, Ezzat and Javanian, Mehri and Imany Nabiyyi, Ramin},
     title = {Weakly {Protected} {Nodes} in {Random} {Binary} {Search} {Trees}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022002},
     mrnumber = {4376268},
     zbl = {1483.05022},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022002/}
}
TY  - JOUR
AU  - Mohammad Nezhad, Ezzat
AU  - Javanian, Mehri
AU  - Imany Nabiyyi, Ramin
TI  - Weakly Protected Nodes in Random Binary Search Trees
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022002/
DO  - 10.1051/ita/2022002
LA  - en
ID  - ITA_2022__56_1_A2_0
ER  - 
%0 Journal Article
%A Mohammad Nezhad, Ezzat
%A Javanian, Mehri
%A Imany Nabiyyi, Ramin
%T Weakly Protected Nodes in Random Binary Search Trees
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022002/
%R 10.1051/ita/2022002
%G en
%F ITA_2022__56_1_A2_0
Mohammad Nezhad, Ezzat; Javanian, Mehri; Imany Nabiyyi, Ramin. Weakly Protected Nodes in Random Binary Search Trees. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 2. doi: 10.1051/ita/2022002

[1] M. Bona, k-protected nodes in binary search trees. Adv. Appl. Math. 53 (2014) 1–11. | MR | Zbl | DOI

[2] L. Devroye and S. Janson, Protected nodes and fringe subtrees in some random trees. Electr. Commun. Probab. 19 (2014) 1–10. | MR | Zbl

[3] C. Holmgren and S. Janson, Asymptotic distribution of two-protected nodes in ternary search trees. Electr. J. Probab. 20 (2015) 1–20. | MR | Zbl

[4] C. Holmgren and S. Janson, Limit laws for functions of fringe trees for binary search trees and recursive trees. Electr. J. Probab. 20 (2015) 1–51. | MR | Zbl

[5] H. M. Mahmoud, Evolution of random search trees. John Wiley & Sons Inc., New York (1992). | MR | Zbl

[6] H. M. Mahmoud and M. D. Ward, Asymptotic distribution of two-protected nodes in random binary search trees. Appl. Math. Lett. 25 (2012) 2218–2222. | MR | Zbl | DOI

[7] R. Neininger, Refined quicksort asymptotics. Random Struct. Algor. 46 (2015) 346–361. | MR | Zbl | DOI

[8] S. Rachev, Probability Metrics and the Stability of Stochastic Models. New York (1991). | MR | Zbl

[9] U. Roesler, A limit theorem for “Quicksort”. RAIRO: ITA 25 (1991) 85–100. | MR | Zbl | Numdam

[10] L. Yang and S. L. Yang, Weakly protected points in ordered trees. Graphs Combinat. (2021) . | DOI | MR | Zbl

Cité par Sources :