On the expected height of fringe-blanced trees

DOI10.1007/BF01210596zbMath0790.68025MaRDI QIDQ1323353

Luc P. Devroye

Publication date: 4 July 1994

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

random binary search tree

Mathematics Subject Classification ID

Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Data structures (68P05)

Related Items (6)

The asymptotic distribution of cluster sizes for supercritical percolation on random split trees ⋮ Balancing \(m\)-ary search trees with compressions on the fringe ⋮ Weighted height of random trees ⋮ The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees ⋮ The fluctuations of the giant cluster for percolation on random split trees ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees

Cites Work

• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• Postulates for subadditive processes
• Subadditive ergodic theory
• Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
• The analysis of a fringe heuristic for binary search trees
• On the height of random m‐ary search trees
• A note on the height of binary search trees
• The first- and last-birth problems for a multitype age-dependent branching process
• Locally balanced binary trees
• Chernoff's theorem in the branching random walk
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the expected height of fringe-blanced trees