Path length of protected nodes in random binary search trees
نویسندگان
1 Department of Statistics, Faculty of Science, Imam Khomeini International University, Qazvin, I. R. Iran
2 Department of Statistics, Faculty of Science, Imam Khomeini International University, Qazvin, I. R. Iran
doi
10.22061/jdma.2025.12370.1151چکیده
A protected node is a node that is not a leaf and none of its children is a leaf, and also a weakly protected node is not a leaf and at least one of its children is not a leaf. Let Pn and Wn be the path length of the protected and weakly protected nodes in a random binary search tree (BST) of size n, respectively. In this paper, we derive the exact mean and variance of these random variables and show that $$\frac{15 Pn}{11n\ln n}\to 1$$and$$\frac{15W_n}{14n\ln n}\to 1$$in probability.
