Árbol WAVL

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 se compara repetidamente k con el dato almacenado en cada nodo a lo largo de una ruta desde la raíz. Si k es menor que el valor en el nodo, se sigue la ruta hacia el hijo izquierdo, o hacia el hijo derecho, si k es mayor. Cuando se alcanza un nodo con un valor igual a k , o un nodo externo, la búsqueda finaliza. ^{[ 6 ]}

Si la búsqueda se detiene en un nodo interno, se ha encontrado la clave k . Si, por el contrario, la búsqueda se detiene en un nodo externo, entonces se ha encontrado la posición donde se insertaría k (si se insertara). ^{[ 6 ]}

La inserción de un nodo interno con clave k en un árbol WAVL requiere una búsqueda de k en el árbol, que finaliza en un nodo externo; luego, la sustitución de dicho nodo externo por el nuevo nodo interno con dos hijos externos; y, finalmente, el reequilibrio del árbol. El reequilibrio puede realizarse de arriba hacia abajo o de abajo hacia arriba, ^{[ 2 ]} pero la versión de abajo hacia arriba 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 la inserción, la diferencia de rango entre el padre y el nodo era de 1 o 2, pero esta se ha reducido en 1 debido a que el subárbol con raíz 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 el reequilibrio con el antiguo padre como nuevo nodo.

Finalmente, con diferencias de rango de 0 y 2 para el nodo y su hermano, una o dos rotaciones del árbol, con los ajustes correspondientes a dichas diferencias, pueden restablecer el equilibrio. El hijo intermedio del nodo es aquel cuya clave se encuentra entre las claves del nodo y su padre. Si la diferencia de rango entre ese hijo y el nodo es 2, se rota el árbol para subir el nodo y bajar el padre, y luego se degrada al padre (reduciendo su rango mediante el ajuste de las diferencias de rango a su alrededor), restableciéndose así el equilibrio. En caso contrario, se rota el árbol para subir el hijo y bajar el nodo, y luego se vuelve a rotar para subir el hijo y bajar el padre. Se promueve al hijo, se degradan el nodo y el padre, y se restablece el equilibrio.

Así, en resumen, el procedimiento de inserción consiste en una búsqueda, la creació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 del árbol. ^{[ 1 ] [ 2 ]}

Para eliminar un nodo interno de un árbol WAVL, se procede a la eliminación mediante búsqueda binaria . Para un nodo interno sin hijos externos, esto implica encontrar su sucesor en el árbol, intercambiarlo con su sucesor y, finalmente, eliminarlo de su nueva posición, donde su hijo izquierdo es necesariamente un nodo externo. Para eliminar un nodo interno con un hijo externo, se reemplaza 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 de 1 o 2, pero esa diferencia ha aumentado 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 de nodo interno 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, se degrada al padre (disminuyendo su rango al disminuir las diferencias de rango entre él y cada uno de sus hijos) y se continúa reequilibrando con el antiguo padre como nuevo nodo. De lo contrario, si los dos hijos del hermano tienen diferencias de rango de 2 con el hermano, se degradan el padre y el hermano y se continúa reequilibrando con el antiguo padre como nuevo nodo.

Finalmente, con diferencias de rango de 3 y 1 para el nodo y el hermano, y con el hermano teniendo un hijo con diferencia de rango 1, una o dos rotaciones del árbol, con los ajustes asociados a las diferencias de rango, pueden restaurar 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, como mínimo, y dos veces, si es necesario para evitar violar la propiedad de 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 de nuevo 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 del árbol.[1][2]

Vale la pena comparar el resultado de una eliminación que provocaría rotaciones en múltiples niveles en un árbol AVL con los cambios de rotación y 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.

Un árbol AVL es un tipo de árbol de búsqueda binaria balanceado en el que las alturas de los dos hijos de cada nodo interno deben diferir 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 con la misma altura h , entonces la altura de x debe ser exactamente h + 1. En cambio, en un árbol WAVL, si un nodo x tiene dos hijos con el 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 un árbol WAVL. Esta mayor flexibilidad en los rangos también conlleva una mayor flexibilidad en las estructuras: algunos árboles WAVL no se pueden convertir en árboles AVL ni siquiera modificando sus rangos, porque incluyen nodos cuyas alturas de 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 de 2. ^{[ 1 ]}

Si un árbol WAVL se crea solo mediante operaciones de inserción, su estructura será la misma que la de un árbol AVL creado con 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 diferenciarse de un árbol AVL. En particular, esto implica que un árbol WAVL creado solo mediante inserciones tiene una altura máxima de .${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$. ^{[ 2 ]}

Un árbol rojo-negro es un árbol de búsqueda binaria 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.
• Todos los caminos desde la raíz hasta un nodo externo tienen el mismo número de nodos negros.

Los árboles rojo-negro pueden definirse de forma equivalente en términos de un sistema de rangos, almacenado en los nodos, que satisface los siguientes requisitos (diferentes de los requisitos para los rangos en los árboles WAVL):

• El rango de un nodo externo siempre es  0 y el rango de su padre siempre es  1.
• El rango de cualquier nodo que no sea la raíz es igual al rango de su padre o al rango de su padre menos  1.
• No hay dos aristas consecutivas en ningún camino raíz-hoja que tengan una diferencia de rango  de 0.

La equivalencia entre las definiciones basadas en color y en rango se puede observar, en un sentido, coloreando un nodo de negro si su padre tiene un rango mayor y de rojo si su padre tiene el mismo rango. En el otro sentido, 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 hacia 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, que cumpla con los requisitos para los árboles rojo-negro, 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-negro tienen una altura máxima${\displaystyle 2\log _{2}n}$, lo mismo es cierto para 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 su estructura arbórea, los árboles WAVL son casos especiales de árboles rojo-negro, 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, ya que, en efecto, provocarían el cambio de color de grandes subárboles del árbol rojo-negro en lugar de realizar cambios de color solo en una única ruta del á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-negro. ^{[ 1 ] [ 2 ]}