Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees

DOI10.1137/S0895480104440134MaRDI QIDQ5317595zbMATH OpenFDO

Authors Michael Drmota, Hsien-Kuei Hwang

Publication date 16 September 2005

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480104440134

zbMATH Keywords

asymptotic bimodalityBessel functionsbinary search treesprofilesaddle-point methodsingularity analysisStirling numbers of the first kind

Mathematics Subject Classification ID

Combinatorial probability (60C05) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• On the subtrees of random binary search trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• On the Variance of the Height of Random Binary Search Trees
• Profiles of random trees: Plane-oriented recursive trees

Cited in

(8)

• A functional limit theorem for the profile of search trees
• Limit theorems for subtree size profiles of increasing trees
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• Shape measures of random increasing k-trees
• Profiles of random trees: correlation and width of random recursive trees and binary search trees
• The shape of unlabeled rooted random trees
• A functional limit theorem for the profile of \(b\)-ary trees
• Width and mode of the profile for some random trees of logarithmic height

This page was built for publication: Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees

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