Distances and Finger Search in Random Binary Search Trees
From MaRDI portal
Publication:4651486
DOI10.1137/S0097539703424521zbMath1082.68023MaRDI QIDQ4651486
Ralph Neininger, Luc P. Devroye
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Searching and sorting (68P10) Combinatorial probability (60C05) Data structures (68P05)
Related Items
Distances in random digital search trees ⋮ The left-right-imbalance of binary search trees ⋮ Labels distance in bucket recursive trees with variable capacities of buckets ⋮ Retracted: Strong limiting behavior in binary search trees ⋮ The analysis of range quickselect and related problems ⋮ Limiting theorems for the nodes in binary search trees ⋮ On the distribution of distances between specified nodes in increasing trees ⋮ Mixed Poisson approximation of node depth distributions in random binary search trees ⋮ On weighted depths in random binary search trees ⋮ Limit laws for the Randić index of random binary tree models ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ The Wiener Index of Random Digital Trees ⋮ EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES