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

DOI10.1016/S0020-0190(97)00206-8MaRDI QIDQ293237zbMATH OpenOpenAlexFDO

Authors Luc 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 binary search treesrandom permutationsubtrees

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• On the subtrees of random binary search trees
• On the subtree size profile of binary search trees
• Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
• On the largest common subtree of random leaf-labeled binary trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• scientific article; zbMATH DE number 852055 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Deviations from uniformity in random strings
• Limit laws for local counters in random binary search trees
• Negative association of random variables, with applications
• Weighted sums of certain dependent random variables

Cited in

(13)

• Average case analysis of leaf-centric binary tree sources
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• Simplifications of Uniform Expressions Specified by Systems
• On the subtree size profile of binary search trees
• On the number of distinct fringe subtrees in binary search trees
• The Expected Distribution of Degrees in Random Binary Search Trees
• Distinct fringe subtrees in random trees
• On the subtrees of random binary search trees
• Binary subtrees with few labeled paths
• Maximal clades in random binary search trees
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• A note on subtrees rooted along the primary path of a binary tree
• Limit theorems for subtree size profiles of increasing trees

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

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