The profile of binary search trees

DOI10.1214/aoap/1015345394zbMath1012.60038OpenAlexW2068858638MaRDI QIDQ1872435

Jean Jabbour-Hattab, Brigitte Chauvin, Michael Drmota

Publication date: 6 May 2003

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1015345394

zbMATH Keywords

martingalescomplex analysisasymptotic series expansionrepartition of nodes for binary search trees

Mathematics Subject Classification ID

Trees (05C05) Functional limit theorems; invariance principles (60F17)

Related Items (20)

Limit Theorems for Subtree Size Profiles of Increasing Trees ⋮ Edgeworth expansions for profiles of lattice branching random walks ⋮ General Edgeworth expansions with applications to profiles of random trees ⋮ The degree profile of random Pólya trees ⋮ Weak convergence of the number of vertices at intermediate levels of random recursive trees ⋮ Random walks with preferential relocations and fading memory: a study through random recursive trees ⋮ Maximal flow in branching trees and binary search trees ⋮ A functional limit theorem for the profile of random recursive trees ⋮ Profiles of random trees: correlation and width of random recursive trees and binary search trees ⋮ Search trees: metric aspects and strong limit theorems ⋮ A functional limit theorem for the profile of search trees ⋮ On martingale tail sums for the path length in random trees ⋮ On the Subtree Size Profile of Binary Search trees ⋮ The shape of unlabeled rooted random trees ⋮ On the silhouette of binary search trees ⋮ A functional limit theorem for the profile of \(b\)-ary trees ⋮ Random Records and Cuttings in Binary Search Trees ⋮ Width and mode of the profile for some random trees of logarithmic height ⋮ Width of a scale-free tree ⋮ Geometry of weighted recursive and affine preferential attachment trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Branching processes in the analysis of the heights of trees
• Martingales and large deviations for binary search trees
• Asymptotic Development of the Stirling Numbers of the First Kind
• Singularity Analysis of Generating Functions
• More Combinatorial Properties of Certain Trees

This page was built for publication: The profile of binary search trees