فهرست نشریات علمی دسترسی آزاد ایران

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 15Pn/11n.ln n → 1 and 15Wn/14n.ln n→ 1 in probability.