Árbol de raíz

En informática , un árbol radix (también llamado trie radix , árbol de prefijos compacto o trie comprimido ) es una estructura de datos que representa un trie (árbol de prefijos) optimizado en espacio, donde cada nodo que es el único hijo se fusiona con su padre. El número de hijos de cada nodo interno es como máximo el valor absoluto r del árbol radix, donde r = 2 ^x para algún entero x ≥ 1. A diferencia de los árboles regulares, las aristas pueden etiquetarse con secuencias de elementos, así como con elementos individuales. Esto hace que los árboles radix sean mucho más eficientes para conjuntos pequeños (especialmente si las cadenas son largas) y para conjuntos de cadenas que comparten prefijos largos.

A diferencia de los árboles regulares (donde las claves completas se comparan en masa desde su inicio hasta el punto de desigualdad), la clave en cada nodo se compara fragmento a fragmento, donde la cantidad de bits en ese fragmento en ese nodo es la base r del árbol de prefijos. Cuando r es 2, el árbol de prefijos es binario (es decir, se compara la porción de 1 bit de la clave de ese nodo), lo que minimiza la dispersión a expensas de maximizar la profundidad del árbol, es decir, maximizar hasta la fusión de cadenas de bits no divergentes en la clave. Cuando r ≥ 4 es una potencia de 2, entonces el árbol de prefijos es un árbol r -ario, lo que disminuye la profundidad del árbol de prefijos a expensas de la posible dispersión.

Como optimización, las etiquetas de los bordes se pueden almacenar en tamaño constante utilizando dos punteros a una cadena (para el primer y último elemento). ^{[ 1 ]}

Tenga en cuenta que, si bien los ejemplos de este artículo muestran cadenas como secuencias de caracteres, el tipo de los elementos de la cadena se puede elegir arbitrariamente; por ejemplo, como un bit o un byte de la representación de la cadena cuando se utilizan codificaciones de caracteres multibyte o Unicode .

Los árboles radix son útiles para construir matrices asociativas con claves que pueden expresarse como cadenas. Encuentran una aplicación particular en el área de enrutamiento IP , ^{[ 2 ] [ 3 ] [ 4 ]} donde la capacidad de contener amplios rangos de valores con pocas excepciones es particularmente adecuada para la organización jerárquica de direcciones IP . ^{[ 5 ]} También se utilizan para índices invertidos de documentos de texto en la recuperación de información .

Los árboles de radix admiten operaciones de inserción, eliminación y búsqueda. La inserción añade una nueva cadena al trie, procurando minimizar la cantidad de datos almacenados. La eliminación borra una cadena del trie. Las operaciones de búsqueda incluyen (pero no se limitan necesariamente a) la búsqueda exacta, la búsqueda del predecesor, la búsqueda del sucesor y la búsqueda de todas las cadenas con un prefijo. Todas estas operaciones son de complejidad O( k ), donde k es la longitud máxima de todas las cadenas del conjunto, medida en bits igual a la base del trie de radix.

Buscar

La operación de búsqueda determina si una cadena existe en un trie. La mayoría de las operaciones modifican este enfoque de alguna manera para gestionar sus tareas específicas. Por ejemplo, el nodo donde termina una cadena puede ser importante. Esta operación es similar a la de los tries, excepto que algunas aristas consumen varios elementos.

El siguiente pseudocódigo presupone que estos métodos y miembros existen.

Borde

• Nodo targetNode
• etiqueta de cadena

Nodo

• Matriz de aristas aristas
• función esHoja()

