Martingales and Profile of Binary Search Trees

2004/10/07 by Brigitte Chauvin, Chauvin, Brigitte, Thierry Klein +5
Mathematics · #60C05 #60G42 #60G44 #60J25 #60J80 #68W40 #FOS: Mathematics #Probability (math.PR) #math.PR #msc:60C05 #msc:60G42 #msc:60G44 #msc:60J25 #msc:60J80 #msc:68W40

paper · pdf · doi:10.48550/arxiv.math/0410211

arxiv created 2004/10/07 · arxiv updated 2009/12/01

Abstract

We are interested in the asymptotic analysis of the binary search tree (BST) under the random permutation model. Via an embedding in a continuous time model, we get new results, in particular the asymptotic behavior of the profile.

Related

• Connecting Yule Process, Bisection and Binary Search Tree via Martingales
• Almost sure asymptotics for the random binary search tree
• On martingale tail sums for the path length in random trees
• Additive functionals on random search trees
• Dependence and phase changes in random m-ary search trees