En informática , un árbol WAVL o árbol AVL débil es un árbol binario de búsqueda autoequilibrado . Los árboles WAVL reciben su 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-negros , que caen todos en un marco común de árboles equilibrados de rango . Al igual que otros árboles binarios de búsqueda equilibrados, los árboles WAVL pueden manejar operaciones de inserción, eliminación y búsqueda en 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-negros. Una ventaja de los árboles AVL sobre los árboles rojo-negros es que son más equilibrados: tienen una altura máxima (para un árbol con n elementos de datos, donde es la proporción áurea ), mientras que los árboles rojo-negros tienen una altura máxima mayor, . Si se crea un árbol WAVL utilizando 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-negros tienen la ventaja sobre los árboles AVL de 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 del árbol , mientras que los árboles rojo-negros tienen operaciones de eliminación más simples que utilizan solo un número constante de rotaciones del árbol. Los árboles WAVL, como los árboles rojo-negros, utilizan solo un número constante de rotaciones del árbol, y la constante es incluso mejor que para los árboles rojo-negros. [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-negros como un tipo de árbol de rango equilibrado. [2]
Los distintos árboles binarios de búsqueda tienen distintos algoritmos de inserción/eliminación y de balanceo, lo que dificulta su estudio sistemático. Los autores de Haeupler, Sen y Tarjan (2015) presentan el marco de árboles de balanceo de rangos para unificar el estudio de los árboles binarios de búsqueda mediante la definición del árbol binario de rangos, y cada árbol binario de búsqueda se rige por restricciones específicas aplicadas a la función de rangos. Nótese que el marco no especifica los algoritmos en los que se implementan estos árboles.
Un árbol binario de rango es un árbol binario en el que cada nodo x está asociado con un rango r(x). Por convención, el nodo vacío tiene rango -1. Para un nodo x que no es la raíz, la diferencia de rango es , y dicho nodo se denomina i-hijo si la diferencia de rango es i. Un nodo es de tipo si la diferencia de rango de su hijo izquierdo y su hijo derecho es i y j (sin tener en cuenta el orden).
Con esto, podemos definir reglas adicionales, que corresponden a diferentes árboles:
Hasta ahora todas estas reglas son simétricas para el nodo izquierdo y el nodo derecho. Al romper dichas simetrías, se dan lugar a otras reglas:
El árbol AVL débil se define mediante la regla AVL débil:
Tenga en cuenta que el árbol AVL débil generaliza el árbol AVL al permitir nodos de tipo 2,2. Una prueba sencilla muestra que un árbol AVL débil se puede colorear de forma que represente un árbol rojo-negro. Por lo tanto, en cierto sentido, el árbol AVL débil combina las propiedades del árbol AVL y del árbol rojo-negro.
Al igual que los árboles binarios de búsqueda 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 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 lleva datos y tiene un vínculo solo con 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 son x mismo. Los nodos externos forman las hojas del árbol. [3] Los elementos de datos están dispuestos 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 binarios de búsqueda 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 lejano. 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]
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 balanceada. Se comienza en la raíz del árbol y luego se compara repetidamente k con el elemento de datos almacenado en cada nodo de 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 cambio, siguiendo la ruta hacia el hijo derecho cuando k es mayor que el valor en el nodo. Cuando se llega a un nodo con un valor igual a k , o se llega a 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, se ha encontrado la posición en la que se insertaría k (si se insertara). [6]
Para insertar un nodo interno con clave k en un árbol WAVL es necesario buscar k en el árbol, terminar en un nodo externo, luego reemplazar ese nodo externo con el nuevo nodo interno con dos hijos externos y, finalmente, reequilibrar el á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 padre, 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 ha crecido. 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, se promueve al padre (se aumenta su rango incrementando las diferencias de rango entre él y cada uno de sus hijos) y se continúa con el reequilibrio con el padre anterior como el nuevo nodo.
Finalmente, con diferencias de rango de 0 y 2 para el nodo y el hermano, una o dos rotaciones del árbol, con 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 el nodo es 2, gire para mover el nodo hacia arriba en el árbol y el padre hacia abajo, luego degrade el padre (reduzca su rango ajustando las diferencias de rango a su alrededor) y se restablecerá el equilibrio. De lo contrario, gire para mover al hijo hacia arriba y al nodo hacia abajo, luego gire nuevamente para mover al hijo hacia arriba y al padre hacia abajo. Ascienda al hijo, degrade el nodo y el padre, y se restablecerá el equilibrio.
Por lo tanto, 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 árbol. [1] [2]
Para eliminar un nodo interno de un árbol WAVL, se comienza con la eliminación de un árbol de búsqueda binaria común . En el caso de un nodo interno sin un hijo externo, esto significa buscar su sucesor en el árbol, intercambiar el nodo con su sucesor y luego eliminar el nodo de su nueva posición en el á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 ascendente comienza considerando la diferencia de rango entre un nodo (inicialmente, el nodo que reemplazó al nodo eliminado) y su padre. Si no hay padre, 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 con raíz en el nodo se ha acortado. Si el padre ahora tiene dos hijos externos, se viola la propiedad del nodo interno porque el padre tiene rango 2. El padre debe degradarse 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, degrade al padre (reduzca su rango al disminuir las diferencias de rango entre él y cada uno de sus hijos) y continúe el reequilibrio con el padre anterior como el nuevo nodo. De lo contrario, si los dos hijos del hermano tienen diferencias de rango de 2 con el hermano, degrade al padre y al hermano y continúe el reequilibrio con el padre anterior como el nuevo nodo.
Finalmente, con diferencias de rango de 3 y 1 para el nodo y el hermano, y con un hermano que tiene un hijo con una diferencia de rango de 1, una o dos rotaciones de árbol, con 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 clave de la sobrina se encuentra entre las claves del padre y el hermano, y la clave del sobrino no. Si la diferencia de rango entre el hermano y el sobrino es 1, rote para mover al hermano hacia arriba y al padre hacia abajo, promueva al hermano y degrade 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 el hermano y el sobrino como 1, rote para mover a la sobrina hacia arriba y al hermano hacia abajo, rote nuevamente para mover a la sobrina hacia arriba y al padre hacia abajo, promueva a la sobrina dos veces, degrade al hermano una vez y degrade al 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 nodos nuevos, un número logarítmico de cambios de rango y un número constante de rotaciones de árbol.[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, se eliminó el nodo con valor 12, seguido de una rotación a la derecha y la asignación de rango cero a todos los nodos externos.
Cada búsqueda, inserción o eliminación en un árbol WAVL implica seguir una única ruta en el árbol y realizar una cantidad constante de pasos para cada nodo de la ruta. En un árbol WAVL con n elementos que solo ha sufrido inserciones, la longitud máxima de la ruta es . Si pueden haberse producido tanto inserciones como eliminaciones, la longitud máxima de la ruta es . Por lo tanto, en cualquier caso, el tiempo en el peor de los casos 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 inserción y eliminación, la complejidad amortizada de las operaciones de reestructuración del árbol es constante. La adición o eliminación del nodo en sí es un proceso de tiempo constante, la cantidad de rotaciones es siempre, como máximo, 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.
Los árboles WAVL están estrechamente relacionados con los árboles AVL y los árboles rojo-negros . 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 coloreados en rojo y negro (y sus rangos reasignados) de una manera que lo convierte 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.
Un árbol AVL es un tipo de árbol binario de búsqueda balanceado 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 las restricciones de un árbol WAVL, y podemos convertir cualquier árbol AVL en un árbol WAVL utilizando 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 entre sí, 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 entre sí, 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 pueden convertirse en árboles AVL ni siquiera modificando sus rangos, porque incluyen nodos cuyas alturas de los hijos 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 con una diferencia de rango 2. [1]
Si se crea un árbol WAVL utilizando únicamente operaciones de inserción, su estructura será la misma que la de un árbol AVL creado mediante la misma secuencia de inserción, y sus rangos serán los mismos que los del árbol AVL correspondiente. Solo mediante operaciones de eliminación un árbol WAVL puede llegar a ser diferente de un árbol AVL. En particular, esto implica que un árbol WAVL creado únicamente mediante inserciones tiene una altura máxima de . [2]
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 árboles rojo-negros 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 los rangos en los árboles WAVL):
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 mayor rango 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 ruta 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 a un sistema de rangos de nodos, obedeciendo los requisitos para árboles rojo-negros, dividiendo cada rango por dos y redondeando al 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. Debido a que los árboles rojo-negros tienen una altura máxima de , lo mismo es cierto para los árboles WAVL. [1] [2] Sin embargo, existen árboles rojo-negros a los que no se les puede dar 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-negros, sus operaciones de actualización son diferentes. Las rotaciones de árbol utilizadas en las operaciones de actualización de árboles WAVL pueden realizar cambios que no estarían permitidos en un árbol rojo-negro, porque en efecto provocarían la recoloración de grandes subárboles del árbol rojo-negro en lugar de realizar cambios de color solo en una única ruta en el árbol. [2] Esto permite que los árboles WAVL realicen menos rotaciones de árbol por eliminación, en el peor de los casos, que los árboles rojo-negros. [1] [2]
