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
Charles Knessl, Wojciech Szpankowski
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
WKB methodNonlinear integral equationLinearizationSaddle point methodBinary search treesLimiting height distributionMatched asymptotics
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.