An analytic approach to the height of binary search trees

MaRDI QIDQ1840504zbMATH OpenFDO

Authors Michael Drmota

Publication date 11 February 2001

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

binary search trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Recommendations

• On the Variance of the Height of Random Binary Search Trees
• Numerical studies of the expected height in randomly built binary search trees
• The height of a random binary search tree
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees. II

Cited in

(37)

• Retracted: Strong limiting behavior in binary search trees
• The Distribution of Heights of Binary Trees and Other Simple Trees
• The height of increasing trees
• The variance of the height of binary search trees
• On Robson's convergence and boundedness conjectures concerning the height of binary search trees
• scientific article; zbMATH DE number 3845601 (Why is no real title available?)
• Constant bounds on the moments of the height of binary search trees
• Note on the heights of random recursive trees and random m‐ary search trees
• How tall is a tree?
• Smoothed analysis of binary search trees
• An analytic approach to the height of binary search trees. II
• Binary search trees of almost optimal height
• The height of a binary search tree: the limiting distribution perspective.
• Limiting theorems for the nodes in binary search trees
• scientific article; zbMATH DE number 1741002 (Why is no real title available?)
• The height of record‐biased trees
• scientific article; zbMATH DE number 3847416 (Why is no real title available?)
• One-sided variations on binary search trees
• Branching processes in the analysis of the heights of trees
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• (Un)expected path lengths of asymmetric binary search trees
• scientific article; zbMATH DE number 3904610 (Why is no real title available?)
• scientific article; zbMATH DE number 2038884 (Why is no real title available?)
• The Expected Distribution of Degrees in Random Binary Search Trees
• The average height of Catalan trees by counting lattice paths
• The height of a random binary search tree
• scientific article; zbMATH DE number 3896954 (Why is no real title available?)
• Some estimates for the distribution of the height of digital search trees
• scientific article; zbMATH DE number 3906516 (Why is no real title available?)
• On the height of random m‐ary search trees
• Numerical studies of the expected height in randomly built binary search trees
• A note on the height of binary search trees
• On the concentration of the height of binary search trees
• Extreme value statistics and traveling fronts: Various applications
• Analytical estimates and proof of the scale-free character of efficiency and improvement in Barabási-Albert trees
• Algorithms and Computation
• On Finding the Height of a Binary Search Tree

This page was built for publication: An analytic approach to the height of binary search trees

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