The height of list-tries and TST. (English) Zbl 1192.68945

Broutin, N.; Devroye, L.

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

Keywords:

tries; branching process; height; de la Briandais; TST