Analysis of random LC tries
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 Theta (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 H-n. For example, we show that H-n is in probability asymptotic to log(2)n and root2-log(2)n 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. (C) 2001 John Wiley & Sons, Inc.
trie lc trie patricia tree probabilistic analysis law of large numbers height of a tree