LIMITING DISTRIBUTION FOR THE DEPTH IN PATRICIA TRIES

Digital tries occur in a variety of computer and communication algorithms, including symbolic manipulations, compiling, comparison-based searching and sorting, digital retrieval techniques, algorithms on strings, file systems, codes, and communication protocols. The depth of the PATRICIA trie in a probabilistic framework is studied. The PATRICIA trie is a digital tree in which nodes that would otherwise have only one branch have been collapsed into nodes having more than one branch. Because of this characteristic, the depth of the PATRICIA trie provides a measure on the compression of the keys stored in the trie. Here, n independent keys that are random strings of symbols from a V-ary alphabet are considered. This model is known as the Bemoulli model. This paper shows that the depth in the asymmetric case (i.e., symbols from the alphabet do not occur with the same probability) is asymptotically normally distributed. In the symmetric case, which surprisingly proved to be more difficult, the limiting generating function and the limiting distribution are presented. In either case, the results point to the conclusion that the PATRICIA trie is with high probability a well-balanced tree.