On the richness of the collection of subtrees in random binary search trees

DOI10.1016/S0020-0190(97)00206-8zbMath1339.68051OpenAlexW2127892269MaRDI QIDQ293237

Luc P. Devroye

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002068?np=y

zbMATH Keywords

computational complexityprobabilistic analysisrandom permutationrandom binary search treessubtrees

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (5)

Limit Theorems for Subtree Size Profiles of Increasing Trees ⋮ Compaction for two models of logarithmic‐depth trees: Analysis and experiments ⋮ Simplifications of Uniform Expressions Specified by Systems ⋮ Unnamed Item ⋮ Distinct fringe subtrees in random trees

Cites Work

• Deviations from uniformity in random strings
• Negative association of random variables, with applications
• Weighted sums of certain dependent random variables
• Limit laws for local counters in random binary search trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the richness of the collection of subtrees in random binary search trees