The Height of List-tries and TST
N. Broutin, L. Devroye
Abstract
We characterize the asymptotics of heights of the trees of [briandais59trie] and the ternary search trees (TST) of [bentley97fast]. Our proof is based on a new analysis of the structure of tries that distinguishes the bulk of the tree, called the core, and the long trees hanging down the core, called the spaghettis.
Full Text: GZIP Compressed PostScript PostScript PDF