The Profile of Binary Search Trees

Abstract

We characterize the limiting behavior of the number of nodes in level k of binary search trees T n in the central region 1 2 log n ≤ k ≤ 2 8 log n.Especially we show that the width V n (the maximal number of internal nodes at the same level) satisfies V n ∼ n/ 4π log n as n → ∞ a.s.

Locations

• arXiv (Cornell University) - PDF
• The Annals of Applied Probability - View - PDF