Trie — это дерево, подобное структуре данных. Он также известен как префиксное дерево. Он используется для хранения строк или путей, и, используя эти пути, он создает структуру данных, так что мы можем очень эффективно искать, вставлять и удалять из этой структуры данных. Trie просматривается в глубину (это алгоритм обхода структуры данных дерева или графа. Он начинается с корневого узла и исследует каждый узел).
У каждого Trie есть пустой узел со ссылками на другие узлы. Структура всегда похожа на связанный узел, который соединяется с пустым узлом.
Понимание этого на примере -
Возьмем несколько строк — qqrs, ppqq, prqs, sstp, prqs.
И мы хотим сопоставить Key String — sstp
Что бы мы сделали?
Нам нужно будет просмотреть каждую из строк, а затем мы сопоставим каждый символ из списка строк с символами ключевой строки.
Это потребует временной сложности O (длина каждой строки * общее количество строк), что очень дорого :(
Теперь попытка поможет нам уменьшить эту временную сложность. Посмотрим, как.
Во-первых, мы попробуем реализовать trie —
Таким образом, мы создали словарь. Когда мы получаем набор слов, мы можем либо создать для него структуру, либо проверить, существует ли уже эта структура, и не создавать аналогичную структуру снова.
Подсчет частоты любой заданной строки
Частоту каждой строки можно увидеть на конечном узле. Частота для строки pqrs равна 2, потому что это произошло дважды в нашем словаре.
мы делаем проверку в каждом узле, заканчивается ли строка в каком-либо заданном узле или нет. Если да, то мы увеличиваем счетчик частоты для этой строки на 1.
Поиск слова
Поиск любого слова с помощью trie на самом деле довольно прост. Берем слово, которое хотим найти, возьмем «sstp» из нашего словаря. Теперь мы проверим прямо из корня, есть ли у нас какой-либо узел со значением «s»? если да, мы переходим к следующему узлу, соответствующему «s», и проверяем, есть ли у нас «s»? если да, снова мы проверяем следующее на «t», а затем на «p». Итак, мы просто пошли по пути и получили слово, которое искали.
Удаление слова
Операция удаления здесь происходит снизу вверх. Сначала мы удаляем последний узел, скажем, n, затем (n-1), (n-1),.. и так далее, пока не достигнем 1-го узла любого заданного слова. Давайте поймем это более четко с помощью этого графического изображения.
Каким может быть максимальное количество дочерних узлов в дереве?
Представьте, что мое дерево содержит только алфавиты, поэтому я могу сказать, что максимальное количество дочерних узлов может достигать 26. Если в моем дереве есть маленькие алфавиты, а также числа, я могу сказать, что оно достигает 26 для алфавитов и 0–9 для чисел. Поэтому можно с уверенностью сказать, что размер дерева прямо пропорционален размеру всех возможных значений, которые может представлять это дерево.
Большие нотации О
Временная сложность вставки, поиска и удаления из дерева зависит от длины слова и общего количества слов. Его можно назвать O(l*w).
Спасибо за прочтение !
