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 Bernoulli 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.

Consider a random word in which the individual symbols are drawn from a finite or infinite alphabet with symbol probabilities $p_i $ , and let $H_n $ be the height of the suffix tree constructed from the first n suffixes of this word. It is shown that $H_n $ is asymptotically close to $2\log n/\log (1/\sum_i p_i^2 )$ in many respects: the difference is $O(\log \log n)$ in probability, and the ratio tends to one almost surely and in the mean.