Введение

Структура данных

В информатике, радикс-дерево (также радикс-три или компактное префиксное дерево, или сжатый три) — это структура данных, представляющая собой три (префиксное дерево), оптимизированное по занимаемому месту, в котором каждый узел, являющийся единственным потомком, объединяется со своим родителем. В результате количество потомков каждого внутреннего узла не превышает радикс r радикс-дерева, где r = 2x для некоторого целого числа x ≥ 1. В отличие от обычных деревьев, рёбра могут быть помечены последовательностями элементов, а не только отдельными элементами. Это делает радикс-деревья гораздо более эффективными для небольших наборов данных (особенно если строки длинные) и для наборов строк, имеющих длинные общие префиксы. В отличие от обычных деревьев (где целые ключи сравниваются целиком, от начала до точки расхождения), ключ в каждом узле сравнивается по частям (блоками) битов, причём размер блока битов в данном узле равен радиксу r радикс-три. Когда r = 2, радикс-три является двоичным (то есть сравнивается 1-битная часть ключа данного узла), что минимизирует разреженность за счёт увеличения глубины три. Когда r ≥ 4 является степенью 2, радикс-три является r-ичным, что уменьшает глубину радикс-три за счёт возможной разреженности. В качестве оптимизации метки рёбер могут храниться в фиксированном объёме памяти, используя два указателя на строку (для первого и последнего элементов). Следует отметить, что хотя в примерах в этой статье строки представлены как последовательности символов, тип элементов строки может быть выбран произвольно; например, это может быть бит или байт строкового представления при использовании многобайтовых кодировок символов или Unicode.

Приложения

Деревья радикалов полезны для построения ассоциативных массивов с ключами, которые можно представить в виде строк. Они находят особое применение в области IP-маршрутизации, где возможность компактного хранения больших диапазонов значений с небольшим количеством исключений особенно хорошо подходит для иерархической организации IP-адресов. Они также используются для создания инвертированных индексов текстовых документов в задачах информационного поиска.

Операции

Радикс-деревья поддерживают операции вставки, удаления и поиска. Вставка добавляет новую строку в радикс-дерево, стремясь минимизировать объем хранимых данных. Удаление удаляет строку из радикс-дерева. Операции поиска включают (но не ограничиваются) точный поиск, поиск предшествующего элемента, поиск следующего элемента и поиск всех строк с заданным префиксом. Все эти операции имеют сложность O(k), где k — максимальная длина всех строк в наборе, а длина измеряется в количестве битов, равном радиксу радикс-дерева.

Вставка

Чтобы вставить строку, мы осуществляем поиск в дереве до тех пор, пока не сможем продвинуться дальше. В этот момент мы либо добавляем новый исходящий ребро, помеченный всеми оставшимися символами входной строки, либо, если уже существует исходящее ребро, имеющее общий префикс с оставшейся частью входной строки, мы разделяем его на два ребра (первое помечено общим префиксом) и продолжаем. Этот шаг разделения гарантирует, что ни у одного узла не будет больше дочерних ребер, чем возможных символов в строке. Ниже показаны несколько примеров вставки, хотя их может быть и больше. Обратите внимание, что `r` просто обозначает корень. Предполагается, что ребра могут быть помечены пустыми строками для завершения строк, где это необходимо, и что у корня нет входящих ребер. (Алгоритм поиска, описанный выше, не будет работать при использовании ребер с пустой строкой).

Удаление

Чтобы удалить строку x из дерева, мы сначала находим лист, представляющий x. Затем, если x существует, мы удаляем соответствующий листовой узел. Если у родительского узла этого листа есть только один другой потомок, то входящая метка этого потомка добавляется к входящей метке родителя, и этот потомок удаляется.

Дополнительные операции

Найти все строки с общим префиксом: возвращает массив строк, начинающихся с одного и того же префикса. Найти предшественника: определяет наибольшую строку, которая меньше заданной в лексикографическом порядке. Найти преемника: определяет наименьшую строку, которая больше заданной в лексикографическом порядке.

История

