В информатике radix tree (также radix trie или compact prefix tree или compress trie ) — это структура данных , которая представляет собой оптимизированное по пространству trie (префиксное дерево), в котором каждый узел, являющийся единственным потомком, объединяется со своим родителем. Результатом является то, что количество потомков каждого внутреннего узла не превышает radix r radix tree, где r = 2 x для некоторого целого числа x ≥ 1. В отличие от обычных деревьев, ребра могут быть помечены последовательностями элементов, а также отдельными элементами. Это делает radix trees гораздо более эффективными для небольших наборов (особенно если строки длинные) и для наборов строк, которые имеют длинные префиксы.
В отличие от обычных деревьев (где все ключи сравниваются в массовом порядке от начала до точки неравенства), ключ в каждом узле сравнивается по частям битов, где количество битов в этой части в этом узле равно основанию r радиксного дерева. Когда r равно 2, радиксное дерево является бинарным (т. е. сравнивается 1-битная часть ключа этого узла), что минимизирует разреженность за счет максимизации глубины дерева — т. е. максимизации вплоть до объединения нерасходящихся битовых строк в ключе. Когда r ≥ 4 является степенью 2, то радиксное дерево является r -арным деревом, что уменьшает глубину радиксного дерева за счет потенциальной разреженности.
В качестве оптимизации метки ребер можно хранить в постоянном размере, используя два указателя на строку (для первого и последнего элементов). [1]
Обратите внимание, что хотя примеры в этой статье показывают строки как последовательности символов, тип элементов строки может быть выбран произвольно; например, как бит или байт представления строки при использовании многобайтовых кодировок символов или Unicode .
Радикальные деревья полезны для построения ассоциативных массивов с ключами, которые могут быть выражены как строки. Они находят особое применение в области IP- маршрутизации , [2] [3] [4] где способность содержать большие диапазоны значений с несколькими исключениями особенно подходит для иерархической организации IP-адресов . [5] Они также используются для инвертированных индексов текстовых документов при поиске информации .
Деревья Radix поддерживают операции вставки, удаления и поиска. Вставка добавляет новую строку в trie, пытаясь минимизировать объем хранимых данных. Удаление удаляет строку из trie. Операции поиска включают (но не обязательно ограничиваются) точный поиск, поиск предшественника, поиск последователя и поиск всех строк с префиксом. Все эти операции являются O( k ), где k — максимальная длина всех строк в наборе, где длина измеряется в количестве бит, равном основанию trie radix.
Операция поиска определяет, существует ли строка в trie. Большинство операций изменяют этот подход некоторым образом для решения своих конкретных задач. Например, узел, в котором заканчивается строка, может иметь значение. Эта операция похожа на попытки, за исключением того, что некоторые ребра потребляют несколько элементов.
Следующий псевдокод предполагает, что эти методы и члены существуют.
Край
Узел
функция поиска ( строка x){ // Начнем с корня, элементы не найдены Node traverseNode := root ; int elementsFound := 0; // Проход до тех пор, пока не будет найден лист или продолжение невозможно while (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length) { // Получаем следующее ребро для исследования на основе элементов, которые еще не найдены в x Edge nextEdge := select edge from traverseNode.edges where edge.label is a prefix of x.suffix(elementsFound) // x.suffix(elementsFound) возвращает последние (x.length - elementsFound) элементы x // Было ли найдено ребро? if (nextEdge != null ) { // Устанавливаем следующий узел для исследования traverseNode := nextEdge.targetNode; // Увеличиваем элементы, найденные на основе метки, сохраненной на краю elementsFound += nextEdge.label.length; } еще { // Завершить цикл traverseNode := null ; } } // Соответствие найдено, если мы достигли конечного узла и израсходовали ровно x.length элементов return (traverseNode != null && traverseNode.isLeaf() && elementsFound == x.length);}Чтобы вставить строку, мы ищем по дереву до тех пор, пока не сможем двигаться дальше. В этот момент мы либо добавляем новое исходящее ребро, помеченное всеми оставшимися элементами во входной строке, либо, если уже есть исходящее ребро, разделяющее префикс с оставшейся входной строкой, мы разделяем его на два ребра (первое помечено общим префиксом) и продолжаем. Этот шаг разделения гарантирует, что ни один узел не имеет больше потомков, чем возможных элементов строки.
Ниже показано несколько случаев вставки, хотя их может быть больше. Обратите внимание, что r просто представляет корень. Предполагается, что ребра могут быть помечены пустыми строками для завершения строк, где это необходимо, и что корень не имеет входящих ребер. (Описанный выше алгоритм поиска не будет работать при использовании ребер с пустыми строками.)
Чтобы удалить строку x из дерева, мы сначала находим лист, представляющий x. Затем, предполагая, что x существует, мы удаляем соответствующий листовой узел. Если родительский узел нашего листового узла имеет только одного другого потомка, то входящая метка этого потомка добавляется к входящей метке родителя, а потомок удаляется.
Структура данных была изобретена в 1968 году Дональдом Р. Моррисоном [6], с которым она в первую очередь ассоциируется, и Гернотом Гвеенбергером [7] .
Дональд Кнут , страницы 498-500 в третьем томе «Искусства программирования », называет их «деревьями Патрисии», предположительно, по аббревиатуре в названии статьи Моррисона: «PATRICIA — Практический алгоритм извлечения информации, закодированной в алфавитно-цифровом формате». Сегодня деревья Патрисии рассматриваются как деревья с основанием, равным 2, что означает, что каждый бит ключа сравнивается индивидуально, а каждый узел является двухсторонней (т. е. левой и правой) ветвью.
(В следующих сравнениях предполагается, что ключи имеют длину k , а структура данных содержит n членов.)
В отличие от сбалансированных деревьев , радиксные деревья позволяют выполнять поиск, вставку и удаление за время O( k ), а не O(log n ). Это не кажется преимуществом, так как обычно k ≥ log n , но в сбалансированном дереве каждое сравнение является сравнением строк, требующим O( k ) времени в худшем случае, многие из которых на практике медленны из-за длинных общих префиксов (в случае, когда сравнения начинаются с начала строки). В trie все сравнения требуют постоянного времени, но для поиска строки длиной m требуется m сравнений . Радиксные деревья могут выполнять эти операции с меньшим количеством сравнений и требуют гораздо меньшего количества узлов.
Однако радиксные деревья также разделяют недостатки попыток: поскольку они могут применяться только к строкам элементов или элементам с эффективно обратимым отображением в строки, им не хватает полной общности сбалансированных деревьев поиска, которые применяются к любому типу данных с полным порядком . Обратимое отображение в строки может использоваться для получения требуемого полного порядка для сбалансированных деревьев поиска, но не наоборот. Это также может быть проблематичным, если тип данных предоставляет только операцию сравнения, но не операцию (де) сериализации .
Обычно говорят, что хэш-таблицы имеют ожидаемое время вставки и удаления O(1), но это верно только в том случае, если считать вычисление хеша ключа операцией постоянного времени. Если принять во внимание хэширование ключа, хэш-таблицы имеют ожидаемое время вставки и удаления O( k ), но в худшем случае это может занять больше времени в зависимости от того, как обрабатываются коллизии. Радикальные деревья имеют худший случай вставки и удаления O( k ). Операции последователя/предшественника радиксных деревьев также не реализованы хэш-таблицами.
Распространенное расширение радиксных деревьев использует два цвета узлов: «черный» и «белый». Чтобы проверить, хранится ли заданная строка в дереве, поиск начинается сверху и следует по краям входной строки до тех пор, пока дальнейший прогресс не будет невозможен. Если строка поиска израсходована, а конечный узел — черный, поиск не удался; если он белый, поиск удался. Это позволяет нам добавлять в дерево большой диапазон строк с общим префиксом, используя белые узлы, а затем удалять небольшой набор «исключений» экономным способом, вставляя их, используя черные узлы.
HAT -trie — это кэш-ориентированная структура данных, основанная на радиксных деревьях, которая предлагает эффективное хранение и извлечение строк, а также упорядоченные итерации. Производительность, как по времени, так и по пространству, сопоставима с кэш-ориентированной хеш-таблицей . [8] [9]
PATRICIA trie — это особый вариант radix 2 (двоичного) trie, в котором вместо явного хранения каждого бита каждого ключа узлы хранят только позицию первого бита, который различает два поддерева. Во время обхода алгоритм проверяет индексированный бит ключа поиска и выбирает левое или правое поддерево по мере необходимости. Известные особенности PATRICIA trie включают в себя то, что trie требует вставки только одного узла для каждого уникального сохраненного ключа, что делает PATRICIA намного более компактным, чем стандартный двоичный trie. Кроме того, поскольку фактические ключи больше не хранятся явно, необходимо выполнить одно полное сравнение ключей с индексированной записью, чтобы подтвердить совпадение. В этом отношении PATRICIA имеет определенное сходство с индексированием с использованием хэш-таблицы. [6]
Адаптивное радиксное дерево — это вариант радиксного дерева, который интегрирует адаптивные размеры узлов в радиксное дерево. Одним из основных недостатков обычных радиксных деревьев является использование пространства, поскольку оно использует постоянный размер узла на каждом уровне. Основное различие между радиксным деревом и адаптивным радиксным деревом — его переменный размер для каждого узла на основе количества дочерних элементов, который растет при добавлении новых записей. Таким образом, адаптивное радиксное дерево приводит к лучшему использованию пространства без снижения его скорости. [10] [11] [12]
Распространенной практикой является смягчение критериев запрета родителей с одним потомком в ситуациях, когда родитель представляет действительный ключ в наборе данных. Этот вариант радиксного дерева достигает более высокой эффективности пространства, чем тот, который допускает только внутренние узлы с по крайней мере двумя потомками. [13]
Процедуры для построения и поддержки деревьев счисления для поиска маршрутов.
{{cite book}}: |journal=проигнорировано ( помощь )