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 ∫ f² < ∞. 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.
No takes yet. Share an insight, caveat, or question.
Luc Devroye (1992) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: