×

zbMATH — the first resource for mathematics

The height of list-tries and TST. (English) Zbl 1192.68945
2007 Conference on analysis of algorithms, AofA 07. Papers from the 13th Conference held in Juan-les-Pins, France, June 17–22, 2007. Nancy: The Association Discrete Mathematics & Theoretical Science (DMTCS). 247-258, electronic only (2007).
Summary: We characterize the asymptotics of heights of the trees of Briandais (1959) and the ternary search trees of Bentley (1997). 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.
For the entire collection see [Zbl 1180.68001].

MSC:
68W40 Analysis of algorithms
65Y99 Computer aspects of numerical algorithms
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: Link