Smoothed Analysis of Trie Height by Star-like PFAs

Stefan Eckhardt, Sven Kosub, Johannes Nowak

Tries are general purpose data structures for information retrieval. The most significant parameter of a trie is its height $H$ which equals the length of the longest common prefix…