Analysis of random LC tries

LC tries were introduced by Andersson and Nilsson in 1993. They are compact ed 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 m odel, 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 probabi lity and in expectation. (C) 2001 John Wiley & Sons, Inc.