pattern heroPT–23LeetCode Extension

Префиксное дерево (trie)

Храним слова деревом из букв: слова с общим началом идут по общему пути. Поиск слова или начала слова занимает столько шагов, сколько в нём букв, сколько бы слов ни было в словаре.

Вариант
P17 Префиксное дерево (trie)Вставка и поиск · 1×

Пример задачи: вставить слова «sun», «sum», «so», затем узнать, есть ли слово «su», начинается ли какое-нибудь слово с «su» и с «b».

rootinsert("sun")sun
в дереве; двойное кольцо — конец словатолько что добавленпройденный путьтекущий узелнайденонет такой буквы

Вставляем «sun»: начинаем с корня

word = "sun"ch = –node = rootisPrefix = –
01/58
сначала · назад · пуск · шаг
Скорость
1function insert(word):
2 node = root
3 for each ch in word:
4 if ch not in node.children:
5 node.children[ch] = new node
6 node = node.children[ch]
7 node.end = true
8function search(word, isPrefix):
9 node = root
10 for each ch in word:
11 if ch not in node.children:
12 return false
13 node = node.children[ch]
14 return isPrefix or node.end

← → шаг · пробел — пауза

Как узнать

много слов и вопросы про их начала: есть ли слово или префикс, автодополнение, слово с буквами-джокерами или поиск многих слов в одной сетке.

Как решать такие задачи

  1. Заведи узел: потомки по буквам (словарь или массив из 26) и флаг конца слова.
  2. Вставка: иди от корня, добавляй недостающего потомка для каждой буквы, последний узел отметь как конец.
  3. Поиск: иди так же и останавливайся на отсутствующей букве. Слову нужна отметка конца, префиксу — нет.
  4. Если в сетке нужно найти много слов, иди по дереву и по сетке вместе: любой префикс, который никуда не ведёт, сразу обрывает поиск.

Вариант: Поиск с «.»

То же, но в шаблоне есть «.», которая означает любую букву. Обычная буква ведёт в одну ветку, а точка — во все, поэтому на точке пробуем каждую ветку по очереди.

  1. Напиши match(node, i): подходит ли остаток шаблона начиная с i к чему-то под этим узлом?
  2. База: когда шаблон кончился, на узле должна стоять отметка конца слова.
  3. Обычная буква: иди в этого потомка или верни false, если его нет.
  4. Джокер: вызови match для каждого потомка и верни true, как только кто-то из них вернёт true.

Где встречается

  • Маршрутизация. Ядро Linux решает, куда отправить пакет, по префиксному дереву IP-адресов (fib_trie): идёт по битам адреса и находит самый длинный подходящий префикс.
  • Веб-фреймворки. Роутеры httprouter и Gin на Go хранят адреса страниц вроде /users/:id в префиксном дереве, поэтому нужный обработчик находится за длину адреса, сколько бы маршрутов ни было.
  • Redis. Redis хранит потоки (Streams) в сжатом префиксном дереве rax.