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

Мне нравится дерево имен больше, чем дерево префиксов или цифровое дерево, хотя дерево префиксов является наиболее точным определением. Имя trie происходит от поиска, но произносится как «попытка», а не «дерево». Идея заключалась в том, чтобы отличить дерево от дерева.

Попробуйте угадать, что такое дерево. Я построил дерево из 4 слов: яблоко, банан, ублюдок, бан:

Я настоятельно рекомендую использовать инструмент визуализации из Университета Сан-Франциско, чтобы поиграть с деревом.

Trie компактно хранит ключи, представленные в виде последовательности (обычно строки). Затем вы можете использовать его как набор или хэш-карту для запроса ключей. Кроме того, вы получаете возможность запрашивать ключи и значения по префиксу ключа.

Я не акцентирую внимание на оптимальном алгоритме. Цель этой статьи - познакомить вас с trie и узнать, когда вы можете его использовать.

Создадим желаемый API:

Для понимания идеи достаточно будет реализовать эти две функции: Insert и Contains. И это будет разумным основанием для следующих улучшений.

Я начинаю с реализации общего рунного дерева. В Go руна представляет собой надмножество ASCII и представляет собой кодовые точки Unicode. Думайте об этом как о типе char в Java или C, но для Unicode.

Итак, есть функция Insert без каких-либо оптимизаций, просто первая наивная реализация:

Алгоритм прост:

1. Установите текущее значение узла для корневого узла.
2. Для каждой буквы слова: a) Проверьте, содержит ли текущий узел букву, и, если ее нет, создайте новый узел для буквы и присоедините его к текущему узлу. б) Но если он включает букву, получите узел под этой буквой и установите его как текущий узел. Вернуться к 2.
3. Отметьте последний обработанный узел как конец слова.

Обходим дерево по буквам до последнего узла.

Давайте протестируем эту реализацию. В Go есть инструменты для написания простых тестов производительности, подобных этому:

А затем запускаем тест:

Инструмент Go bench не считает выделение стека, поэтому я вижу, что функция Contains не содержит выделений кучи, и это отлично.

Структура Trie позволяет нам добавить еще одну функцию, которая невозможна для обычной хеш-карты - SearchByPrefix:

Функция не оптимизирована, но показывает, что это возможно и не так сложно. Он вызывает функцию, определенную ранее nodeByPrefix.

Приложения

Автозаполнение

Поскольку дерево позволяет искать слова по префиксу, это хороший кандидат для алгоритмов автозаполнения.

Маршрутизация

Библиотека fasthttp для Go использует trie как внутреннюю реализацию для маршрутизации. Это не только самая быстрая (возможно) реализация маршрутизации, но и не производит мусора.

Если хотите, можете нырнуть глубже .

Другие варианты

Если тебе надо:

1. Набор, в котором может потребоваться поиск по префиксу.
2. Компактно храните множество похожих данных.
3. Вы строите структуру один раз, а затем запрашиваете ее.

Например, вы создаете набор доменов, включая поддомены в памяти при запуске приложения, а затем только запрашиваете его. Вы можете подумать о том, чтобы выполнить эту задачу.

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

Если вам не нужен поиск по префиксу, а ваша структура данных сильно меняется, лучше использовать хэш-карту или хеш-набор.

Известные реализации trie

Я нашел две интересные библиотеки с образцовой реализацией trie:

1. https://github.com/siongui/go-succinct-data-structure-trie
2. https://github.com/celzero/gotrie

Первоначально опубликовано на https://scalabledeveloper.com .