The expected profile of digital search trees

DOI10.1016/J.JCTA.2011.04.001zbMATH Open1233.68127OpenAlexW2117773253MaRDI QIDQ549244FDOQ549244

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

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

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)

Cites Work

• Title not available (Why is that?)
• Random Trees
• Mellin transforms and asymptotics: Harmonic sums
• Title not available (Why is that?)
• Special issue: Average-case analysis of algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact and asymptotic distributions in digital and binary search trees
• Analytical depoissonization and its applications
• Profiles of Tries
• Width and mode of the profile for some random trees of logarithmic height
• Asymptotical growth of a class of random trees
• A characterization of digital search trees from the successful search viewpoint
• A study of trie-like structures under the density model
• A note on growing binary trees
• On the average profile of symmetric digital search trees
• Paths in a random digital tree: limiting distributions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• 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
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees

Cited In (14)

• Title not available (Why is that?)
• Digital search trees and chaos game representation
• Title not available (Why is that?)
• Node profiles of symmetric digital search trees: Concentration properties
• Title not available (Why is that?)
• On the average profile of symmetric digital search trees
• The Ubiquitous Digital Tree
• Asymptotic expectation of protected node profile in random digital search trees
• Profiles of PATRICIA tries
• The variance of the profile in digital search trees
• Limit theorems for subtree size profiles of increasing trees
• Asymmetric Rényi Problem
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• Title not available (Why is that?)

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)