В чем разница между осевшими деревьями и попытками Патриции?

Я узнаю о радикальных деревьях (иначе говоря, сжатых попытках) и попытках Патриции, но я нахожу противоречивую информацию о том, действительно ли они одинаковы. Основное дерево может быть получено из обычного (несжатого) дерева путем объединения узлов с их родителями, когда узлы являются единственными дочерними. Это также касается попыток Патриции. Чем отличаются две структуры данных?

Например, NIST перечисляет два одинаковых:

Патриция дерево

(структура данных)

Определение: компактное представление дерева, в котором любой узел, который является единственным потомком, объединяется со своим родителем.

Также известный как основание дерева.

Многие источники в Интернете утверждают то же самое. Тем не менее, по-видимому, попытки Патриции являются частным случаем радикальных деревьев. Запись в Википедии гласит:

Попытки PATRICIA - это радикальные попытки с радикальными значениями, равными 2, что означает, что каждый бит ключа сравнивается индивидуально, и каждый узел представляет собой двустороннюю (т. Е. Левую или правую) ветвь.

Я не очень понимаю это. Разница только в способах сравнения при поиске? Как каждый узел может быть «двусторонней ветвью»? Разве не должно быть максимально ALPHABET_SIZEвозможных ветвей для данного узла?

Может кто-нибудь уточнить это? Для практических целей, обычно ли попытки основаны на попытках Патриции (и, следовательно, часто считаются одинаковыми)? Или не могут быть сделаны такие обобщения?

Я нашел этот пост очень полезным.

Чтобы увидеть разницу между попытками Патриции и радикальными деревьями, важно понять:

• Понятие корня , так как Патриция пытается это корень дерева с корнем, равным 2.
• То, как ключи обрабатываются: как потоки битов . Ключи сравниваются по битам за раз, где - основание дерева.$r$$2^r$

Предположит , что мы вставляем ключи улыбку , улыбнулись , и улыбка (в этом порядке) в Patricia синтаксического дереве. Двоичное представление этих ключей следующее:

Обратите внимание, что smile является префиксом smiled , и, анализируя двоичное представление, мы видим, что первый отличающийся бит (слева направо) равен 0 (выделен красным во второй строке); По этой причине, улыбнулся будет слева ребенок от улыбки . Точно так же, улыбка будет правый потомок из улыбнулся , потому что они имеют одинаковый префикс до бита, значение которого 1 (выделено красного цвета в третьем ряду). В результате после ввода трех клавиш Патрисия получит следующее:

Если основание было, например, 4, то внутренние узлы могли бы иметь не более четырех дочерних элементов (с краями, помеченными как 00, 01, 10 и 11 соответственно). В этом случае ключи будут сравниваться по блокам по 2 бита, а не по 1 (как в попытках Патриции).

Чем отличаются две структуры данных?

Насколько я понимаю, единственной разницей является основание, которое равно 2 в случае попыток Патрисии. Это значение может быть любой степенью 2 в обычных деревьях осей.

Разница только в способах сравнения при поиске?

В обеих структурах данных операция сравнения является побитовой. Однако количество битов, которые проверяются атомарно, зависит от радиуса. В случае попыток Патриции биты сравниваются индивидуально (так как radix = 2). Это не обязательно так в радикальных деревьях. В общем случае биты проверяются порциями размера , где - основание дерева.$\log_2{R}$$R$

Как каждый узел может быть «двусторонней ветвью»? Разве не должно быть максимально ALPHABET_SIZEвозможных ветвей для данного узла?

Основание определяет максимальное число дочерних элементов, которые могут иметь узлы основанного дерева. Например, когда radix = 2, каждый узел может иметь не более двух дочерних элементов. Это случай попыток Патрисии (также известных как бинарные радикальные деревья).

Реализуются ли радикальные попытки как попытки Патриции (и, следовательно, часто считаются одинаковыми)? Или не могут быть сделаны такие обобщения?

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

Патриция Trie - это двоичная радикальная последовательность, полученная в результате применения алгоритма PATRICIA к буквенно-цифровым данным.

PATRICIA расшифровывается как « Практический алгоритм получения информации, закодированной в буквенно-цифровой форме» [ оригинальная статья Дональда Моррисона ]. В документе определяется основной словарный запас, состоящий из START, STOP, END, L-PHRASE, BRANCH, TWIN и CHAIN. Попытки PATRICIA - это попытки, которые являются результатом применения этого алгоритма - попытки двоичного радиуса, где основание, r, равно 2 [ wikipedia ] (и выше); двоичный выбор в каждом узле при обходе дерева).

Однако на практике термин Patricia, по-видимому, используется с r> = 2 (то есть, попытками радиуса), где используется аналогичный алгоритм хранения и поиска. Например, это называется Патриция. Эфириума Патрисия Меркл Trie еще один пример, где г 16 в определенных узлах.