Almost sure asymptotics for the random binary search tree

MaRDI QIDQ2959932zbMATH OpenFDO

Authors Matthew I. Roberts

Publication date 10 February 2017

Full work available at URL https://arxiv.org/abs/1002.3896, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0139

zbMATH Keywords

branching random walkQuicksortrandom permutation modelbinary search treeYule tree

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05) Searching and sorting (68P10)

Abstract: We consider a (random permutation model) binary search tree with n nodes and give asymptotics on the loglog scale for the height H_n and saturation level h_n of the tree as n oinfty, both almost surely and in probability. We then consider the number F_n of particles at level H_n at time n, and show that F_n is unbounded almost surely.

Recommendations

• A note on the height of binary search trees
• The profile of binary search trees
• The height of a random binary search tree
• The height of a binary search tree: the limiting distribution perspective.
• On the Variance of the Height of Random Binary Search Trees

Cited in

(6)

• Asymptotic variance of random symmetric digital search trees
• Random binary trees: from the average case analysis to the asymptotics of distributions
• Transfer theorems and asymptotic distributional results for m‐ary search trees
• An almost sure result for path lengths in binary search trees
• An Improved Bound for Random Binary Search Trees with Concurrent Insertions
• Complex Burgers equation: a probabilistic perspective

This page was built for publication: Almost sure asymptotics for the random binary search tree

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