2001/09/18 by Satya N. Majumdar, P. L. Krapivsky
Computer Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Binary number #Binary search tree #Binary tree #Combinatorics #Computer science #Data Management and Algorithms #Distribution (mathematics) #Interval tree #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Optimal binary search tree #Random binary tree #Random tree #Stochastic processes and statistical mechanics #Tree (set theory) #Tree structure #cond-mat.dis-nn #cond-mat.stat-mech #cs.DS
paper · pdf · doi:10.1103/physreve.65.036127
published as Phys. Rev. E 65, 036127 (2002) · 16 pages, two-column revtex
arxiv created 2001/09/18 · openalex publication_date 2002/02/27 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the statistics of height and balanced height in the binary search tree problem in computer science. The search tree problem is first mapped to a fragmentation problem that is then further mapped to a modified directed polymer problem on a Cayley tree. We employ the techniques of traveling fronts to solve the polymer problem and translate back to derive exact asymptotic properties in the original search tree problem. The second mapping allows us not only to again derive the already known results for random binary trees but to obtain exact results for search trees where the entries arrive according to an arbitrary distribution, not necessarily randomly. Besides it allows us to derive the asymptotic shape of the full probability distribution of height and not just its moments. Our results are then generalized to m-ary search trees with arbitrary distribution.