En informática , un árbol de base (también trie de base o árbol de prefijos compacto o trie comprimido ) es una estructura de datos que representa un trie (árbol de prefijos) optimizado en 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 el radix r del árbol de base, donde r = 2 x para algún entero x ≥ 1. A diferencia de los árboles regulares, las aristas se pueden etiquetar con secuencias de elementos, así como con 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 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 de bits por fragmento de bits, donde la cantidad de bits en ese fragmento en ese nodo es el radio r del trie de radio. Cuando r es 2, el trie de radio es binario (es decir, se compara 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 fusión de cadenas de bits no divergentes en la clave. Cuando r ≥ 4 es una potencia de 2, entonces el trie de radio es un trie r -ario, lo que disminuye la profundidad del trie de radio a expensas de la escasez potencial.
Como optimización, las etiquetas de borde se pueden almacenar en tamaño constante utilizando dos punteros a una cadena (para el primer y el último elemento). [1]
Tenga en cuenta que, aunque 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 byte de la representación de la cadena cuando se utilizan codificaciones de caracteres multibyte o Unicode .
Los árboles de base son útiles para construir matrices asociativas con claves que se pueden expresar como cadenas. Encuentran una aplicación particular en el área de enrutamiento IP , [2] [3] [4] donde la capacidad de contener grandes rangos de valores con unas 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 base admiten operaciones de inserción, eliminación y búsqueda. La inserción agrega una nueva cadena al trie 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 al base del trie de base.
La operación de búsqueda determina si existe una cadena en un trie. 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 tries, excepto que algunos bordes consumen múltiples elementos.
El siguiente pseudocódigo asume que estos métodos y miembros existen.
Borde
Nodo
función de búsqueda ( cadena x){ // Comienza en la raíz sin encontrar elementos Nodo traverseNode := root ; int elementsFound := 0; // Recorrer hasta encontrar una hoja o no es posible continuar mientras (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length) { // Obtener el siguiente borde a explorar en función de los elementos que aún no se encontraron en x Edge nextEdge := select edge from traverseNode.edges where edge.label es un prefijo de x.suffix(elementsFound) // x.suffix(elementsFound) devuelve los últimos (x.length - elementsFound) elementos de x // ¿Se encontró un borde? if (nextEdge != null ) { // Establezca el siguiente nodo para explorar traverseNode := nextEdge.targetNode; // Incrementar los elementos encontrados en función de la etiqueta almacenada en el borde elementosEncontrados += nextEdge.label.length; } demás { // Terminar 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);}Para insertar una cadena, buscamos en el árbol hasta que no podamos avanzar más. En este punto, añadimos una nueva arista de salida etiquetada con todos los elementos restantes de la cadena de entrada o, si ya hay una arista de salida que comparte un prefijo con la cadena de entrada restante, la dividimos en dos aristas (la primera etiquetada con el prefijo común) y continuamos. Este paso de división garantiza que ningún nodo tenga más hijos que elementos de cadena posibles.
A continuación se muestran varios casos de inserción, aunque pueden existir más. Nótese que r simplemente representa la raíz. Se supone que las aristas se pueden etiquetar con cadenas vacías para terminar las cadenas cuando sea necesario y que la raíz no tiene arista entrante. (El algoritmo de búsqueda descrito anteriormente no funcionará cuando se utilicen aristas de cadena vacía).
Para eliminar una cadena x de un árbol, primero localizamos la hoja que representa a x. Luego, suponiendo que x existe, eliminamos el nodo de hoja correspondiente. Si el padre de nuestro nodo de hoja solo tiene otro hijo, entonces la etiqueta entrante de ese hijo se agrega a la etiqueta entrante del padre y se elimina el hijo.
La estructura de datos fue inventada en 1968 por Donald R. Morrison, [6] con quien está principalmente asociada, y por Gernot Gwehenberger. [7]
Donald Knuth , en las páginas 498-500 del Volumen III de El arte de la programación informática , los llama "árboles de Patricia", probablemente por el acrónimo que aparece 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 de dos vías (es decir, izquierda versus derecha).
(En las siguientes comparaciones, se supone que las claves tienen longitud k y la estructura de datos contiene n miembros).
A diferencia de los árboles balanceados , 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 ser una ventaja, ya que normalmente k ≥ log n , pero en un árbol balanceado cada comparación es una comparación de cadenas que requiere O( k ) tiempo 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 en que las comparaciones comienzan al principio 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 de base pueden realizar estas operaciones con menos comparaciones y requieren muchos menos nodos.
Sin embargo, los árboles de base también comparten las desventajas de los tries: como solo se pueden aplicar a cadenas de elementos o elementos con una asignación reversible eficiente a cadenas, carecen de la generalidad total de los árboles de búsqueda balanceados, que se aplican a cualquier tipo de datos con un ordenamiento total . Se puede utilizar una asignación reversible a cadenas para producir el ordenamiento 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 datos solo proporciona una operación de comparación, pero no una operación de (des) serialización .
Se dice comúnmente que las tablas hash tienen tiempos de inserción y eliminación esperados de O(1), pero esto solo 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 tienen tiempos de inserción y eliminación esperados de O( k ), pero pueden tardar más en el peor de los casos según cómo se gestionen las colisiones. Los árboles de base tienen tiempos de inserción y eliminación de O( k ) en el peor de los casos . Las operaciones sucesor/predecesor 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 dada está almacenada en el árbol, la búsqueda comienza desde la parte superior y sigue los bordes de la cadena de entrada hasta que no se puede avanzar más. 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, utilizando nodos blancos, y luego eliminar un pequeño conjunto de "excepciones" de una manera que ahorra espacio insertándolas utilizando nodos negros.
El HAT-trie es una estructura de datos con capacidad de almacenamiento en caché basada en árboles de bases que ofrece un almacenamiento y recuperación de cadenas eficientes, así como iteraciones ordenadas. El rendimiento, tanto en términos de tiempo como de espacio, es comparable al de la tabla hash con capacidad de almacenamiento en 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 el trie solo requiere que se inserte un nodo por cada clave única almacenada, lo que hace que PATRICIA sea 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 de clave completa en el registro indexado para confirmar una coincidencia. En este sentido, PATRICIA tiene 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. Una desventaja importante de los árboles de base habituales es el uso del espacio, ya que 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 en función del número de elementos secundarios, que crece a medida que se añaden nuevas entradas. Por lo 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 solo un hijo en situaciones en las que el padre representa una clave válida en el conjunto de datos. Esta variante del árbol de base logra una mayor eficiencia espacial que la que solo permite nodos internos con al menos dos hijos. [13]
Rutinas para crear y mantener árboles de radix para búsquedas de enrutamiento.
{{cite book}}: |journal=ignorado ( ayuda )