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

DOI10.1016/S0304-3975(01)00387-5MaRDI QIDQ1853551zbMATH OpenFDO

Authors 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

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

Recommendations

• An analytic approach to the height of binary search trees
• Branching processes in the analysis of the heights of trees
• A note on the height of binary search trees
• On the concentration of the height of binary search trees
• On the Variance of the Height of Random Binary Search Trees

Cites work

• scientific article; zbMATH DE number 3649136 (Why is no real title available?)
• scientific article; zbMATH DE number 4069516 (Why is no real title available?)
• scientific article; zbMATH DE number 1375579 (Why is no real title available?)
• scientific article; zbMATH DE number 3703128 (Why is no real title available?)
• scientific article; zbMATH DE number 44103 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1231230 (Why is no real title available?)
• scientific article; zbMATH DE number 1339099 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1512698 (Why is no real title available?)
• scientific article; zbMATH DE number 863491 (Why is no real title available?)
• scientific article; zbMATH DE number 3104956 (Why is no real title available?)
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• Branching processes in the analysis of the heights of trees
• Differential-difference equations
• Exact and asymptotic distributions in digital and binary search trees
• How tall is a tree?
• On growing random binary trees
• On the Variance of the Height of Random Binary Search Trees
• Singular Perturbation Analysis of Boundary Value Problems for Differential-Difference Equations. V. Small Shifts with Layer Behavior
• Singularity Analysis of Generating Functions
• Special issue: Average-case analysis of algorithms

Cited in

(13)

• Uniform distribution modulo one and binary search trees
• Constant bounds on the moments of the height of binary search trees
• How tall is a tree?
• Almost sure asymptotics for the random binary search tree
• Some new results for McKean's graphs with applications to Kac's equation
• Reductions in binary search trees
• scientific article; zbMATH DE number 1741002 (Why is no real title available?)
• The height of record‐biased trees
• The height of Mallows trees
• scientific article; zbMATH DE number 1552321 (Why is no real title available?)
• scientific article; zbMATH DE number 2038884 (Why is no real title available?)
• Algorithms and Computation
• On Finding the Height of a Binary Search Tree

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853551)