Алгоритмы на деревьях
2026-02-26 22:53 Diff
https://ru.hexlet.io/courses/algorithms-trees/lessons/prefix/theory_unit

Древовидные структуры можно использовать для хранения и организации, причем не только цельных, но и группируемых данных.

Например, такие данные могут состоять из последовательности одинаковых символов. Рассмотрим в качестве исходной точки несколько слов из толкового словаря:

ОБЕСПЕЧИВАТЬ. Несовершенный вид к «обеспечить»...

ОБЕСПЕЧИТЬ. Совершенный вид к «обеспечивать». Предоставить материальные средства для жизни...

ОБЕСПЕЧИТЬСЯ. Совершенный вид к «обеспечиваться». Запастись, стать обеспеченным...

Как можно видеть из примера, существует несколько слов, которые начинаются на одну и ту же последовательность символов. В нашем случае у слов один и тот же корень, меняются только суффиксы и окончания.

В информатике часть последовательности данных, которая не меняется и находится перед суффиксом, называется префиксной частью.

В этом уроке мы более подробно познакомимся с принципами работы префиксных деревьев, их производными версиями и механизмами работы.

Зачем нужны префиксные деревья

При помощи одинаковых префиксов можно сгруппировать наши слова в следующем виде:

Префиксные деревья специально разработаны, чтобы помогать нам организовывать, хранить и группировать данные в таком виде. Префиксное дерево для нашего примера будут иметь следующий вид:

Префиксные деревья помогают прогнозировать пользовательский ввод — например, предлагая слово, наиболее близкое по составу введенных букв. Так работают системы проверки орфографии или дополнитель кода в среде разработки.

Механизм префиксов нашел свое место и в работе интернет-маршрутизации. Там он помогает эффективно хранить IP-адреса, группируемые по префиксам:

Как устроены префиксные деревья

В качестве примера префиксного дерева рассмотрим хранение слов или некоторых ассоциативных массивов.

Префиксным деревом называется дерево, в котором каждая вершина помечена некоторой буквой и имеет дополнительный признак терминальности. Если мы читаем вершины по порядку, мы получаем последовательность символов, соответствующую некоторому слову.

Если полученная последовательность заканчивается признаком терминальности, то такое слово считается существующим в этой структуре данных.

При этом два узла не могут быть связаны с общим предком с помощью одной и той же буквы.

Операции над деревом

Для начала представим префиксное дерево в виде кода на JavaScript:

С префиксными деревьями можно проводить разные операции, в том числе поиск слов, вставка нового слова и удаление слова. Разберем их подробнее.

Поиск слова в дереве

Для выполнения поиска сперва необходимо обратиться к корневой вершине. Обычно считается, что значение корневой вершины равно пустоте.

Далее мы перемещаемся по указателям, соответствующим каждой следующей букве в искомом слове.

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

Если флаг конца слова присутствует, то поиск считаем завершенным успешно — искомое слово найдено.

Представим теперь эту операцию в виде метода:

Вставка слова

В таком случае операция вcтавки слова в дерево будет выглядеть следующим образом:

Удаление слова

Операция удаления слова принимает следующий вид:

Сжатые префиксные деревья

Это особый подвид префиксных деревьев, заслуживающий отдельного внимания.

В таких деревьях мы сжимаем структуру за счет размещения в вершине не одной буквы, а сразу целого фрагмента префикса. При этом из каждого элемента этого префикса существует строго одна связь с другим элементом префикса.

Такие деревья гораздо удобнее использовать для чтения информации за счет уменьшения количества переходов по ссылкам между вершинами.

Рассмотрим пример такого дерева на рисунке ниже:

А так это дерево выглядит без сжатия:

Как видите, количество переходов между вершинами действительно сокращается. Но важно помнить, что такой способ хранения требует более сложную организацию процедур. При сжатии вставка и удаление слов могут потребовать более неочевидной организации вершин — например, их дополнительного разбиения или объединения.

Сжатые префиксные деревья отлично подходят для хранения данных, которые редко подвергаются изменениям.

Выводы

В этом уроке вы познакомились с классическими и сжатыми префиксными деревьями. Это отличный механизм организации хранения группируемых данных. Такой способ хранения уменьшает объем хранимых данных, помогает предсказывать пользовательский ввод, автоматически исправлять ошибки и организовывать маршрутизацию в вычислительных сетях.