Limiting theorems for the nodes in binary search trees

DOI10.1007/s11425-007-0129-xzbMath1137.60010MaRDI QIDQ2481277

Jie Liu, Chen Yu, Su Chun

Publication date: 9 April 2008

Published in: Science in China. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11425-007-0129-x

zbMATH Keywords

law of large numbers; nodes; limiting distribution; contraction method; binary search tree

Mathematics Subject Classification ID

60F05: Central limit and other weak theorems

05C80: Random graphs (graph-theoretic aspects)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Left and right pathlengths in random binary trees
• Branching processes in the analysis of the heights of trees
• A note on the distribution of the three types of nodes in uniform binary trees
• A general limit theorem for recursive algorithms and combinatorial structures
• Constant bounds on the moments of the height of binary search trees
• An analytic approach to the height of binary search trees
• Distribution of distances in random binary search trees.
• A note on the distance in random recursive trees
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• An analytic approach to the height of binary search trees II
• A note on the height of binary search trees
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• On the concentration of the height of binary search trees
• Distances and Finger Search in Random Binary Search Trees
• Probability metrics and recursive algorithms
• On the Variance of the Height of Random Binary Search Trees
• The variance of the height of binary search trees