Path length of protected nodes in random binary search trees

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{۱۵ Pn}{۱۱n\ln n}\to ۱and\frac{۱۵W_n}{۱۴n\ln n}\to ۱in probability.

Keywords:

Binary search trees‎ , ‎path length‎ , ‎protected node‎ , ‎weakly protected node‎ , ‎limiting rule