The expected profile of digital search trees

DOI10.1016/J.JCTA.2011.04.001MaRDI QIDQ549244zbMATHOpenAlexFDO

Authors Michael Drmota, Wojciech Szpankowski

Publication date 7 July 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2011.04.001

zbMATH Keywords

Mellin transformanalysis of algorithmsgenerating functionsanalytic combinatoricsrecurrencessaddle point methoddigital search treespoissonizationtree profiles

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• scientific article; zbMATH DE number 7051180
• On the average profile of symmetric digital search trees
• The variance of the profile in digital search trees
• Typical depth of a digital search tree built on a general source
• scientific article; zbMATH DE number 849078

Cites work

• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2013191 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 2117212 (Why is no real title available?)
• A characterization of digital search trees from the successful search viewpoint
• A note on growing binary trees
• A study of trie-like structures under the density model
• Analytical depoissonization and its applications
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• Asymptotical growth of a class of random trees
• Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
• Average profile of the Lempel-Ziv parsing scheme for a Markovian source
• Exact and asymptotic distributions in digital and binary search trees
• Mellin transforms and asymptotics: Harmonic sums
• On the average profile of symmetric digital search trees
• Paths in a random digital tree: limiting distributions
• Profiles of Tries
• Random Trees
• Special issue: Average-case analysis of algorithms
• Width and mode of the profile for some random trees of logarithmic height

Cited in

(16)

• On the average profile of symmetric digital search trees
• Asymmetric Rényi problem
• Typical depth of a digital search tree built on a general source
• Asymptotic expectation of protected node profile in random digital search trees
• scientific article; zbMATH DE number 3961005 (Why is no real title available?)
• scientific article; zbMATH DE number 7051180 (Why is no real title available?)
• The Ubiquitous Digital Tree
• scientific article; zbMATH DE number 6145140 (Why is no real title available?)
• Digital search trees and chaos game representation
• Analysis of digital search trees incorporated with paging
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• scientific article; zbMATH DE number 1445303 (Why is no real title available?)
• Limit theorems for subtree size profiles of increasing trees
• The variance of the profile in digital search trees
• Profiles of PATRICIA tries
• Node profiles of symmetric digital search trees: Concentration properties

This page was built for publication: The expected profile of digital search trees

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