En informática , un árbol de base (también radix trie o árbol de prefijos compacto o trie comprimido ) es una estructura de datos que representa un trie (árbol de prefijos) optimizado para el espacio en el que cada nodo que es el único hijo se fusiona con su padre. El resultado es que el número de hijos de cada nodo interno es como máximo la base r del árbol de base, donde r = 2 x para algún número entero x ≥ 1. A diferencia de los árboles normales, los bordes se pueden etiquetar con secuencias de elementos, así como elementos individuales. Esto hace que los árboles de base 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 normales (donde las claves completas se comparan en masa desde su inicio hasta el punto de desigualdad), la clave en cada nodo se compara fragmento de bits por fragmento de bits, donde la cantidad de bits en ese fragmento en ese nodo es la base r de la base trie. Cuando r es 2, la raíz trie es binaria (es decir, compare la porción de 1 bit de la clave de ese nodo), lo que minimiza la escasez a expensas de maximizar la profundidad del trie, es decir, maximizar hasta la combinación de cadenas de bits no divergentes en la clave. . Cuando r ≥ 4 es una potencia de 2, entonces la raíz trie es una r -aria, lo que disminuye la profundidad de la base trie a expensas de la escasez potencial.
Como optimización, las etiquetas de borde se pueden almacenar en tamaño constante mediante el uso de dos punteros a una cadena (para el primer y último elemento). [1]
Tenga en cuenta que aunque los ejemplos de este artículo muestran cadenas como secuencias de caracteres, el tipo de elementos de la cadena se puede elegir arbitrariamente; por ejemplo, como un bit o byte de la representación de cadena cuando se utilizan codificaciones de caracteres multibyte o Unicode .
Los árboles de base son útiles para construir matrices asociativas con claves que pueden expresarse como cadenas. Encuentran una aplicación particular en el área del enrutamiento IP , [2] [3] [4] donde la capacidad de contener grandes rangos de valores con algunas 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 Radix admiten operaciones de inserción, eliminación y búsqueda. La inserción agrega una nueva cadena al intento mientras intenta minimizar la cantidad de datos almacenados. La eliminación elimina una cadena del trie. Las operaciones de búsqueda incluyen (pero no se limitan necesariamente a) búsqueda exacta, búsqueda de predecesor, búsqueda de sucesor y búsqueda de todas las cadenas con un prefijo. Todas estas operaciones son O( k ) donde k es la longitud máxima de todas las cadenas en el conjunto, donde la longitud se mide en la cantidad de bits igual a la base de la raíz trie.
La operación de búsqueda determina si existe una cadena en un intento. La mayoría de las operaciones modifican este enfoque de alguna manera para manejar sus tareas específicas. Por ejemplo, el nodo donde termina una cadena puede ser importante. Esta operación es similar a los intentos excepto que algunos bordes consumen múltiples elementos.
El siguiente pseudocódigo supone que estos métodos y miembros existen.
Borde
Nodo
búsqueda de función ( cadena x){ // Comienza en la raíz sin encontrar elementos Nodo traverseNode := root ; elementos int encontrados: = 0; // Atraviesa hasta encontrar una hoja o no es posible continuar mientras (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length) { // Obtenga el siguiente borde para explorar en función de los elementos que aún no se encuentran en x Edge nextEdge: = seleccione el borde de traverseNode.edges donde edge.label es un prefijo de x.suffix(elementsFound) // x.suffix(elementsFound) devuelve los últimos elementos (x.length - elementsFound) de x // ¿Se encontró una ventaja? si (bordesiguiente! = nulo ) { // Establece el siguiente nodo a explorar traverseNode := nextEdge.targetNode; // Incrementa los elementos encontrados según la etiqueta almacenada en el borde elementos encontrados += nextEdge.label.length; } demás { // Terminar el bucle traverseNode := null ; } } // Se encuentra una coincidencia si llegamos a un nodo hoja y hemos usado exactamente x.length elementos return (traverseNode != null && traverseNode.isLeaf() && elementsFound == x.length);}Para insertar una cadena, buscamos en el árbol hasta que no podamos avanzar más. En este punto, agregamos un nuevo borde de salida etiquetado con todos los elementos restantes en la cadena de entrada, o si ya hay un borde de salida que comparte un prefijo con la cadena de entrada restante, lo dividimos en dos bordes (el primero etiquetado con el código común prefijo) y continuar. Este paso de división garantiza que ningún nodo tenga más hijos que posibles elementos de cadena.
A continuación se muestran varios casos de inserción, aunque pueden existir más. Tenga en cuenta que r simplemente representa la raíz. Se supone que los bordes se pueden etiquetar con cadenas vacías para terminar cadenas cuando sea necesario y que la raíz no tiene un borde entrante. (El algoritmo de búsqueda descrito anteriormente no funcionará cuando se utilicen bordes de cadena vacía).
Para eliminar una cadena x de un árbol, primero ubicamos la hoja que representa x. Luego, suponiendo que x existe, eliminamos el nodo hoja correspondiente. Si el padre de nuestro nodo hoja tiene solo otro hijo, entonces la etiqueta entrante de ese hijo se agrega a la etiqueta entrante del padre y el hijo se elimina.
La estructura de datos fue inventada en 1968 por Donald R. Morrison, [6] con quien está principalmente asociado, y por Gernot Gwehenberger. [7]
Donald Knuth , páginas 498-500 en el Volumen III de El arte de la programación informática , los llama "árboles de Patricia", presumiblemente por el acrónimo en el 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 con base igual a 2, lo que significa que cada bit de la clave se compara individualmente y cada nodo es una rama bidireccional (es decir, izquierda versus 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 de base 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 O( k ) tiempo en el peor de los casos, muchos de los cuales son lentos en la práctica debido a prefijos comunes largos (en el caso donde las comparaciones comienzan al inicio de la cadena). En un intento, 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.
Sin embargo, los árboles Radix también comparten las desventajas de los intentos: como solo se pueden aplicar a cadenas de elementos o elementos con un mapeo eficientemente reversible a cadenas, carecen de la generalidad completa de los árboles de búsqueda balanceados, que se aplican a cualquier tipo de datos con un total ordenar . Se puede utilizar una asignación reversible a cadenas para producir el orden total requerido para árboles de búsqueda equilibrados, pero no al revés. Esto también puede ser problemático si un tipo de datos solo proporciona una operación de comparación, pero no una operación de (des) serialización .
Se suele decir que las tablas hash esperan tiempos de inserción y eliminación O(1), pero esto sólo es cierto cuando se considera que el cálculo del hash de la clave es una operación de tiempo constante. Cuando se tiene en cuenta el hash de la clave, las tablas hash esperan tiempos de inserción y eliminación O( k ), pero pueden tardar más en el peor de los casos dependiendo de cómo se manejen las colisiones. Los árboles de base tienen inserción y eliminación de O ( k ) en el peor de los casos. Las operaciones sucesoras/predecesoras de los árboles de base tampoco se implementan mediante tablas hash.
Una extensión común de los árboles de base utiliza dos colores de nodos, "negro" y "blanco". Para comprobar si una cadena determinada está almacenada en el árbol, la búsqueda comienza desde arriba y sigue los bordes de la cadena de entrada hasta que no se pueda realizar más progreso. Si la cadena de búsqueda se consume y el nodo final es un nodo negro, la búsqueda ha fallado; si es blanco, la búsqueda ha tenido éxito. Esto nos permite agregar una gran variedad de cadenas con un prefijo común al árbol, usando nodos blancos, y luego eliminar un pequeño conjunto de "excepciones" de manera eficiente en el espacio insertándolas usando nodos negros.
HAT -trie es una estructura de datos consciente de la caché basada en árboles de base que ofrece almacenamiento y recuperación de cadenas eficientes e iteraciones ordenadas. El rendimiento, con respecto al tiempo y al espacio, es comparable al de la tabla hash consciente del caché . [8] [9]
Un trie PATRICIA es una variante especial del trie de base 2 (binario), 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. Las características notables del trie PATRICIA incluyen que solo requiere que se inserte un nodo para cada clave única almacenada, lo que hace que PATRICIA sea mucho más compacta 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 de claves completa 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 de base adaptativo es una variante del árbol de base que integra tamaños de nodos adaptativos al árbol de base. Un gran inconveniente de los árboles de base habituales es el uso del espacio, porque utiliza un tamaño de nodo constante en cada nivel. La principal diferencia entre el árbol de base y el árbol de base adaptativo es su tamaño variable para cada nodo según la cantidad de elementos secundarios, que crece a medida que se agregan nuevas entradas. Por tanto, el árbol de base adaptativo conduce a un mejor uso del espacio sin reducir su velocidad. [10] [11] [12]
Una práctica común es relajar los criterios de no permitir padres con un solo hijo en situaciones en las que el padre representa una clave válida en el conjunto de datos. Esta variante de árbol de base logra una mayor eficiencia espacial que la que solo permite nodos internos con al menos dos hijos. [13]
Rutinas para construir y mantener árboles de base para búsquedas de rutas.
{{cite book}}: |journal=ignorado ( ayuda ){{cite book}}: Mantenimiento CS1: fecha y año ( enlace )