Тернарное дерево поиска

Троичное дерево поиска (TST)
Троичное дерево поиска (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 Роберта Седжвика и Кевина Уэйна

[dobbs-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н «Тройные деревья поиска» . Доктор Добб .

[ostrov-2] Jump up to: ^а ^б Островский, Игорь. «Эффективное автозаполнение с помощью троичного дерева поиска» .

[wrobel-3] Jump up to: ^а ^б Врубель, Лукаш. «Тройное дерево поиска» .

[sedgewick-4] Бентли, Джон; Седжвик, Боб. «Тройное дерево поиска» .

[wally-5] Jump up to: ^а ^б ^с Флинт, Уолли (16 февраля 2001 г.). «Поместите свои данные в троичное дерево поиска» . JavaWorld . Проверено 19 июля 2020 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

v т и Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v т и Струны
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations