Distances in random digital search trees

DOI10.1007/S00236-006-0019-7MaRDI QIDQ852009zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Distribution of inter-node distances in digital trees
• Distribution of distances in random binary search trees.
• Limit distribution of distances in biased random tries
• scientific article; zbMATH DE number 849078
• The variance of the profile in digital search trees

Cites work

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

Cited in

(10)

• Imbalance in random digital trees
• The \(k\)-th total path length and the total Steiner \(k\)-distance for digital search trees
• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• Limit distribution of distances in biased random tries
• Average-Case Analysis of Cousins in m-ary Tries
• Probabilities Related to Father-Son Distances in Binary Search Trees
• Continuous-time digital search tree and a border aggregation model
• Distribution of inter-node distances in digital trees
• Distances and Finger Search in Random Binary Search Trees
• The Wiener index of random digital trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q852009)