Extremal Weighted Path Lengths in Random Binary Search Trees

Journal Article

Lasmar, Rafik Aguech, Hosam Mahmoud, Nabil . 2007

• نوع عمل المنشور: Research Paper
• رابط المنشور على الويب: PDF
• الوسوم: Paper
• المجلة \ الصحيفة: Probability in the Engineering and Informational Sciences
• رقم العدد: 1
• رقم الإصدار السنوي: 21
• الصفحات: 133 إلى141

مستخلص المنشور

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.