The height of a binary search tree: the limiting distribution perspective.

DOI10.1016/S0304-3975(01)00387-5zbMath1061.68039MaRDI QIDQ1853551

Charles Knessl, Wojciech Szpankowski

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

WKB methodNonlinear integral equationLinearizationSaddle point methodBinary search treesLimiting height distributionMatched asymptotics

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (2)

Reductions in binary search trees ⋮ Some new results for McKean's graphs with applications to Kac's equation

Cites Work

• Differential-difference equations
• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• Special issue: Average-case analysis of algorithms
• An analytic approach to the height of binary search trees
• How tall is a tree?
• Singularity Analysis of Generating Functions
• Exact and asymptotic distributions in digital and binary search trees
• A note on the height of binary search trees
• Singular Perturbation Analysis of Boundary Value Problems for Differential-Difference Equations. V. Small Shifts with Layer Behavior
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• On the Variance of the Height of Random Binary Search Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The height of a binary search tree: the limiting distribution perspective.