One-sided variations on binary search trees

DOI10.1007/BF02523399zbMath1099.68601MaRDI QIDQ1881001

Hosam M. Mahmoud

Publication date: 27 September 2004

Published in: Annals of the Institute of Statistical Mathematics (Search for Journal in Brave)

zbMATH Keywords

contractionlimit distributionrecurrence equationdegenerate limitRandom tree

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Data structures (68P05)

Related Items (4)

Paths in \(m\)-ary interval trees ⋮ Normal limiting distribution of the size of binary interval trees ⋮ Fragment size distributions in random fragmentations with cutoff ⋮ One-sided variations on interval trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to select a loser
• Random sequential bisection and its associated binary tree
• Applications of the theory of records in the study of random trees
• On the distribution for the duration of a randomized leader election algorithm
• On the number of descendants and ascendants in random search trees
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Distribution of distances in random binary search trees.
• On the contraction method with degenerate limit equation.
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• One-sided variations on interval trees
• Probability metrics and recursive algorithms
• Randomized binary search technique
• Cutting down random trees
• A limit theorem for “quicksort”
• The variance of the height of binary search trees

This page was built for publication: One-sided variations on binary search trees