Mixed Poisson approximation of node depth distributions in random binary search trees

DOI10.1214/105051604000000611zbMath1066.68031arXivmath/0503738OpenAlexW1494565703MaRDI QIDQ1774220

Rudolf Grübel, Nikolče Stefanoski

Publication date: 29 April 2005

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0503738

zbMATH Keywords

mixed Poisson distributions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Central limit and other weak theorems (60F05) Searching and sorting (68P10)

Related Items (4)

On moment sequences and mixed Poisson distributions ⋮ The left-right-imbalance of binary search trees ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ On weighted depths in random binary search trees

Uses Software

• Quicksort
• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Applications of the theory of records in the study of random trees
• Distribution of distances in random binary search trees.
• Exact and asymptotic distributions in digital and binary search trees
• Comparisons in Hoare's Find Algorithm
• Hoare's Selection Algorithm: A Markov Chain Approach
• Distances and Finger Search in Random Binary Search Trees
• Asymptotic distribution theory for Hoare's selection algorithm
• Randomized binary search technique

This page was built for publication: Mixed Poisson approximation of node depth distributions in random binary search trees