Premium
Probabilistic behavior of asymmetric level compressed tries
Author(s) -
Devroye Luc,
Szpankowski Wojcieh
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20067
Subject(s) - bernoulli's principle , struct , mathematics , probabilistic logic , binary logarithm , entropy (arrow of time) , combinatorics , discrete mathematics , statistics , physics , computer science , quantum mechanics , thermodynamics , programming language
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$${{\rm log\,\,log}\,\,n} \over {\rm log}\,\, \left(1 - {{\cal H} \over {\cal H} - \infty}\right)$$ 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$${{\rm log}\,\,n}\,\, \over {\cal H}_2$$ where H 2 = log(1/( p 2 + (1− p ) 2 )). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005