función buscar( cadena x) { // Comienza en la raíz sin elementos encontrados Nodo traverseNode := raíz ; int elementsFound := 0; // Recorre hasta que se encuentre una hoja o no sea posible continuar mientras (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length) { // Obtener la siguiente arista a explorar en función de los elementos aún no encontrados en x Edge nextEdge := seleccionar arista de traverseNode.edges donde edge.label es un prefijo de x.suffix(elementsFound) // x.suffix(elementsFound) devuelve los últimos (x.length - elementsFound) elementos de x// ¿Se encontró una arista? if (nextEdge != null ) { // Establecer el siguiente nodo a explorar traverseNode := nextEdge.targetNode; // Incrementa los elementos encontrados en función de la etiqueta almacenada en el borde. elementosEncontrados += nextEdge.label.length; } demás { // Finalizar el bucle traverseNode := null ; } } // Se encuentra una coincidencia si llegamos a un nodo hoja y hemos utilizado exactamente x.length elementos return (traverseNode != null && traverseNode.isLeaf() && elementsFound == x.length); }

La estructura de datos fue inventada en 1968 por Donald R. Morrison, ^{[ 6 ]} con quien se asocia principalmente, y por Gernot Gwehenberger. ^{[ 7 ]}

Donald Knuth , en las páginas 498-500 del volumen III de The Art of Computer Programming , los denomina "árboles de Patricia", presumiblemente por el acrónimo del título del artículo de Morrison: "PATRICIA - Algoritmo práctico para recuperar información codificada en alfanumérico". Hoy en día, los árboles de Patricia se consideran árboles de base 2, lo que significa que cada bit de la clave se compara individualmente y cada nodo es una rama bidireccional (es decir, izquierda frente a derecha).

(En las siguientes comparaciones, se supone que las claves tienen una longitud k y que la estructura de datos contiene n miembros).

A diferencia de los árboles equilibrados , los árboles radix permiten la búsqueda, inserción y eliminación en tiempo O( k ) en lugar de O(log n ). Esto no parece una ventaja, ya que normalmente k ≥ log n , pero en un árbol equilibrado cada comparación es una comparación de cadenas que requiere un tiempo de O( k ) en el peor de los casos, muchas de las cuales son lentas en la práctica debido a los largos prefijos comunes (en el caso de que las comparaciones comiencen al inicio de la cadena). En un trie, todas las comparaciones requieren un tiempo constante, pero se necesitan m comparaciones para buscar una cadena de longitud m . Los árboles radix pueden realizar estas operaciones con menos comparaciones y requieren muchos menos nodos.

Los árboles Radix también comparten las desventajas de los tries: dado que solo se pueden aplicar a cadenas de elementos o a elementos con una asignación reversible eficiente a cadenas, carecen de la generalidad completa de los árboles de búsqueda balanceados, que se aplican a cualquier tipo de dato con un orden total . Una asignación reversible a cadenas puede utilizarse para producir el orden total requerido para los árboles de búsqueda balanceados, pero no al revés. Esto también puede ser problemático si un tipo de dato solo proporciona una operación de comparación, pero no una operación de (des) serialización .

Se suele decir que las tablas hash tienen tiempos de inserción y eliminación esperados de O(1), pero esto solo es cierto si se considera que el cálculo del hash de la clave es una operación de tiempo constante. Al tener en cuenta el hash de la clave, las tablas hash tienen tiempos de inserción y eliminación esperados de O( k ), pero pueden tardar más en el peor de los casos dependiendo de cómo se gestionen las colisiones. Los árboles radix tienen tiempos de inserción y eliminación en el peor de los casos de O( k ). Las operaciones de sucesor/predecesor de los árboles radix tampoco están implementadas en las tablas hash.

Una extensión común de los árboles radix utiliza nodos de dos colores: "negro" y "blanco". Para comprobar si una cadena dada está almacenada en el árbol, la búsqueda comienza desde la raíz y sigue las aristas de la cadena de entrada hasta que no se puede avanzar más. Si la cadena de búsqueda se ha procesado y el nodo final es negro, la búsqueda ha fallado; si es blanco, la búsqueda ha tenido éxito. Esto permite añadir al árbol un amplio rango de cadenas con un prefijo común, utilizando nodos blancos, y luego eliminar un pequeño conjunto de "excepciones" de forma eficiente en cuanto a espacio, insertándolas mediante nodos negros.

El HAT-trie es una estructura de datos optimizada para caché basada en árboles radix que ofrece almacenamiento y recuperación de cadenas eficientes, así como iteraciones ordenadas. Su rendimiento, tanto en tiempo como en espacio, es comparable al de la tabla hash optimizada para caché . ^{[ 8 ] [ 9 ]}

Un trie PATRICIA es una variante especial del trie binario (de base 2), en el que, en lugar de almacenar explícitamente cada bit de cada clave, los nodos almacenan solo la posición del primer bit que diferencia dos subárboles. Durante el recorrido, el algoritmo examina el bit indexado de la clave de búsqueda y elige el subárbol izquierdo o derecho según corresponda. Entre las características notables del trie PATRICIA se incluye que solo requiere la inserción de un nodo por cada clave única almacenada, lo que lo hace mucho más compacto que un trie binario estándar. Además, dado que las claves reales ya no se almacenan explícitamente, es necesario realizar una comparación completa de claves en el registro indexado para confirmar una coincidencia. En este sentido, PATRICIA guarda cierta semejanza con la indexación mediante una tabla hash. ^{[ 6 ]}

El árbol radix adaptativo es una variante del árbol radix que integra tamaños de nodo adaptativos. Una desventaja importante de los árboles radix convencionales es el uso de espacio, ya que utilizan un tamaño de nodo constante en cada nivel. La principal diferencia entre el árbol radix y el árbol radix adaptativo radica en el tamaño variable de cada nodo, que depende del número de elementos hijos y aumenta al añadir nuevas entradas. Por lo tanto, el árbol radix adaptativo permite un mejor uso del espacio sin reducir su velocidad. ^{[ 10 ] [ 11 ] [ 12 ]}

Una práctica común es flexibilizar el criterio de no permitir padres con un solo hijo en situaciones donde el padre representa una clave válida en el conjunto de datos. Esta variante del árbol radix logra una mayor eficiencia espacial que la que solo permite nodos internos con al menos dos hijos. ^{[ 13 ]}

• Material de investigación y referencia sobre algoritmos y estructuras de datos: PATRICIA , de Lloyd Allison, Universidad de Monash.
• Patricia Tree , Diccionario de algoritmos y estructuras de datos del NIST
• Árboles de bits críticos , por Daniel J. Bernstein
• API de árbol Radix en el kernel de Linux , por Jonathan Corbet
• Kart (árbol radix de alteración de clave) , por Paul Jarc
• El árbol radix adaptativo: indexación ingeniosa para bases de datos en memoria principal , por Viktor Leis, Alfons Kemper , Thomas Neumann , Universidad Técnica de Múnich.