Analysis of random LC tries
Luc Devroye · Random Structures and Algorithms · 2001
Abstract LC tries were introduced by Andersson and Nilsson in 1993. They are compacted versions of tries or patricia tries in which, from the top down, maximal height complete subtrees are level compressed. Andersson and Nilsson (1993) showed that for i.i.d. uniformly distributed input strings, the expected depth of the LC patricia trie is Θ(log* n). In this article, we refine and extend this result. We analyze both kinds of LC tries for the uniform model, and study the depth of a typical node and the height Hn. For example, we show that Hn is in probability asymptotic to log2 n and \documentclass{article}\pagestyle{empty}\begin{document}$\sqrt{2 \log_2 n}$\end{document} for the LC trie and the LC patricia trie, respectively, and that for both the tries, the depth of a typical node is asymptotic to log*(n) in probability and in expectation. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 359–375, 2001