Тернарное дерево поиска
 | Эта статья требует внимания эксперта в области вычислительной техники . Конкретная проблема такова: «Отсутствует описание нескольких, но в данном случае очень важных операций. Отсутствует псевдокод всех операций (включая только что упомянутые недостающие). Псевдокод значительно улучшает понимание операций. Отсутствует строгий математический анализ сложности времени выполнения.". ( сентябрь 2016 г. ) |
| Троичное дерево поиска (TST) | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | дерево | ||||||||||||||||||||
| |||||||||||||||||||||
В информатике троичное дерево поиска — это тип дерева (иногда называемого префиксным деревом ), в котором узлы расположены аналогично двоичному дереву поиска , но с количеством дочерних элементов до трех, а не с ограничением двоичного дерева в два. Как и другие префиксные деревья, троичное дерево поиска может использоваться как ассоциативная структура карты с возможностью инкрементального строкового поиска . Однако троичные деревья поиска более экономичны по сравнению со стандартными префиксными деревьями за счет скорости. Общие приложения для троичных деревьев поиска включают проверку орфографии и автозаполнение .
Описание [ править ]
Каждый узел троичного дерева поиска хранит один символ , объект (или указатель на объект в зависимости от реализации) и указатели на его трех дочерних элементов, условно называемых равными kid , lo kid и hi kid , которые также могут называться соответственно как средний (ребенок) , низший (ребенок) и высший (ребенок) . [1] Узел также может иметь указатель на свой родительский узел, а также индикатор того, отмечает ли этот узел конец слова. [2] Указатель lo kid должен указывать на узел, значение символа которого меньше текущего узла . Указатель hi kid должен указывать на узел, символ которого больше, чем текущий узел . [1] Равный малыш указывает на следующий символ в слове. На рисунке ниже показано троичное дерево поиска со строками «cute», «cup», «at», «as», «he», «us» и «i»:
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s
Как и в других структурах данных дерева, каждый узел в троичном дереве поиска представляет собой префикс сохраненных строк. Все строки в среднем поддереве узла начинаются с этого префикса.
Операции [ править ]
Вставка [ править ]
Вставка значения в троичный поиск может быть определена рекурсивно или итеративно, так же, как определяются поисковые запросы. Этот рекурсивный метод постоянно вызывается для узлов дерева, имеющих ключ, который становится все короче за счет обрезки символов в передней части ключа. Если этот метод достигает узла, который еще не был создан, он создает узел и присваивает ему значение первого символа ключа. Независимо от того, создан новый узел или нет, метод проверяет, больше или меньше первый символ в строке, чем значение символа в узле, и выполняет рекурсивный вызов соответствующего узла, как и в операции поиска. Однако если первый символ ключа равен значению узла, то для равного ребенка вызывается процедура вставки, и первый символ ключа отсекается. [1] Подобно двоичным деревьям поиска и другим структурам данных , троичные деревья поиска могут вырождаться в зависимости от порядка ключей. [3] [ самостоятельный источник? ] Вставка ключей в алфавитном порядке — один из способов получить наихудшее вырожденное дерево. [1] Вставка ключей в случайном порядке часто дает хорошо сбалансированное дерево. [1]
function insertion(string key) is
node p := root
//initialized to be equal in case root is null
node last := root
int idx := 0
while p is not null do
//recurse on proper subtree
if key[idx] < p.splitchar then
last := p
p := p.left
else if key[idx] > p.splitchar then
last := p
p := p.right
else:
// key is already in our Tree
if idx == length(key) then
return
//trim character from our key
idx := idx+1
last := p
p := p.mid
p := node()
//add p in as a child of the last non-null node (or root if root is null)
if root == null then
root := p
else if last.splitchar < key[idx] then
last.right := p
else if last.splitchar > key[idx] then
last.left := p
else
last.mid := p
p.splitchar := key[idx]
idx := idx+1
// Insert remainder of key
while idx < length(key) do
p.mid := node()
p.mid.splitchar := key[idx]
idx += 1
Поиск [ править ]
Чтобы найти конкретный узел или данные, связанные с узлом, необходим строковый ключ. Процедура поиска начинается с проверки корневого узла дерева и определения того, какое из следующих условий произошло. Если первый символ строки меньше символа в корневом узле, можно вызвать рекурсивный поиск в дереве, корень которого является lo kid текущего корня. Аналогично, если первый символ больше текущего узла в дереве, то можно выполнить рекурсивный вызов дерева, корнем которого является верхний предел текущего узла. [1] И наконец, если первый символ строки равен символу текущего узла, функция возвращает узел, если в ключе больше нет символов. Если в ключе больше символов, то первый символ ключа необходимо удалить и выполнить рекурсивный вызов с учетом равного дочернего узла и измененного ключа. [1] Это также можно записать нерекурсивным способом, используя указатель на текущий узел и указатель на текущий символ ключа. [1]
Псевдокод [ править ]
function search(string query) is
if is_empty(query) then
return false
node p := root
int idx := 0
while p is not null do
if query[idx] < p.splitchar then
p := p.left
else if query[idx] > p.splitchar then
p := p.right;
else
if idx = length(query) then
return true
idx := idx + 1
p := p.mid
return false
Удаление [ править ]
Операция удаления состоит из поиска ключевой строки в дереве поиска и поиска узла, называемого firstMid в приведенном ниже псевдокоде, такого, что на пути от среднего дочернего элемента firstMid до конца пути поиска ключевой строки не остается или правильные дети. Это будет представлять собой уникальный суффикс в троичном дереве, соответствующий ключевой строке. Если такого пути нет, это означает, что ключевая строка либо полностью содержится в качестве префикса другой строки, либо отсутствует в дереве поиска. Во многих реализациях используется символ конца строки, чтобы гарантировать возникновение только последнего случая. Затем путь удаляется от firstMid.mid до конца пути поиска. В случае, когда firstMid является корнем, ключевая строка должна быть последней строкой в дереве, и, таким образом, после удаления корень устанавливается в нулевое значение.
function delete(string key) is
if is_empty(key) then
return
node p := root
int idx := 0
node firstMid := null
while p is not null do
if key[idx] < p.splitchar then
firstMid := null
p := p.left
else if key[idx] > p.splitchar then
firstMid := null
p := p.right
else
firstMid := p
while p is not null and key[idx] == p.splitchar do
idx := idx + 1
p := p.mid
if firstMid == null then
return // No unique string suffix
// At this point, firstMid points to the node before the strings unique suffix occurs
node q := firstMid.mid
node p := q
firstMid.mid := null // disconnect suffix from tree
while q is not null do //walk down suffix path and delete nodes
p := q
q := q.mid
delete(p) // free memory associated with node p
if firstMid == root then
delete(root) //delete the entire tree
root := null
Обход [ править ]
[ нужны разъяснения ] [ нужен пример ]
Поиск с частичным совпадением [ править ]
[ нужны разъяснения ] [ нужен пример ]
Поиск ближайших соседей [ править ]
[ нужны разъяснения ] [ нужен пример ]
Время работы [ править ]
Время работы троичных деревьев поиска значительно зависит от входных данных. Тернарные деревья поиска работают лучше всего, если задано несколько похожих строк , особенно если эти строки имеют общий префикс . Альтернативно, троичные деревья поиска эффективны при хранении большого количества относительно коротких строк (например, слов в словаре ). [1] Время выполнения троичных деревьев поиска аналогично двоичным деревьям поиска , поскольку они обычно выполняются за логарифмическое время, но в вырожденном (наихудшем) случае могут работать и за линейное время. Кроме того, при рассмотрении времени выполнения необходимо учитывать размер строк. Например, в пути поиска строки длины k будет k обходов по средним дочерним элементам в дереве, а также логарифмическое количество обходов по левому и правому дочернему элементу в дереве. Таким образом, в троичном дереве поиска с небольшим количеством очень больших строк длина строк может доминировать во время выполнения. [4]
Временные сложности для операций с троичным деревом поиска: [1]
| Среднее время работы | Худшее время работы | |
|---|---|---|
| Искать | О (логарифм n + k ) | О ( п + к ) |
| Вставка | О (логарифм n + k ) | О ( п + к ) |
| Удалить | О (логарифм n + k ) | О ( п + к ) |
Сравнение с другими структурами данных [ править ]
Пытается [ править ]
Несмотря на то, что троичные деревья поиска медленнее других префиксных деревьев , они могут лучше подходить для больших наборов данных из-за их эффективности использования пространства. [1]
Хэш-карты [ править ]
Хэш-таблицы также можно использовать вместо троичных деревьев поиска для сопоставления строк со значениями. Однако хеш-карты также часто используют больше памяти, чем троичные деревья поиска (но не так много, как попытки). Кроме того, хеш-карты обычно медленнее сообщают о строке, которая не находится в той же структуре данных, поскольку они должны сравнивать всю строку, а не только первые несколько символов. Есть некоторые свидетельства того, что троичные деревья поиска работают быстрее, чем хеш-карты. [1] Кроме того, хеш-карты не позволяют использовать многие виды использования троичных деревьев поиска, например поиск ближайших соседей .
DAFSA ( детерминированный ациклический конечный автомат ) [ править ]
Если хранение словарных слов — это все, что требуется (т. е. не требуется хранение вспомогательной информации для каждого слова), минимальный детерминированный ациклический конечный автомат (DAFSA) будет использовать меньше места, чем дерево или троичное дерево поиска. Это связано с тем, что DAFSA может сжимать идентичные ветви дерева, которые соответствуют одним и тем же суффиксам (или частям) разных сохраняемых слов.
Использует [ править ]
Тернарные деревья поиска можно использовать для решения многих задач, в которых необходимо хранить и извлекать большое количество строк в произвольном порядке. Некоторые из наиболее распространенных и полезных из них приведены ниже:
- В любое время можно использовать дерево , но предпочтительна структура с меньшим потреблением памяти. [1]
- Быстрая и компактная структура данных для сопоставления строк с другими данными. [3]
- Чтобы реализовать автозаполнение . [2] [ самостоятельный источник? ]
- В качестве проверки правописания . [5]
- Поиск ближайшего соседа (особым случаем которого является проверка орфографии). [1]
- В качестве базы данных, особенно когда желательна индексация по нескольким неключевым полям. [5]
- Вместо хеш-таблицы . [5]
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и ж г час я дж к л м н «Тройные деревья поиска» . Доктор Добб .
- ^ Jump up to: Перейти обратно: а б Островский, Игорь. «Эффективное автозаполнение с помощью троичного дерева поиска» .
- ^ Jump up to: Перейти обратно: а б Врубель, Лукаш. «Тройное дерево поиска» .
- ^ Бентли, Джон; Седжвик, Боб. «Тройное дерево поиска» .
- ^ Jump up to: Перейти обратно: а б с Флинт, Уолли (16 февраля 2001 г.). «Поместите свои данные в троичное дерево поиска» . JavaWorld . Проверено 19 июля 2020 г.
Внешние ссылки [ править ]
- Страница троичных деревьев поиска со статьями (Джона Бентли и Роберта Седжвика) о троичных деревьях поиска и алгоритмах «сортировки и поиска строк».
- Троичные попытки поиска – видео Роберта Седжвика
- TST.java.html Реализация TST на Java Роберта Седжвика и Кевина Уэйна