On the subtree size profile of binary search trees

DOI10.1017/S0963548309990630MaRDI QIDQ4933600zbMATH OpenFDO

Authors Florian Dennert, Rudolf Grübel

Publication date 14 October 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548309990630

zbMATH Keywords

binary search tree algorithmrandom treestree sequence

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• On the subtrees of random binary search trees
• Random binary trees. Algorithms, asymptotics and statistics
• The profile of binary search trees
• Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
• On the richness of the collection of subtrees in random binary search trees

Cites work

• A functional limit theorem for the profile of search trees
• A general limit theorem for recursive algorithms and combinatorial structures
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• Limit laws for local counters in random binary search trees
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
• The profile of binary search trees

Cited in

(13)

• Normal limiting distribution of the size of binary interval trees
• The profile of binary search trees
• Distinct fringe subtrees in random trees
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• Search trees: metric aspects and strong limit theorems
• The subtree size profile of bucket recursive trees
• Limit theorems for subtree size profiles of increasing trees
• Random binary trees. Algorithms, asymptotics and statistics
• On the richness of the collection of subtrees in random binary search trees
• On the subtrees of random binary search trees
• scientific article; zbMATH DE number 6145140 (Why is no real title available?)
• Binary search trees of permuton samples
• Martingales and profile of binary search trees

This page was built for publication: On the subtree size profile of binary search trees

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