Что такое префиксное дерево (trie) и где его применяют?

Trie — дерево, где каждое ребро помечено символом, а путь от корня задаёт строку: вставка, поиск и проверка префикса стоят O(L), где L — длина ключа, независимо от числа хранимых слов.

Устройство

• Узел: массив или словарь детей по символам плюс флаг «здесь заканчивается слово».
• Общие префиксы хранятся один раз: «cat» и «car» делят путь «ca».

Операции

• Вставка и поиск: спуск по символам ключа за O(L) — хешировать всю строку не нужно.
• Автодополнение: спустились по префиксу и собрали всё поддерево.

Цена

Память: на каждый узел приходится массив или словарь потомков — расточительно. Компактные варианты (сжатое trie, radix tree) сливают цепочки из одного ребёнка в одно ребро.

Применения

Автокомплит, словари с префиксными запросами, longest prefix match в маршрутизации, задачи «все слова на поле букв».

Коротко для собеседования

Trie хранит строки как пути по символам, поэтому поиск и проверка префикса зависят только от длины ключа, а общие префиксы хранятся один раз. Он идеален для автодополнения и longest prefix match, но расточителен по памяти — на практике часто берут сжатый radix tree.