Структура данных была изобретена в 1968 году Дональдом Р. Моррисоном, с которым она наиболее тесно связана, и Гернотом Гвенбергером. Дональд Кнут в томе III "Искусства компьютерного программирования" на страницах 498–500 называет их "деревьями Патриции", вероятно, по аналогии с акронимом в названии статьи Моррисона: "PATRICIA – Практический алгоритм поиска информации, закодированной в буквенно-цифровом виде". В настоящее время деревья Патриции рассматриваются как radix-деревья с радиксом, равным 2, что означает, что каждый бит ключа сравнивается по отдельности, и каждый узел представляет собой двухнаправленную (то есть, левую или правую) ветвь.

Сравнение с другими структурами данных

(В следующих сравнениях предполагается, что ключи имеют длину k и структура данных содержит n элементов.) В отличие от сбалансированных деревьев, radix-деревья (или префиксные деревья) позволяют выполнять поиск, вставку и удаление за время O(k) вместо O(log n). Это может не показаться преимуществом, поскольку обычно k ≥ log n, но в сбалансированном дереве каждое сравнение – это сравнение строк, требующее O(k) времени в худшем случае, и многие из них медленны на практике из-за длинных общих префиксов (особенно когда сравнения начинаются с начала строки). В trie все сравнения требуют постоянного времени, но для поиска строки длиной m требуется m сравнений. Radix-деревья могут выполнять эти операции с меньшим количеством сравнений и требуют значительно меньше узлов. Однако radix-деревья также разделяют недостатки trie: поскольку они применимы только к строкам элементов или элементам, имеющим эффективное обратимое отображение в строки, им не хватает полной универсальности сбалансированных деревьев поиска, которые применимы к любому типу данных с полным порядком. Обратимое отображение в строки можно использовать для получения необходимого полного порядка для сбалансированных деревьев поиска, но не наоборот. Это также может быть проблематично, если тип данных предоставляет только операцию сравнения, но не операцию (де)сериализации. Обычно считается, что хеш-таблицы имеют ожидаемое время вставки и удаления O(1), но это верно только если вычисление хеша ключа считается операцией, занимающей постоянное время. Если учитывать время вычисления хеша ключа, то хеш-таблицы имеют ожидаемое время вставки и удаления O(k), но в худшем случае может потребоваться больше времени в зависимости от способа обработки коллизий. Radix-деревья имеют худшее время вставки и удаления O(k). Операции поиска следующего/предыдущего элемента в radix-деревьях не реализуются в хеш-таблицах.

Варианты

В распространенном расширении корневых деревьев используются два цвета узлов, "черный" и "белый". Чтобы проверить, хранится ли заданная строка в дереве, поиск начинается с корня и следует по ребрам, соответствующим символам входной строки, до тех пор, пока дальнейшее продвижение невозможно. Если строка поиска полностью обработана, а конечный узел является черным, поиск не удался; если он белый, поиск успешен. Это позволяет добавлять в дерево большой набор строк с общим префиксом, используя белые узлы, а затем эффективно удалять небольшой набор "исключений", вставляя их с помощью черных узлов. HAT-трие – это структура данных, оптимизированная для кэша и основанная на корневых деревьях, обеспечивающая эффективное хранение и извлечение строк, а также упорядоченную итерацию. По производительности, как по времени, так и по объему занимаемой памяти, она сопоставима с кэш-ориентированной хеш-таблицей. PATRICIA-трие – это специальный вариант радикс-трие (двоичного) порядка 2, в котором узлы хранят не каждый бит каждого ключа, а только позицию первого бита, различающего два поддерева. При обходе алгоритм анализирует индексированный бит ключа поиска и выбирает соответствующее левое или правое поддерево. Важной особенностью PATRICIA-трие является то, что для хранения каждого уникального ключа требуется только один узел, что делает PATRICIA значительно более компактной, чем стандартный двоичный трие. Кроме того, поскольку сами ключи больше не хранятся явно, для подтверждения соответствия необходимо выполнить полное сравнение ключей с индексируемой записью. В этом отношении PATRICIA имеет некоторое сходство с индексацией с использованием хеш-таблицы. Распространенной практикой является ослабление требования о запрете узлов-родителей с единственным потомком в тех случаях, когда родительский узел сам представляет собой допустимый ключ в наборе данных. Этот вариант корневого дерева обеспечивает более высокую эффективность использования памяти, чем вариант, допускающий внутренние узлы только с двумя или более потомками.