Что такое trie (префиксное дерево) — и почему подсказка не перебирает весь словарь

Ты делаешь поле поиска с подсказками. Нейросеть пишет честное решение:

const hints = words.filter(w => w.startsWith(query)).slice(0, 10);

На 300 словах летает. Потом ты подгружаешь словарь на 100 000 слов. И каждая нажатая буква — это 100 000 сравнений. Человек печатает «про», а код трижды пробегает весь словарь целиком. Включая «яблоко» и «зебру», которые точно не подходят.

Смотри, тут хитрость: все слова на «про» уже начинаются одинаково. Зачем хранить это начало сто раз? Вот на этой мысли и стоит trie.

Что такое trie одной строкой

Trie (префиксное дерево) — это способ хранить слова так, чтобы общие начала лежали один раз, а слова расходились от них ветками.

Читается как «трай» или «три» — от слова retrieval, «извлечение». Спорят до сих пор, оба варианта в ходу.

Представь слова «про», «прод», «проект» и «пруд». В trie это выглядит так:

п
└─ р
   ├─ о ●            ← «про» заканчивается здесь
   │  ├─ д ●         ← «прод»
   │  └─ е → к → т ● ← «проект»
   └─ у → д ●        ← «пруд»

Каждый узел — одна буква. Точка ● значит «здесь кончается настоящее слово». Буквы «п» и «р» хранятся один раз на все четыре слова.

Как он ищет

Ищем всё на «про». Алгоритм не смотрит на словарь вообще. Он идёт по буквам запроса:

1. Из корня — в ветку «п».
2. Из «п» — в «р».
3. Из «р» — в «о». Пришли.

Три шага, потому что в запросе три буквы. Не важно, сколько в словаре слов — сто или миллион. Шагов столько, сколько ты напечатал.

Дальше дерево под этим узлом и есть ответ: все слова на «про». Обходим его и собираем первые 10. Как только набрали — останавливаемся.

В коде узел — это обычный объект, где ключи — буквы, а значения — следующие узлы:

function insert(root, word) {
  let node = root;
  for (const ch of word) {
    node[ch] ??= {};
    node = node[ch];
  }
  node.end = true;
}

Поиск — тот же цикл, только без создания узлов. Нет нужной буквы — значит, слов с таким началом нет вообще. Ответ «пусто» приходит мгновенно.

Почему это важно тебе

Вот где trie встречается, даже если ты его не писал:

• Автодополнение. Поисковые подсказки, выбор города, теги. Каждый новый символ — один шаг вниз от прошлого узла, а не новый проход по словарю.
• Роутинг в веб-сервере. Fastify ищет, какой код вызвать для /users/42/posts, через радиксное дерево — это сжатый trie. Пути с общим началом /users/ лежат в одной ветке.
• Проверка орфографии и T9 на старых телефонах.
• Интернет-маршрутизаторы. Найти, куда отправить пакет, — это поиск самого длинного совпадающего начала адреса. Классическая задача для префиксного дерева.

И главный вывод для тебя: если в задаче звучит «начинается с…», а слов тысячи и больше — это сигнал. Поиск по префиксу и есть родная работа trie.

Где он проигрывает

Честно: trie — не серебряная пуля.

• Память. Каждая буква — отдельный объект. Дерево легко занимает в несколько раз больше, чем простой список слов. Сжатый вариант — радиксное дерево: цепочку «е → к → т» он хранит одним узлом «ект».
• Только начало. Найти «ект» в середине слова trie не умеет. Для поиска по любому месту и по смыслу нужны другие инструменты — например, семантический поиск.
• Небольшие списки. На 2–3 тысячах слов filter укладывается в доли миллисекунды. Строить дерево там — лишняя сложность. Не трогай то, что не тормозит.

Простое правило: начни с filter. Пожалуйся профайлеру. Если подсказки подвисают на длинном словаре — тогда trie.

Как собрать само поле поиска, с задержкой и подсветкой, — в статье «Как добавить поиск в приложение».

Trie — это то же самое, что дерево?

Это частный случай дерева. Особенность в том, что путь от корня до узла сам и есть ключ — по буквам. Значение не лежит в узле целиком, его «собирают» по дороге.

Чем trie лучше, чем объект с ключами-словами?

Объект { проект: true } мгновенно отвечает «есть ли ровно это слово». Но спросить «какие слова начинаются на „про“» он не может — придётся перебрать все ключи. Trie отвечает на оба вопроса.

Регистр и буква «ё» мешают?

Мешают: для trie «Про», «про» и «прo» с латинской «o» — три разные ветки. Перед вставкой и поиском приводи всё к одному виду: toLowerCase(), «ё» → «е», лишние пробелы прочь.