DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional