Qual é a diferença entre árvores radix e Patricia tenta?

Estou aprendendo sobre árvores de raiz (tentativas compactadas) e tentativas de Patricia, mas estou encontrando informações conflitantes sobre se elas são realmente iguais ou não. Uma árvore de raiz pode ser obtida de uma tentativa normal (não compactada) mesclando nós com seus pais quando os nós são o único filho. Isso também vale para tentativas de Patricia. De que maneira as duas estruturas de dados são diferentes?

Por exemplo, o NIST lista os dois da mesma forma:

Árvore Patricia

(estrutura de dados)

Definição: Uma representação compacta de uma tentativa na qual qualquer nó que é filho único é mesclado com seu pai.

Também conhecida como árvore de raiz.

Muitas fontes na web afirmam o mesmo. No entanto, aparentemente Patricia tenta ser um caso especial de árvores de raiz. A entrada da Wikipedia diz:

PATRICIA try são tentativas de raiz com raiz igual a 2, o que significa que cada bit da chave é comparado individualmente e cada nó é um ramo de mão dupla (ou seja, esquerda versus direita).

Eu realmente não entendo isso. A diferença é apenas na maneira como são feitas comparações ao fazer pesquisas? Como cada nó pode ser um "ramo de mão dupla"? Não deveria haver, no máximo, ALPHABET_SIZEramificações possíveis para um determinado nó?

Alguém pode esclarecer isso? Para fins práticos, as tentativas com base em radix são tipicamente implementadas como Patricia tenta (e, portanto, geralmente é considerada a mesma)? Ou essas generalizações não podem ser feitas?

Achei este post muito útil.

Para ver a diferença entre Patricia try e radix trees, é importante entender:

• A noção de raiz , uma vez que Patricia tenta, são árvores de raiz com raiz igual a 2.
• $r$$2^r$

Suponha que inseramos as chaves smile , sorriu e sorria (nessa ordem) em uma tentativa de Patricia. A representação binária dessas chaves é a seguinte:

Observe que smile é um prefixo de smiled e, analisando a representação binária, podemos ver que o primeiro bit que difere (da esquerda para a direita) é 0 (destacado em vermelho na segunda linha); por esse motivo, sorriu será o filho esquerdo do sorriso . Da mesma forma, os sorrisos serão o filho certo de sorriram porque compartilham o mesmo prefixo até um bit cujo valor é 1 (destacado em vermelho na terceira linha). A Patricia resultante depois de inserir as três chaves é a seguinte:

Se a raiz fosse, por exemplo, 4, os nós internos poderiam ter, no máximo, quatro filhos (com as bordas marcadas 00, 01, 10 e 11, respectivamente). Nesse caso, as chaves seriam comparadas por pedaços de 2 bits, e não 1 (como tenta Patricia).

De que maneira as duas estruturas de dados são diferentes?

No meu entender, a única diferença é a raiz, que é igual a 2 no caso de Patricia tentar. Este valor pode ser qualquer potência de 2 em árvores de raiz regulares.

A diferença é apenas na maneira como as comparações são feitas ao fazer pesquisas?

$\log_2{R}$$R$

Como cada nó pode ser um "ramo de mão dupla"? Não deveria haver, no máximo, ALPHABET_SIZEramificações possíveis para um determinado nó?

O radical estabelece o número máximo de filhos que os nós de uma árvore de radical podem ter. Por exemplo, quando radix = 2, cada nó pode ter no máximo dois filhos. É o caso das tentativas de Patricia (também conhecidas como árvores de raiz binária).

As tentativas radix são tipicamente implementadas como Patricia tenta (e, portanto, muitas vezes considerada a mesma)? Ou essas generalizações não podem ser feitas?

Para ser sincero, não tenho uma resposta para esta pergunta. Parece que as duas estruturas de dados foram propostas na mesma época por diferentes autores. Por razões históricas das quais desconheço, os dois termos ainda existem hoje.

Um Patricia trie é um radical binário que resulta da aplicação do algoritmo PATRICIA a dados alfanuméricos.

PATRICIA significa Algoritmo Prático para Recuperar Informações Codificadas em Alfanumérico [ artigo original de Donald R. Morrison ]. O artigo define um vocabulário básico que consiste em INICIAR, PARAR, FIM, L-FRASE, FILIAL, GÊMEO e CORRENTE. PATRICIA try são as tentativas que resultam da aplicação desse algoritmo - tentativas binárias de raiz, onde a raiz, r, é 2 [ wikipedia ] (e acima); uma opção binária em cada nó ao atravessar o trie).

No entanto, na prática, o termo Patricia parece ser usado com r> = 2 (ou seja, tentativas radix), onde é usado um alogoritmo de armazenamento e pesquisa semelhante. Por exemplo, isso é intitulado como patricia. O Ethereum Patricia Merkle Trie é outro exemplo, em que r é 16 em determinados nós.