The height of a binary search tree: the limiting distribution perspective.
From MaRDI portal
Publication:1853551
DOI10.1016/S0304-3975(01)00387-5zbMath1061.68039MaRDI QIDQ1853551
Wojciech Szpankowski, Charles Knessl
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
WKB method; Nonlinear integral equation; Linearization; Saddle point method; Binary search trees; Limiting height distribution; Matched asymptotics
Related Items
Some new results for McKean's graphs with applications to Kac's equation, Reductions in binary search trees
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
