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.

کلیدواژه ها:

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