Probabilistic behavior of asymmetric level compressed tries
Luc Devroye, W. Szpankowski · Random Structures and Algorithms · 2005
Abstract Level‐Compressed (in short LC) tries were introduced by Andersson and Nilsson in 1993. They are compacted versions of tries in which, from the top down, maximal height complete subtrees are level compressed. We show that when the input consists of n independent strings with independent Bernoulli (p) bits, p ≠ 1/2, then the expected depth of a typical node is in probability asymptotic to where H − p log p − (1 − p) log (1 − p) is the Shannon entropy of the source, and H−∞ = log (1 / min(p, 1 − p)). The height is in probability asymptotic to where H2 = log(1/(p2 + (1−p)2)). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005