On the shape of the fringe of various types of random trees

DOI10.1002/MMA.1085MaRDI QIDQ3634637zbMATH OpenOpenAlexFDO

Authors Michael Drmota, Bernhard Gittenberger, Alois Panholzer, Helmut Prodinger, Mark Daniel Ward

Publication date 25 June 2009

Published in Mathematical Methods in the Applied Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/mma.1085

zbMATH Keywords

analysis of algorithmspattern matchingsimply generated treessuffix treesbinary search treesdigital search treesrecursive treestriesPatricia trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• On the variety of shapes on the fringe of a random recursive tree
• On the Contour of Random Trees
• On the profile of random trees
• Asymptotic fringe distributions for general families of random trees
• Distinct fringe subtrees in random trees
• Pattern distribution in various types of random trees

Cites work

• scientific article; zbMATH DE number 4106282 (Why is no real title available?)
• scientific article; zbMATH DE number 5050583 (Why is no real title available?)
• Analysis of the average depth in a suffix tree under a Markov model
• Analytical depoissonization and its applications
• Asymptotic distributions and a multivariate Darboux method in enumeration problems
• Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Digital Search Trees Revisited
• Error Resilient LZ'77 Data Compression: Algorithms, Analysis, and Experiments
• File structures using hashing functions
• Limit laws for local counters in random binary search trees
• Mathematics for the Analysis of Algorithms.
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Mellin transforms and asymptotics: Harmonic sums
• On pattern frequency occurrences in a Markovian sequence
• On the Altitude of Nodes in Random Trees
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• Periods in strings
• Singularity Analysis of Generating Functions
• String overlaps, pattern matching, and nontransitive games
• The height distribution of leaves in rooted trees
• Total Path Length for Random Recursive Trees
• Two Notes on Notation
• Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are Unreliable

Cited in

(4)

• Asymptotic fringe distributions for general families of random trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Fringe analysis of plane trees related to cutting and pruning
• Limit theorems for patterns in phylogenetic trees

This page was built for publication: On the shape of the fringe of various types of random trees

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