Extremal Weighted Path Lengths in Random Binary Search Trees

Lasmar, Rafik Aguech, Hosam Mahmoud, Nabil . 2007

Paper

We consider weighted path lengths to the extremal leaves in a random binary search tree. When linearly scaled, the weighted path length to the minimal label has Dickman's infinitely divisible distribution as a limit. By contrast, the weighted path length to the maximal label needs to be centered and scaled to converge to a standard normal variate in distribution. The exercise shows that path lengths associated with different ranks exhibit different behaviors depending on the rank. However, the majority of the ranks have a weighted path length with average behavior similar to that of the weighted path to the maximal node.

نوع عمل المنشور

Research Paper

رقم المجلد

رقم الانشاء

مجلة/صحيفة

Probability in the Engineering and Informational Sciences

الصفحات

133 إلى141