Smoothed heights of tries and patricia tries

DOI10.1016/J.TCS.2015.02.009zbMath1332.68037OpenAlexW2023422760MaRDI QIDQ896160

Randy Goebel, Weitian Tong, Guo-Hui Lin

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.009

zbMATH Keywords

triesmoothed analysisdata structurepatricia trie

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (1)

Influence analysis: A survey of the state-of-the-art

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic analysis of the height of tries and of the complexity of triesort
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• On the average height of trees in digital search and dynamic hashing
• An experimental study of compression methods for dynamic tries
• Smoothed analysis of algorithms
• Paths in a random digital tree: limiting distributions
• Some results on V-ary asymmetric tries
• Analysis of Extendible Hashing
• On the Application of the Borel-Cantelli Lemma

This page was built for publication: Smoothed heights of tries and patricia tries