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

DOI10.1137/S0895480104440134zbMath1086.68037MaRDI QIDQ5317595

Michael Drmota, Hsien-Kuei Hwang

Publication date: 16 September 2005

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

zbMATH Keywords

profileBessel functionssingularity analysisbinary search treessaddle-point methodStirling numbers of the first kindasymptotic bimodality

Mathematics Subject Classification ID

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

Related Items (7)

Limit Theorems for Subtree Size Profiles of Increasing Trees ⋮ Shape Measures of Random Increasing k-trees ⋮ Profiles of random trees: correlation and width of random recursive trees and binary search trees ⋮ A functional limit theorem for the profile of 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