Distances in random digital search trees

DOI10.1007/s00236-006-0019-7zbMath1102.60020OpenAlexW2162074286MaRDI QIDQ852009

Rafik Aguech, Nabil Lasmar, Hosam M. Mahmoud

Publication date: 27 November 2006

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-006-0019-7

zbMATH Keywords

Mellin transformFixed pointPoissonizationRecurrenceContraction methodRandom trees

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Searching and sorting (68P10) Combinatorial probability (60C05) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (3)

Average-Case Analysis of Cousins in m-ary Tries ⋮ Imbalance in random digital trees ⋮ The Wiener Index of Random Digital Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The oscillatory distribution of distances in random tries
• Mellin transforms and asymptotics: Harmonic sums
• Asymptotical growth of a class of random trees
• Further results on digital search trees
• Analytical depoissonization and its applications
• A characterization of digital search trees from the successful search viewpoint
• Linear probing and graphs
• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Distribution of distances in random binary search trees.
• Spanning tree size in random binary search trees.
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Limit distribution of distances in biased random tries
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Digital Search Trees Revisited
• Exact and asymptotic distributions in digital and binary search trees
• Average Profile of the Generalized Digital Search Tree and the Generalized Lempel--Ziv Algorithm
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• Distances and Finger Search in Random Binary Search Trees
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
• Probability metrics and recursive algorithms
• File structures using hashing functions
• A limit theorem for “quicksort”

This page was built for publication: Distances in random digital search trees