A Study of Trie-Like Structures Under the Density Model

We consider random tries constructed from sequences of i.i.d. random variables with a common density f on [0,1] (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 .f2<.. Finally, we study two popular improvements of the trie, the PATRICIA tree and the digital search tree, and show to what extent they improve over the trie.