On the smoothed heights of Trie and Patricia index trees
Full Text: Tong2014_Chapter_OnTheSmoothedHeightsOfTrieAndP.pdf
Two of the most popular data structures for storing strings are the Trie and the Patricia index trees. Let H n denote the height of the Trie (the Patricia, respectively) on a set of n strings. It is well known that under the uniform distribution model on the strings, for Trie H n /logn → 2 and for Patricia H n /logn → 1, when n approaches infinity. Nevertheless, in the worst case, the height of the Trie on n strings is unbounded, and the height of the Patricia on n strings is in Θ(n). To better understand the practical performance of both the Trie and Patricia index trees, we investigate these two classical data structures in a smoothed analysis model. Given a set ={𝑠1,𝑠2,…,𝑠𝑛} of n binary strings, we perturb the set by adding an i.i.d Bernoulli random noise to each bit of every string. We show that the resulting smoothed heights of Trie and Patricia trees are both Θ(logn).
Citation
W. Tong, R. Goebel, G. Lin. "On the smoothed heights of Trie and Patricia index trees". International Computing and Combinatorics Conference (COCOON), pp 94-103, August 2014.| Keywords: | |
| Category: | In Conference |
| Web Links: | Springer |
BibTeX
@incollection{Tong+al:(COCOON)14,
author = {Weitian Tong and Randy Goebel and Guohui Lin},
title = {On the smoothed heights of Trie and Patricia index trees},
Pages = {94-103},
booktitle = {International Computing and Combinatorics Conference (COCOON)},
year = 2014,
}Last Updated: June 10, 2020Submitted by Sabina P
