En informática , un árbol WAVL o un árbol AVL débil es un árbol de búsqueda binaria autoequilibrado . Los árboles WAVL llevan el nombre de los árboles AVL , otro tipo de árbol de búsqueda equilibrado, y están estrechamente relacionados tanto con los árboles AVL como con los árboles rojo-negro , que caen en un marco común de árboles equilibrados de rango . Al igual que otros árboles de búsqueda binaria equilibrada, los árboles WAVL pueden manejar operaciones de inserción, eliminación y búsqueda en el tiempo O (log n ) por operación. [1] [2]
Los árboles WAVL están diseñados para combinar algunas de las mejores propiedades de los árboles AVL y de los árboles rojo-negro. Una ventaja de los árboles AVL sobre los árboles rojo-negros es que son más equilibrados: tienen una altura como máximo(para un árbol con n elementos de datos, dondees la proporción áurea ), mientras que los árboles rojo-negro tienen una altura máxima mayor,. Si un árbol WAVL se crea usando solo inserciones, sin eliminaciones, entonces tiene el mismo límite de altura pequeño que tiene un árbol AVL. Por otro lado, los árboles rojo-negro tienen la ventaja sobre los árboles AVL en una menor reestructuración de sus árboles. En los árboles AVL, cada eliminación puede requerir un número logarítmico de operaciones de rotación de árboles , mientras que los árboles rojo-negro tienen operaciones de eliminación más simples que utilizan solo un número constante de rotaciones de árboles. Los árboles WAVL, como los árboles rojo-negro, usan solo un número constante de rotaciones de árboles, y la constante es incluso mejor que para los árboles rojo-negro. [1] [2]
Los árboles WAVL fueron introducidos por Haeupler, Sen y Tarjan (2015) . Los mismos autores también proporcionaron una visión común de los árboles AVL, los árboles WAVL y los árboles rojo-negro como un tipo de árbol de rango equilibrado. [2]
Definición
Al igual que con los árboles de búsqueda binaria en general, un árbol WAVL consta de una colección de nodos , de dos tipos: nodos internos y nodos externos. Un nodo interno almacena un elemento de datos y está vinculado a su padre (excepto por un nodo raíz designado que no tiene padre) y exactamente a dos hijos en el árbol, el hijo izquierdo y el hijo derecho. Un nodo externo no transporta datos y tiene un enlace solo a su padre en el árbol. Estos nodos están dispuestos para formar un árbol binario, de modo que para cualquier nodo interno x los padres de los hijos izquierdo y derecho de x sean el mismo x . Los nodos externos forman las hojas del árbol. [3] Los elementos de datos se organizan en el árbol de tal manera que un recorrido en orden del árbol enumera los elementos de datos en orden ordenado. [4]
Lo que distingue a los árboles WAVL de otros tipos de árboles de búsqueda binaria es el uso de rangos . Estos son números, asociados con cada nodo, que proporcionan una aproximación a la distancia desde el nodo hasta su descendiente de hoja más lejana. A diferencia de los árboles AVL, donde los rangos se definen como iguales a las alturas de los nodos, los rangos no siempre son iguales a las alturas en los árboles WAVL. La diferencia de rango del nodo x se define como la diferencia entre el rango del padre de x y el rango de x. Los rangos deben obedecer las siguientes propiedades: [1] [2]
- Propiedad de nodo externo: cada nodo externo tiene rango 0 [5]
- Propiedad de diferencia de rango: si un nodo no raíz tiene rango r , entonces el rango de su padre debe ser r + 1 o r + 2 . En otras palabras, la diferencia de rango para cualquier nodo no raíz es 1 o 2. [1]
- Propiedad de nodo interno: un nodo interno con dos hijos externos debe tener el rango exactamente 1.
Operaciones
buscando
La búsqueda de una clave k en un árbol WAVL es muy similar a la de cualquier estructura de datos de árbol de búsqueda binaria equilibrada. Uno comienza en la raíz del árbol y luego compara repetidamente k con el elemento de datos almacenado en cada nodo en una ruta desde la raíz, siguiendo la ruta hacia el hijo izquierdo de un nodo cuando k es menor que el valor en el nodo o en lugar de seguir la ruta hacia el hijo derecho cuando k es mayor que el valor en el nodo. Cuando se alcanza un nodo con valor igual ak , o se alcanza un nodo externo, la búsqueda se detiene. [6]
Si la búsqueda se detiene en un nodo interno, se ha encontrado la clave k . Si, en cambio, la búsqueda se detiene en un nodo externo, entonces se ha encontrado la posición donde se insertaría k (si estuviera insertada). [6]
Inserción
Insertar un nodo interno con la clave k en un árbol WAVL requiere una búsqueda de k en el árbol, terminando en un nodo externo, luego un reemplazo de ese nodo externo con el nuevo nodo interno con dos hijos externos, y finalmente un reequilibrio del árbol . El paso de reequilibrio se puede realizar de arriba hacia abajo o de abajo hacia arriba, [2] pero la versión de abajo hacia arriba del reequilibrio es la que más se asemeja a los árboles AVL. [1] [2]
El reequilibrio ascendente comienza considerando la diferencia de rango entre un nodo, inicialmente el nodo recién insertado, y su padre. Si no hay padres, se restablece el equilibrio. Antes de que comenzara la inserción, la diferencia de rango entre el padre y el nodo era 1 o 2, pero esa diferencia se ha reducido en 1 porque el subárbol enraizado en el nodo se ha vuelto más alto. Si la nueva diferencia de rango entre el padre y el nodo es 1, se restablece el equilibrio. De lo contrario, si el hermano, el otro hijo del padre, tiene una diferencia de rango de 1 con el padre, promueva al padre (aumente su rango aumentando las diferencias de rango entre él y cada uno de sus hijos) y continúe reequilibrando con el anterior. padre como el nuevo nodo.
Finalmente, con diferencias de rango de 0 y 2 para el nodo y el hermano, una o dos rotaciones de árbol, con los ajustes asociados a las diferencias de rango, pueden restablecer el equilibrio. El hijo intermedio del nodo es el que tiene una clave entre las claves del nodo y el padre. Si la diferencia de rango para ese hijo y nodo es 2, rote para mover el nodo hacia arriba en el árbol y el padre hacia abajo, luego degradar al padre (reduzca su rango ajustando las diferencias de rango a su alrededor) y se restablecerá el equilibrio. De lo contrario, gire para mover al niño hacia arriba y el nodo hacia abajo, luego gire nuevamente para mover al niño hacia arriba y al padre hacia abajo. Asciende al niño, degrada al nodo y al padre, y se restablece el equilibrio.
Así, en general, el procedimiento de inserción consiste en una búsqueda, la creación de un número constante de nuevos nodos, un número logarítmico de cambios de rango y un número constante de rotaciones de árboles. [1] [2]
Supresión
La eliminación de un nodo interno de un árbol WAVL comienza con la eliminación ordinaria del árbol de búsqueda binaria . Para un nodo interno sin hijo externo, eso significa encontrar su sucesor en el árbol, intercambiar el nodo con su sucesor y luego eliminar el nodo de su nueva posición de árbol, donde su hijo izquierdo es necesariamente un nodo externo. Para eliminar un nodo interno con un hijo externo, reemplace el nodo con el otro hijo.
El reequilibrio de abajo hacia arriba comienza considerando la diferencia de rango entre un nodo, inicialmente, el nodo que reemplazó al nodo eliminado, y su padre. Si no hay padres, se restablece el equilibrio. Antes de que comenzara la eliminación, la diferencia de rango entre el padre y el nodo era 1 o 2, pero esa diferencia se ha incrementado en 1 porque el subárbol enraizado en el nodo se ha acortado. Si el padre ahora tiene dos hijos externos, la propiedad del nodo interno se viola porque el padre tiene rango 2. El padre debe ser degradado y el reequilibrio continúa con el padre como el nodo que es la raíz del subárbol demasiado corto.
Si el nodo no tiene padre, se restablece el equilibrio. Si la diferencia de rango entre el nodo y el padre ha aumentado de 1 a 2, se restablece el equilibrio. De lo contrario, si el hermano, el otro hijo del padre, tiene una diferencia de rango de 2 con el padre, degradar al padre (disminuir su rango al disminuir las diferencias de rango entre él y cada uno de sus hijos) y continuar reequilibrando con el anterior. padre como el nuevo nodo. De lo contrario, si los dos hijos del hermano tienen diferencias de rango de 2 con el hermano, degradar al padre y al hermano y continuar reequilibrando con el padre anterior como el nuevo nodo.
Finalmente, con diferencias de rango de 3 y 1 para nodo y hermano, y con un hermano que tiene un hijo con diferencia de rango 1, una o dos rotaciones de árbol, con los ajustes asociados a las diferencias de rango, pueden restablecer el equilibrio. Identifique a los hijos del hermano como la sobrina y el sobrino, donde la llave de la sobrina se encuentra entre las llaves del padre y el hermano, y la llave del sobrino no. Si la diferencia de rango entre hermano y sobrino es 1, rotar para mover al hermano hacia arriba y al padre hacia abajo, promover al hermano y degradar al padre una vez, al menos, y dos veces, si es necesario para evitar violar la propiedad del nodo interno. De lo contrario, con la diferencia de rango entre hermano y sobrino como 1, rotar para mover a la sobrina hacia arriba y al hermano hacia abajo, rotar nuevamente para mover a la sobrina hacia arriba y al padre hacia abajo, promover a la sobrina dos veces, degradar al hermano una vez y degradar la categoría. padre dos veces.
En general, una eliminación consiste en una búsqueda hacia abajo para encontrar un nodo con un hijo externo, la eliminación de un número constante de nuevos nodos, un número logarítmico de cambios de rango y un número constante de rotaciones de árboles. [1] [2]
Vale la pena comparar el resultado de una eliminación que causaría rotaciones en múltiples niveles en un árbol AVL con la rotación y los cambios de rango realizados en un árbol WAVL. En la segunda imagen, el nodo con valor 12 ha sido eliminado, seguido de una rotación a la derecha y la asignación de todos los nodos externos al rango cero.
Complejidad computacional
Cada búsqueda, inserción o eliminación en un árbol WAVL implica seguir una única ruta en el árbol y realizar un número constante de pasos para cada nodo en la ruta. En un árbol WAVL con n elementos que solo se han insertado , la longitud máxima de la ruta es. Si pueden haber ocurrido tanto inserciones como eliminaciones, la longitud máxima de la ruta es. Por lo tanto, en cualquier caso, el peor momento para cada búsqueda, inserción o eliminación en un árbol WAVL con n elementos de datos es O (log n ) .
Además, después de encontrar un nodo para la inserción y eliminación, la complejidad amortizada de las operaciones de reestructuración del árbol es constante. Agregar o eliminar el nodo en sí es un tiempo constante, la cantidad de rotaciones es siempre como mucho constante y se puede demostrar que la cantidad total de cambios de rango en los nodos es lineal en el número de inserciones y eliminaciones.
Estructuras relacionadas
WAVL árboles están estrechamente relacionados con los dos árboles AVL y árboles rojo-negro . Cada árbol AVL puede tener rangos asignados a sus nodos de una manera que lo convierte en un árbol WAVL. Y cada árbol WAVL puede tener sus nodos de color rojo y negro (y sus rangos reasignados) de una manera que lo convierta en un árbol rojo-negro. Sin embargo, algunos árboles WAVL no provienen de árboles AVL de esta manera y algunos árboles rojo-negros no provienen de árboles WAVL de esta manera.
Árboles AVL
Un árbol AVL es una especie de árbol de búsqueda binario equilibrado en el que los dos hijos de cada nodo interno deben tener alturas que difieran como máximo en uno. [7] La altura de un nodo externo es cero, y la altura de cualquier nodo interno es siempre uno más el máximo de las alturas de sus dos hijos. Por lo tanto, la función de altura de un árbol AVL obedece a las restricciones de un árbol WAVL, y podemos convertir cualquier árbol AVL en un árbol WAVL usando la altura de cada nodo como su rango. [1] [2]
La diferencia clave entre un árbol AVL y un árbol WAVL surge cuando un nodo tiene dos hijos con el mismo rango o altura. En un árbol AVL, si un nodo x tiene dos hijos de la misma altura h , entonces la altura de x debe ser exactamente h + 1 . Por el contrario, en un árbol WAVL, si un nodo x tiene dos hijos del mismo rango r , entonces el rango de x puede ser r + 1 o r + 2 . Esto se debe a que el rango no es estrictamente igual a la altura en el árbol WAVL. Esta mayor flexibilidad en los rangos también conduce a una mayor flexibilidad en las estructuras: algunos árboles WAVL no se pueden convertir en árboles AVL incluso modificando sus rangos, porque incluyen nodos cuyas alturas de los niños difieren en más de uno. [2] Sin embargo, podemos decir que todos los árboles AVL son árboles WAVL. Los árboles AVL son árboles WAVL sin el tipo de nodo que tiene ambos hijos de diferencia de rango 2. [1]
Si un árbol WAVL se crea solo usando operaciones de inserción, entonces su estructura será la misma que la estructura de un árbol AVL creado por la misma secuencia de inserción, y sus rangos serán los mismos que los rangos del árbol AVL correspondiente. Es solo a través de operaciones de eliminación que un árbol WAVL puede volverse diferente de un árbol AVL. En particular, esto implica que un árbol WAVL creado solo a través de inserciones tiene una altura como máximo. [2]
Árboles rojo-negros
Un árbol rojo-negro es un árbol de búsqueda binario equilibrado en el que cada nodo tiene un color (rojo o negro), que satisface las siguientes propiedades:
- Los nodos externos son negros.
- Si un nodo interno es rojo, sus dos hijos son negros.
- Todas las rutas desde la raíz hasta un nodo externo tienen el mismo número de nodos negros.
Los árboles rojo-negro se pueden definir de manera equivalente en términos de un sistema de rangos, almacenados en los nodos, que satisfacen los siguientes requisitos (diferentes de los requisitos para rangos en árboles WAVL):
- El rango de un nodo externo es siempre 0 y el rango de su padre es siempre 1.
- El rango de cualquier nodo no raíz es igual al rango de su padre o al rango de su padre menos 1.
- No hay dos bordes consecutivos en ninguna ruta raíz-hoja que tengan una diferencia de rango 0.
La equivalencia entre las definiciones basadas en color y en rango se puede ver, en una dirección, coloreando un nodo de negro si su padre tiene un rango mayor y de rojo si su padre tiene el mismo rango. En la otra dirección, los colores se pueden convertir en rangos haciendo que el rango de un nodo negro sea igual al número de nodos negros en cualquier camino a un nodo externo, y haciendo que el rango de un nodo rojo sea igual al de su padre. [8]
Los rangos de los nodos en un árbol WAVL se pueden convertir en un sistema de rangos de nodos, obedeciendo los requisitos de los árboles rojo-negro, dividiendo cada rango por dos y redondeando al número entero más cercano. [9] Debido a esta conversión, para cada árbol WAVL existe un árbol rojo-negro válido con la misma estructura. Porque los árboles rojo-negros tienen una altura máxima, lo mismo ocurre con los árboles WAVL. [1] [2] Sin embargo, existen árboles rojo-negro a los que no se les puede asignar una función de rango de árbol WAVL válida. [2]
A pesar de que, en términos de sus estructuras de árbol, los árboles WAVL son casos especiales de árboles rojo-negro, sus operaciones de actualización son diferentes. Las rotaciones de árboles utilizadas en las operaciones de actualización del árbol WAVL pueden realizar cambios que no estarían permitidos en un árbol rojo-negro, porque de hecho causarían el cambio de color de grandes subárboles del árbol rojo-negro en lugar de realizar cambios de color solo en un solo árbol. camino en el árbol. [2] Esto permite que los árboles WAVL realicen menos rotaciones de árboles por eliminación, en el peor de los casos, que los árboles rojo-negro. [1] [2]
Referencias
- ^ a b c d e f g h i j Goodrich, Michael T .; Tamassia, Roberto (2015), "4.4 Árboles AVL débiles", Diseño y aplicaciones de algoritmos , Wiley, págs. 130-138.
- ^ a b c d e f g h yo j k l m n Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), "Árboles de rango equilibrado" (PDF) , ACM Transactions on Algorithms , 11 (4): Art. 30, 26, doi : 10.1145 / 2689412 , MR 3361215.
- ^ Goodrich y Tamassia (2015) , Sección 2.3 Árboles, págs. 68–83.
- ^ Goodrich y Tamassia (2015) , Capítulo 3 Árboles de búsqueda binaria, págs. 89-114.
- ^ En esto seguimos a Goodrich & Tamassia (2015) . En la versión descrita por Haeupler, Sen & Tarjan (2015) , los nodos externos tienen rango -1. Esta variación hace muy poca diferencia en las operaciones de los árboles WAVL, pero provoca algunos cambios menores en la fórmula para convertir árboles WAVL en árboles rojo-negro.
- ^ a b Goodrich y Tamassia (2015) , Sección 3.1.2 Búsqueda en un árbol de búsqueda binaria, págs. 95–96.
- ^ Goodrich y Tamassia (2015) , Sección 4.2 AVL Trees, págs. 120-125.
- ^ Goodrich y Tamassia (2015) , Sección 4.3 Árboles rojo-negros, págs. 126-129.
- ^ En Haeupler, Sen & Tarjan (2015) la conversión se realiza redondeando hacia abajo, porque los rangos de los nodos externos son −1 en lugar de 0. Goodrich & Tamassia (2015) dan una fórmula que también redondea hacia abajo, pero debido a que usan el rango 0 para los nodos externos, su fórmula asigna incorrectamente el rango rojo-negro 0 a los nodos internos con rango WAVL 1.