Estoy aprendiendo sobre los árboles radix (también conocidos como intentos comprimidos) y Patricia intenta, pero encuentro información contradictoria sobre si realmente son lo mismo o no. Se puede obtener un árbol de raíz de un trie normal (sin comprimir) fusionando nodos con sus padres cuando los nodos son el único hijo. Esto también es válido para los intentos de Patricia. ¿De qué maneras son diferentes las dos estructuras de datos?
Por ejemplo, NIST enumera los dos como iguales:
Árbol patricia
(estructura de datos)
Definición: Una representación compacta de un trie en el que cualquier nodo que es hijo único se fusiona con su padre.
También conocido como árbol radix.
Muchas fuentes en la web afirman lo mismo. Sin embargo, aparentemente los intentos de Patricia son un caso especial de árboles radix. La entrada de Wikipedia dice:
Los intentos de PATRICIA son intentos de radix con radix igual a 2, lo que significa que cada bit de la clave se compara individualmente y cada nodo es una rama de dos vías (es decir, izquierda versus derecha).
Realmente no entiendo esto. ¿Es la diferencia solo en la forma en que se hacen las comparaciones al hacer búsquedas? ¿Cómo puede cada nodo ser una "rama de dos vías"? ¿No debería haber como máximo ALPHABET_SIZE
ramas posibles para un nodo dado?
¿Alguien puede aclarar esto? Para fines prácticos, ¿los intentos de radix se implementan típicamente como los intentos de Patricia (y, por lo tanto, a menudo se consideran lo mismo)? ¿O no se pueden hacer tales generalizaciones?
fuente