Premium
Analysis of random LC tries
Author(s) -
Devroye Luc
Publication year - 2001
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.10006
Subject(s) - trie , node (physics) , combinatorics , binary logarithm , mathematics , discrete mathematics , computer science , physics , data structure , quantum mechanics , programming language
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 H n . For example, we show that H n is in probability asymptotic to log 2 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