Трие дерево
Название Трие происходит от слова «поиск», поиск, потому что Трие может найти нужное слово в словаре с помощью всего лишь префикса.
Хотя произношение соответствует «Tree», чтобы отличить это словарное дерево от обычного двоичного дерева, программист Сяо Ву обычно перечитывает конец «Trie», что можно понять как чтение «TreeE».
Дерево Trie, также называемое «словарным деревом». Как следует из названия, этодревовидная структура. Это структура данных, специально предназначенная для сопоставления строк, которая используется для решения проблемы быстрого поиска определенной строки в наборе строк.
Кроме того, дерево Trie также называют деревом префиксов (поскольку потомки узла имеют общий префикс, например, pan — это префикс панды).
Его ключи - все строки, которые могут выполнять эффективный запрос и вставку.Временная сложность O(k), а k - длина строки.Недостаток в том, что если большое количество строк не имеет общего префикса, это потребляет много памяти.
Его основная идея состоит в том, чтобы сделать запросы эффективными, сведя к минимуму ненужные сравнения строк, то есть «обменив пространство на время», а затем используя общие префиксы для повышения эффективности запросов.
Особенности Trie Trees
Предположим, что есть пять строк: код, повар, пять, файл, жир. Теперь нужно узнать, существует ли строка несколько раз. Если каждый взгляд берет строку, которую вы ищете, с этими пятью строками, совпадающими по очереди, эта эффективность относительно низка, нет ли более эффективного способа сделать это?
Если они организованы на пять строк под картой структуры, сканирование от невооруженного глаза в прошлом не то, что чувства будут быстрее, чем их.
Из приведенного выше рисунка мы можем найти три характеристики дерева Trie:
- Корневой узел не содержит символов, и каждый узел, кроме корневого узла, содержит только один символ.
- От корневого узла к узлу символы, проходящие по пути, соединяются, чтобы сформировать строку, соответствующую узлу.
- Все дочерние узлы каждого узла содержат разные символы
Поймите процесс построения дерева Trie с помощью анимации. Каждый шаг в процессе построения эквивалентен вставке строки в дерево Trie. Когда все строки вставлены, строится дерево Trie.
Операция вставки дерева Trie
Операция вставки дерева Trie очень проста, фактически каждая буква слова вставляется в дерево Trie одна за другой. Перед вставкой проверьте, существует ли узел, соответствующий букве, если он есть, поделитесь узлом, если нет, создайте соответствующий узел. например, вставка новых словcook, есть следующие шаги:
- вставить первую букву
c,НаходитьrootНиже узла есть дочерние узлыc, то общий узелc - Вставка второй буквы
o,НаходитьcНиже узла есть дочерние узлыo, то общий узелo - вставить третью букву
o,НаходитьoНиже узла нет дочерних узловo, затем создайте дочерний узелo - вставить третью букву
k,НаходитьoНиже узла нет дочерних узловk, затем создайте дочерний узелk - До сих пор слово
cookВсе буквы были вставлены в дерево Trie, затем установите узелkбиты флага, обозначающие путьroot->c->o->o->kСимволы всех узлов на этом пути могут составить словоcook
Операция запроса дерева Trie
При поиске строки в дереве Trie, например при поиске строкиcode, вы можете разбить искомую строку на отдельные символы c, o, d, e, а затем начать сопоставление с корневого узла дерева Trie. Как показано на рисунке, зеленый путь — это путь, соответствующий дереву Trie.
Если вы ищете строкуcod(Треска) О чем? Вы все еще можете использовать тот же метод, что и выше, начиная с корневого узла и сопоставляя определенный путь, как показано на рисунке, зеленый путь - это строкаcodсоответствующий путь. Однако последний узел "d" пути не оранжевый и не является флагом слова, поэтомуcodСтрока не существует. Это,codЭто префикс подстроки строки, но она не полностью совпадает с любой строкой.
Программисты не должны быть соленой рыбой, они должны
cookподойди поближе :)
Операция удаления дерева Trie
Операция удаления дерева trie аналогична операции удаления двоичного дерева. Необходимо учитывать расположение удаленного узла. Вот три ситуации для анализа:
удалить целые слова (например,hi)
- Найдите первый символ, начиная с корневого узла
h - оказаться
hПосле дочернего узла продолжайте поискhследующий дочерний узелi -
iэто словоhiбит флага, удалите бит флага -
iузелhi, удали это - найдено после удаления
hУзел является листовым узлом и не является флагом слова, он также удаляется. - Готово
hiудаление слов
удалить префиксные слова (например,cod)
codПосле поиска всей строки слов,dПоскольку узел не является конечным узлом, просто удалите его словесный знак.
удалить слова ответвления (например,cook)
cookпервоеo, узел является нелистовым узлом, остановить удаление, и это делаетсяcookОперация удаления строки.
Применение Trie Trees
На самом деле деревья Trie используются повсеместно в повседневной жизни, например:
В частности, он часто используется для статистики и сортировать большое количество строк (но не ограничено строками), поэтому они часто используются системами поисковой системы для статистики частоты текстовых слов. Его преимущество заключается в том, что минимизируют ненужные строковые сравнения, эффективность запроса выше, чем хэш-таблица.
1. Сопоставление префикса
Например: найти все строки, начинающиеся с五分钟строка для начала. Нам просто нужно построить дерево со всеми строками, а затем вывести ключевые слова на пути, начинающемся с пяти->минут->минут.
Сопоставление префикса Trie часто используется для поисковых подсказок. Например, при вводе веб-адреса может автоматически выполняться поиск возможных вариантов. Если нет точно совпадающих результатов поиска, может быть возвращен максимально похожий префикс.
2. Поиск строки
Имея список знакомой лексики, состоящий из N слов, и статью, полностью написанную строчными буквами английского языка, запишите все новые слова, которых нет в списке знакомой лексики, в порядке их появления.
Функция поиска/запроса — самая примитивная функция дерева Trie. Учитывая набор строк, чтобы определить, появлялась ли строка раньше, идея состоит в том, чтобы сравнивать символы один за другим, начиная с корневого узла:
- Если вы попутно сравните и обнаружите разные символы, значит, строки в наборе нет.
- Если сравниваются все символы и все они одинаковы, также необходимо оценить бит флага последнего узла (отмечая, представляет ли узел ключевое слово).
Ограничения деревьев проб
Как упоминалось выше, основная идея Trie заключается в обмене пространства на время и использовании общего префикса строк для сокращения накладных расходов времени запроса для достижения цели повышения эффективности.
Предположим, что количество символов равноmСуществует несколько строк длины n, образующих дерево Trie, тогда исходящая степень каждого узла равнаm(Т.е. количество возможных дочерних узлов на узел равноm), высота дерева Trie равнаn. Очевидно, что мы тратим много места на хранение символов, и наихудшая пространственная сложность дерева Trie в настоящее время — этоO(m^n). Это также связано с тем, что исходящая степень каждого узлаm, поэтому мы можем эффективно запрашивать символ за символом по каждой ветви дерева вместо обхода всех строк для запроса. В настоящее время наихудшая временная сложность дерева Trie составляетO(n).
Это воплощение изменения пространства во времени и использования общих префиксов для сокращения времени запроса.