Limiting theorems for the nodes in binary search trees

DOI10.1007/S11425-007-0129-XMaRDI QIDQ2481277zbMATH OpenOpenAlexFDO

Authors Jie Liu, Su Chun, Chen Yu

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

binary search treecontraction methodlaw of large numberslimiting distributionnodes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

Recommendations

• Limit laws for local counters in random binary search trees
• On the subtrees of random binary search trees
• Asymptotic distribution of two-protected nodes in random binary search trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Weakly protected nodes in random binary search trees

Cites work

• A general limit theorem for recursive algorithms and combinatorial structures
• A note on the distance in random recursive trees
• A note on the distribution of the three types of nodes in uniform binary trees
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees
• An analytic approach to the height of binary search trees. II
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• Branching processes in the analysis of the heights of trees
• Constant bounds on the moments of the height of binary search trees
• Distances and Finger Search in Random Binary Search Trees
• Distribution of distances in random binary search trees.
• scientific article; zbMATH DE number 4023312 (Why is no real title available?)
• scientific article; zbMATH DE number 1375573 (Why is no real title available?)
• scientific article; zbMATH DE number 49698 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• Left and right pathlengths in random binary trees
• On a multivariate contraction method for random recursive structures with applications to quicksort
• On the concentration of the height of binary search trees
• On the Variance of the Height of Random Binary Search Trees
• Probability metrics and recursive algorithms
• The variance of the height of binary search trees

Cited in

(11)

• Normal limiting distribution of the size of binary interval trees
• Spanning tree size in random binary search trees.
• One-sided variations on binary search trees
• A scaling limit for the cover time of the binary tree
• scientific article; zbMATH DE number 2127734 (Why is no real title available?)
• Limit laws for local counters in random binary search trees
• Retracted: Strong limiting behavior in binary search trees
• scientific article; zbMATH DE number 1552323 (Why is no real title available?)
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Weakly protected nodes in random binary search trees
• Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees

This page was built for publication: Limiting theorems for the nodes in binary search trees

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