Префиксные деревья (Trie): Структуры данных для автокомплита и роутинга

Термин Trie (читается как "трай") происходит от слова retrieval (поиск информации). В отличие от обычного бинарного дерева поиска, где узел хранит целый ключ, в префиксном дереве позиция узла определяет строку, с которой он связан. Корневой узел представляет пустую строку. Каждое ребро, отходящее от узла, помечается одним символом алфавита.

Путь от корня до любого узла дерева "собирает" строку, склеивая символы на пройденных ребрах. Таким образом, все слова, имеющие общий префикс, гарантированно имеют общего предка в дереве. Например, слова "КАРТА" и "КАРТОН" будут идти по одному и тому же пути "К-А-Р-Т", и только на этом узле дерево разветвится: одно ребро пойдет к "А", другое к "О". Специальный маркер (флаг окончания слова) ставится на узле, чтобы отличить префикс "КОТ" от полноценного слова "КОТ" внутри слова "КОТЕЛ".

Асимптотическая сложность операций в Trie поразительна. Поиск, вставка или удаление слова занимают время O(L), где L — длина самого слова! Это время абсолютно не зависит от того, сколько миллионов слов хранится в словаре. Это делает Trie в сотни раз быстрее обычных бинарных деревьев при работе со строками.

Однако классическое Trie обладает серьезным недостатком: оно потребляет огромные объемы оперативной памяти, так как каждый узел должен хранить массив указателей на возможных потомков (для английского алфавита — массив из 26 ячеек, большинство из которых пустые). Для решения этой проблемы используются оптимизации:

• Сжатое префиксное дерево (Radix tree / Patricia tree): узлы, имеющие только одного потомка, объединяются (склеиваются) вместе с родителем, а ребро помечается не одним символом, а целой строкой. Это радикально экономит память.
• Тернарное дерево поиска (Ternary Search Tree): гибрид Trie и бинарного дерева, где каждый узел имеет ровно три потомка (меньше, равно, больше).

Помимо словарей и спеллчекеров, Radix-деревья используются в ядре операционной системы Linux для управления таблицами маршрутизации IP-адресов. Они позволяют мгновенно находить самый длинный совпадающий префикс (Longest Prefix Match), чтобы направить интернет-пакет в правильный порт сетевой карты.