Что такое Trie?

Префиксное дерево (или trie, от англ. retrieval — «поиск») — это древовидная структура данных, предназначенная для хранения и поиска строк по их символам. Каждое ребро в дереве помечено одним символом, а каждый путь от корня вниз к помеченному узлу образует одно из хранящихся слов.

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

Каждый узел (node) в дереве хранит два элемента состояния:

• children: отображение (map) символа на следующий объект TrieNode.
• isEndOfWord: флаг, который принимает значение true, когда путь от корня к этому узлу образует полное слово, которое было добавлено в дерево.

Пять основных операций над префиксным деревом:

1. Insert: Добавление слова с созданием всех недостающих узлов по пути.
2. Search: Проверка того, сохранено ли в дереве полное слово.
3. StartsWith: Проверка того, начинается ли какое-либо из сохраненных слов с данного префикса.
4. Delete: Удаление слова и очистка всех неиспользуемых ветвей.
5. WordCount: Подсчет количества различных слов, хранящихся в дереве.

Давайте создадим класс Trie!