A Study of Trie-Like Structures Under the Density Model
Devroye, Luc
Ann. Appl. Probab., Tome 2 (1992) no. 4, p. 402-434 / Harvested from Project Euclid
We consider random tries constructed from sequences of i.i.d. random variables with a common density $f$ on $\lbrack 0, 1 \rbrack$ (i.e., paths down the tree are carved out by the bits in the binary expansions of the random variables). The depth of insertion of a node and the height of a node are studied with respect to their limit laws and their weak and strong convergence properties. In addition, laws of the iterated logarithm are obtained for the height of a random trie when $\int f^2 < \infty$. Finally, we study two popular improvements of the trie, the $\mathrm{PATRICIA}$ tree and the digital search tree, and show to what extent they improve over the trie.
Publié le : 1992-05-14
Classification:  Trie,  digital search tree,  probabilistic analysis,  strong convergence,  height of a tree,  60D05,  68U05
@article{1177005709,
     author = {Devroye, Luc},
     title = {A Study of Trie-Like Structures Under the Density Model},
     journal = {Ann. Appl. Probab.},
     volume = {2},
     number = {4},
     year = {1992},
     pages = { 402-434},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005709}
}
Devroye, Luc. A Study of Trie-Like Structures Under the Density Model. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp.  402-434. http://gdmltest.u-ga.fr/item/1177005709/