Distances in random digital search trees

DOI10.1007/S00236-006-0019-7zbMATH Open1102.60020OpenAlexW2162074286MaRDI QIDQ852009FDOQ852009

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

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

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)

Cites Work

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

Cited In (8)

• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• Distribution of inter-node distances in digital trees
• Average-Case Analysis of Cousins in m-ary Tries
• The Wiener Index of Random Digital Trees
• Probabilities Related to Father-Son Distances in Binary Search Trees
• Imbalance in random digital trees
• Limit distribution of distances in biased random tries
• Distances and Finger Search in Random Binary Search 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)