В информатике троичное дерево поиска — это тип trie (иногда называемый префиксным деревом ), в котором узлы организованы аналогично бинарному дереву поиска , но с количеством дочерних элементов до трех, а не ограничением бинарного дерева в два. Как и другие префиксные деревья, троичное дерево поиска может использоваться в качестве ассоциативной структуры карты с возможностью инкрементного поиска по строкам . Однако троичные деревья поиска более эффективны с точки зрения пространства по сравнению со стандартными префиксными деревьями за счет скорости. Распространенные приложения для троичных деревьев поиска включают проверку орфографии и автодополнение .
Каждый узел троичного дерева поиска хранит один символ , объект (или указатель на объект в зависимости от реализации) и указатели на три его дочерних элемента, условно называемых equal kid , lo kid и hi kid , которые также могут называться middle (child) , lower (child) и higher (child) соответственно . [1] Узел также может иметь указатель на свой родительский узел, а также индикатор того, отмечает ли узел конец слова или нет. [2] Указатель lo kid должен указывать на узел, значение символа которого меньше текущего узла . Указатель hi kid должен указывать на узел, значение символа которого больше текущего узла . [1] equal kid указывает на следующий символ в слове. На рисунке ниже показано троичное дерево поиска со строками "cute","cup","at","as","he","us" и "i":
с / | \ ааа | | | \ ттеу / / | / | спейс
Как и в других структурах данных trie, каждый узел в тернарном дереве поиска представляет собой префикс хранимых строк. Все строки в среднем поддереве узла начинаются с этого префикса.
Вставка значения в тернарный поиск может быть определена рекурсивно или итеративно, так же как определяются подстановки. Этот рекурсивный метод непрерывно вызывается для узлов дерева, заданного ключом, который становится все короче за счет обрезки символов с передней части ключа. Если этот метод достигает узла, который не был создан, он создает узел и присваивает ему символьное значение первого символа в ключе. Независимо от того, создан новый узел или нет, метод проверяет, больше или меньше первый символ в строке, чем символьное значение в узле, и выполняет рекурсивный вызов для соответствующего узла, как в операции поиска. Однако, если первый символ ключа равен значению узла, то процедура вставки вызывается для равного ребенка, и первый символ ключа отсекается. [1] Подобно двоичным деревьям поиска и другим структурам данных , тернарные деревья поиска могут стать вырожденными в зависимости от порядка ключей. [3] [ самостоятельно опубликованный источник? ] Вставка ключей в алфавитном порядке — один из способов получить наихудшее возможное вырожденное дерево. [1] Вставка ключей в случайном порядке часто приводит к хорошо сбалансированному дереву. [1]
function insertion ( string key ) is node p := root // инициализируется как равный в случае, если root равен null node last := root int idx := 0 while p is not null do // рекурсия по соответствующему поддереву 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 уже есть в нашем дереве if idx == length ( key ) then return // обрезаем символ из нашего ключа idx := idx + 1 last := p p := p . mid p := node () // добавляем p в качестве дочернего элемента последнего ненулевого узла (или корня, если root равен 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 // Вставить остаток ключа while idx < length ( key ) do p . mid := node () p . mid . splitchar := key [ idx ] idx += 1 Для поиска определенного узла или данных, связанных с узлом, необходим строковый ключ. Процедура поиска начинается с проверки корневого узла дерева и определения того, какое из следующих условий имело место. Если первый символ строки меньше символа в корневом узле, рекурсивный поиск может быть вызван для дерева, корень которого является младшим узлом текущего корня. Аналогично, если первый символ больше текущего узла в дереве, то рекурсивный вызов может быть выполнен для дерева, корень которого является старшим узлом текущего узла. [1] В последнем случае, если первый символ строки равен символу текущего узла, то функция возвращает узел, если в ключе больше нет символов. Если в ключе больше символов, то первый символ ключа должен быть удален, и выполняется рекурсивный вызов с учетом равного младшего узла и измененного ключа. [1] Это также можно записать нерекурсивным способом, используя указатель на текущий узел и указатель на текущий символ ключа. [1]
функция поиска ( строка запроса ) is if is_empty ( запрос ) 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 ( запрос ) then return true idx := idx + 1 p := p . mid return false Операция удаления состоит из поиска ключевой строки в дереве поиска и нахождения узла, называемого firstMid в приведенном ниже псевдокоде, такого, что путь от среднего дочернего элемента firstMid до конца пути поиска ключевой строки не имеет левых или правых дочерних элементов. Это будет представлять собой уникальный суффикс в троичном дереве, соответствующем ключевой строке. Если такого пути нет, это означает, что ключевая строка либо полностью содержится как префикс другой строки, либо отсутствует в дереве поиска. Во многих реализациях используется символ конца строки, чтобы гарантировать возникновение только последнего случая. Затем путь удаляется от firstMid.mid до конца пути поиска. В случае, если firstMid является корнем, ключевая строка должна была быть последней строкой в дереве, и, таким образом, корень устанавливается в значение null после удаления.
функция delete ( string key ) если is_empty ( key ) то возвращает узел 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 // Уникального суффикса строки нет // В этот момент firstMid указывает на узел до появления уникального суффикса строки node q := firstMid . mid node p := q firstMid . mid := null // отсоединить суффикс от дерева , пока q не равно null do // пройти по пути суффикса и удалить узлы p := q q := q . mid delete ( p ) // освободить память, связанную с узлом p if firstMid == root then delete ( root ) // удалить все дерево root := null [ необходимо разъяснение ] [ необходим пример ]
[ необходимо разъяснение ] [ необходим пример ]
[ необходимо разъяснение ] [ необходим пример ]
Время выполнения троичных деревьев поиска значительно варьируется в зависимости от входных данных. Троичные деревья поиска работают лучше всего, когда задано несколько похожих строк , особенно когда эти строки имеют общий префикс . С другой стороны, троичные деревья поиска эффективны при хранении большого количества относительно коротких строк (например, слов в словаре ). [1] Время выполнения троичных деревьев поиска похоже на время выполнения бинарных деревьев поиска , в том смысле, что они обычно работают за логарифмическое время, но могут работать за линейное время в вырожденном (худшем) случае. Кроме того, размер строк также должен учитываться при рассмотрении времени выполнения. Например, в пути поиска для строки длины k будет k обходов вниз по средним потомкам в дереве, а также логарифмическое число обходов вниз по левым и правым потомкам в дереве. Таким образом, в троичном дереве поиска на небольшом количестве очень больших строк длины строк могут доминировать над временем выполнения. [4]
Временные сложности для операций троичного дерева поиска: [1]
Хотя троичные деревья поиска медленнее других префиксных деревьев , они могут лучше подходить для больших наборов данных из-за их эффективности использования пространства. [1]
Хеш-таблицы также можно использовать вместо троичных деревьев поиска для сопоставления строк со значениями. Однако хеш-карты также часто используют больше памяти, чем троичные деревья поиска (но не так много, как попытки). Кроме того, хеш-карты обычно медленнее сообщают о строке, которая не находится в той же структуре данных, поскольку им приходится сравнивать всю строку, а не только первые несколько символов. Есть некоторые свидетельства того, что троичные деревья поиска работают быстрее, чем хеш-карты. [1] Кроме того, хеш-карты не позволяют использовать многие из видов использования троичных деревьев поиска, такие как поиск по соседним элементам .
Если хранение слов словаря — это все, что требуется (т. е. хранение вспомогательной информации для каждого слова не требуется), минимальный детерминированный ациклический конечный автомат (DAFSA) будет использовать меньше места, чем trie или тернарное дерево поиска. Это связано с тем, что DAFSA может сжимать идентичные ветви из trie, которые соответствуют тем же суффиксам (или частям) разных сохраняемых слов.
Тернарные деревья поиска могут использоваться для решения многих задач, в которых большое количество строк должно храниться и извлекаться в произвольном порядке. Некоторые из наиболее распространенных или наиболее полезных из них приведены ниже: