Префиксное дерево (trie)
Древовидная структура данных, где каждый узел соответствует символу, — поиск по префиксу занимает O(длина префикса).
Классическое применение: автодополнение, проверка орфографии, таблицы маршрутизации IP (longest-prefix match). Вариант — radix tree (сжатое). Современные пользователи: маршрутизация в nginx, маршрутизация в ядре Linux, многие индексы баз данных.