Martingales and large deviations for binary search trees

DOI10.1002/rsa.1023zbMath0983.60034OpenAlexW2038368294MaRDI QIDQ2748421

Jean Jabbour-Hattab

Publication date: 14 October 2001

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.1023

zbMATH Keywords

asymptotic resultsdepth of the external nodesnumber of external nodes at deepest level

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Random graphs (graph-theoretic aspects) (05C80)

Related Items (7)

The profile of binary search trees ⋮ General Edgeworth expansions with applications to profiles of random trees ⋮ A functional limit theorem for the profile of random recursive trees ⋮ Search trees: metric aspects and strong limit theorems ⋮ On martingale tail sums for the path length in random trees ⋮ A functional limit theorem for the profile of \(b\)-ary trees ⋮ Width and mode of the profile for some random trees of logarithmic height

Cites Work

• Unnamed Item
• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• On Random Binary Trees
• Exact and asymptotic distributions in digital and binary search trees
• Randomized binary search trees
• A note on the height of binary search trees
• On the Variance of the Height of Random Binary Search Trees

This page was built for publication: Martingales and large deviations for binary search trees