Árbol AVL

En un árbol binario , el factor de equilibrio de un nodo X se define como la diferencia de altura.

${\displaystyle \mathrm {BF} (X):=\mathrm {Altura} (\mathrm {Subárbol derecho} (X))-\mathrm {Altura} (\mathrm {Subárbol izquierdo} (X))}$^{[ 6 ] : 459}

de sus dos subárboles hijos enraizados por el nodo X.

Un árbol binario se define como un árbol AVL si

${\displaystyle \mathrm {BF} (X)\in \{-1,0,1\}}$

se cumple para cada nodo X en el árbol.

Un nodo X con${\displaystyle \mathrm {BC} (X)<0}$se llama "de izquierda a derecha", uno con${\displaystyle \mathrm {BF} (X)>0}$se llama "pesado hacia la derecha" y uno con${\displaystyle \mathrm {BF} (X)=0}$A veces se le llama simplemente "equilibrado".

Los factores de equilibrio se pueden mantener actualizados conociendo los factores de equilibrio anteriores y el cambio de altura; no es necesario conocer la altura absoluta. Para almacenar la información de equilibrio AVL, dos bits por nodo son suficientes. ^{[ 7 ]}

La altura${\displaystyle h}$(contado como el número máximo de niveles) de un árbol AVL con${\displaystyle n}$Los nodos se encuentran en el intervalo: ^{[ 6 ] : 460}

${\displaystyle \log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b}$

dónde${\displaystyle \varphi$ :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}   es la proporción áurea y${\displaystyle b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.}$ Esto se debe a que un árbol AVL de altura${\displaystyle h}$contiene al menos${\displaystyle F_{h+2}-1}$nodos donde${\displaystyle \{F_{n}\}_{n\in \mathbb {N} }}$es la secuencia de Fibonacci con los valores semilla${\displaystyle F_{1}=F_{2}=1.}$

La búsqueda de una clave específica en un árbol AVL se puede realizar de la misma manera que en cualquier árbol de búsqueda binaria balanceado o desbalanceado . ^{[ 8 ] : cap. 8} Para que la búsqueda funcione eficazmente, debe emplear una función de comparación que establezca un orden total (o al menos un preorden total ) en el conjunto de claves. ^{[ 9 ] : 23} El número de comparaciones necesarias para una búsqueda exitosa está limitado por la altura h y para una búsqueda fallida es muy cercano a h , por lo que ambas están en O(log n ) , donde n es el número de nodos en el árbol. ^{[ 10 ] : 216}

Como operación de solo lectura, el recorrido de un árbol AVL funciona de la misma manera que en cualquier otro árbol binario. Al explorar los n nodos del árbol, cada enlace se visita exactamente dos veces: una visita hacia abajo para entrar en el subárbol enraizado por ese nodo y otra visita hacia arriba para salir del subárbol de ese nodo después de haberlo explorado.

Una vez que se ha encontrado un nodo en un árbol AVL, se puede acceder al nodo siguiente o anterior en tiempo constante amortizado . ^{[ 11 ] : 58} Algunos casos de exploración de estos nodos "cercanos" requieren recorrer hasta h ∝ log( n ) enlaces (particularmente cuando se navega desde la hoja más a la derecha del subárbol izquierdo de la raíz hasta la raíz o desde la raíz hasta la hoja más a la izquierda del subárbol derecho de la raíz; en el árbol AVL de la figura 1, navegar desde el nodo P hasta el siguiente nodo a la derecha Q toma 3 pasos). Dado que hay n −1 enlaces en cualquier árbol, el costo amortizado es 2×( n −1)/ n , o aproximadamente 2.

Al insertar un nodo en un árbol AVL, se sigue inicialmente el mismo proceso que al insertarlo en un árbol de búsqueda binaria . Si el árbol está vacío, el nodo se inserta como raíz. Si el árbol no está vacío, se recorre el árbol desde la raíz y, recursivamente, se busca la ubicación para insertar el nuevo nodo. Este recorrido se guía por la función de comparación. En este caso, el nodo siempre reemplaza una referencia nula (izquierda o derecha) de un nodo externo en el árbol; es decir, el nodo se convierte en hijo izquierdo o derecho del nodo externo.

Tras esta inserción, si un árbol se desequilibra, solo los ancestros del nodo recién insertado se desequilibran. Esto se debe a que solo esos nodos ven alterados sus subárboles. ^{[ 12 ]} Por lo tanto, es necesario comprobar la coherencia de cada uno de los ancestros del nodo con las invariantes de los árboles AVL: esto se denomina "retroceso". Esto se logra considerando el factor de equilibrio de cada nodo. ^{[ 6 ] : 458–481 [ 11 ] : 108}

Dado que con una sola inserción la altura de un subárbol AVL no puede aumentar en más de uno, el factor de equilibrio temporal de un nodo después de una inserción estará en el rango [–2,+2]. Para cada nodo verificado, si el factor de equilibrio temporal permanece en el rango de –1 a +1 entonces solo es necesaria una actualización del factor de equilibrio y no una rotación. Sin embargo, si el factor de equilibrio temporal es ±2, el subárbol enraizado en este nodo está AVL desequilibrado y se necesita una rotación. ^{[ 9 ] : 52} Con la inserción como muestra el código a continuación, la rotación adecuada reequilibra inmediatamente el árbol perfectamente .

En la figura 1, al insertar el nuevo nodo Z como hijo del nodo X, la altura de ese subárbol Z aumenta de 0 a 1.

Invariante del bucle de retroceso para una inserción

La altura del subárbol enraizado por Z ha aumentado en 1. Ya tiene forma AVL.

Para actualizar los factores de equilibrio de todos los nodos, primero observe que todos los nodos que requieren corrección se encuentran en la ruta de la hoja insertada, desde el nodo hijo hasta el nodo padre. Si se aplica el procedimiento anterior a los nodos a lo largo de esta ruta, comenzando desde la hoja, entonces cada nodo del árbol volverá a tener un factor de equilibrio de -1, 0 o 1.

El rastreo puede detenerse si el factor de equilibrio se vuelve 0, lo que implica que la altura de ese subárbol permanece sin cambios.

Si el factor de equilibrio se convierte en ±1, la altura del subárbol aumenta en uno y es necesario continuar con el rastreo.

Si el factor de equilibrio se convierte temporalmente en ±2, esto debe corregirse mediante una rotación adecuada, tras la cual el subárbol tendrá la misma altura que antes (y su raíz el factor de equilibrio 0).

El tiempo requerido es O(log n ) para la búsqueda, más un máximo de O(log n ) niveles de retroceso ( O(1) en promedio) en el camino de regreso a la raíz, por lo que la operación puede completarse en un tiempo de O(log n ) . ^{[ 9 ] : 53}

Los pasos preliminares para eliminar un nodo son los mismos que para un árbol de búsqueda binaria . En este caso, la eliminación efectiva del nodo en cuestión o del nodo de reemplazo reduce la altura del árbol hijo correspondiente de 1 a 0 o de 2 a 1, si dicho nodo tenía un hijo.

A partir de este subárbol, es necesario comprobar la coherencia de cada uno de los ancestros con las invariantes de los árboles AVL. Esto se denomina "recorrido".

Dado que con una sola eliminación la altura de un subárbol AVL no puede disminuir en más de uno, el factor de equilibrio temporal de un nodo estará en el rango de −2 a +2. Si el factor de equilibrio permanece en el rango de −1 a +1, se puede ajustar de acuerdo con las reglas AVL. Si se convierte en ±2, entonces el subárbol está desequilibrado y necesita ser rotado. (A diferencia de la inserción, donde una rotación siempre equilibra el árbol, después de la eliminación, puede haber BF(Z) ≠ 0 (ver figuras 2 y 3), de modo que después de la rotación simple o doble apropiada la altura del subárbol reequilibrado disminuye en uno, lo que significa que el árbol debe ser reequilibrado nuevamente en el siguiente nivel superior). Los diversos casos de rotaciones se describen en la sección Reequilibrio .

Invariante del bucle de retroceso para una eliminación

La altura del subárbol enraizado por N ha disminuido en 1. Ya tiene forma AVL.

El rastreo puede detenerse si el factor de equilibrio se convierte en ±1 (debe haber sido 0), lo que significa que la altura de ese subárbol permanece sin cambios.

Si el factor de equilibrio se convierte en 0 (debe haber sido ±1), entonces la altura del subárbol disminuye en uno y el rastreo debe continuar.

Si el factor de equilibrio se convierte temporalmente en ±2, esto debe corregirse mediante una rotación adecuada. Dependiendo del factor de equilibrio del nodo hermano Z (el árbol hijo superior en la figura 2), la altura del subárbol disminuye en uno —y el retroceso debe continuar— o no cambia (si Z tiene un factor de equilibrio de 0) y todo el árbol tiene forma AVL.

El tiempo requerido es O(log n ) para la búsqueda, más un máximo de O(log n ) niveles de retroceso ( O(1) en promedio) en el camino de regreso a la raíz, por lo que la operación se puede completar en un tiempo O(log n ) .

Además de las operaciones de inserción, eliminación y búsqueda de elementos individuales, se han definido varias operaciones de conjuntos en árboles AVL: unión , intersección y diferencia de conjuntos . A partir de estas funciones de conjuntos, se pueden implementar operaciones masivas rápidas de inserción o eliminación. Estas operaciones de conjuntos se basan en dos operaciones auxiliares: Split y Join . Con las nuevas operaciones, la implementación de árboles AVL puede ser más eficiente y altamente paralelizable. ^{[ 13 ]}

La función Join, aplicada a dos árboles AVL t ₁ y t ₂ y una clave k, devuelve un árbol que contiene todos los elementos de t ₁ , t ₂ y k . Requiere que k sea mayor que todas las claves de t ₁ y menor que todas las claves de t _2. Si la altura de los dos árboles difiere como máximo en uno, Join simplemente crea un nuevo nodo con el subárbol izquierdo t ₁ , la raíz k y el subárbol derecho t _2. En caso contrario, supongamos que t ₁ es mayor que t ₂ en más de uno (el otro caso es simétrico). Join sigue la columna vertebral derecha de t ₁ hasta un nodo c que está equilibrado con t _2. En este punto, se crea un nuevo nodo con el hijo izquierdo c , la raíz k y el hijo derecho t ₂ para reemplazar a c. El nuevo nodo satisface la invariante AVL y su altura es una unidad mayor que la de c . El aumento de altura puede incrementar la altura de sus ancestros, posiblemente invalidando la invariante AVL de esos nodos. Esto se puede solucionar con una doble rotación si el nodo padre no es válido, o con una rotación simple a la izquierda si el nodo padre no es válido en un nivel superior del árbol. En ambos casos, se restablece la altura para los nodos ancestros posteriores. Por lo tanto, la operación de unión requerirá como máximo dos rotaciones. El coste de esta función es la diferencia de alturas entre los dos árboles de entrada.

Para dividir un árbol AVL en dos árboles más pequeños, uno con valores menores que la clave k y otro con valores mayores que la clave k , primero se traza un camino desde la raíz insertando k en el AVL. Tras esta inserción, todos los valores menores que k se encontrarán a la izquierda del camino, y todos los valores mayores que k se encontrarán a la derecha. Al aplicar la operación Join , todos los subárboles del lado izquierdo se fusionan de abajo hacia arriba utilizando las claves del camino como nodos intermedios para formar el árbol izquierdo, mientras que la parte derecha es asimétrica. El coste de Split es O(log n ) , del orden de la altura del árbol.

La unión de dos árboles AVL t ₁ y t ₂ que representan conjuntos A y B , es un AVL t que representa A ∪ B.

El algoritmo para la intersección o la diferencia es similar, pero requiere la rutina auxiliar Join2 , que es igual a Join pero sin la clave central. Basándose en las nuevas funciones de unión, intersección o diferencia, se puede insertar o eliminar una o varias claves del árbol AVL. Dado que Split llama a Join pero no maneja directamente los criterios de balanceo de los árboles AVL, esta implementación se suele denominar implementación "basada en unión" .

La complejidad de cada uno de la unión, la intersección y la diferencia es${\displaystyle {\text{O}}\left(m\log \left({n \over m}+1\right)\right)}$para árboles AVL de tamaños${\displaystyle m}$y${\displaystyle n\;(\geq m)}$Más importante aún, dado que las llamadas recursivas a la unión, la intersección o la diferencia son independientes entre sí, pueden ejecutarse en paralelo con una profundidad paralela .${\displaystyle {\text{O}}(\log m\log n)}$. ^{[ 13 ]} Cuando${\displaystyle m=1}$La implementación basada en uniones tiene el mismo DAG computacional que la inserción y eliminación de un solo elemento.

Figure 2 shows a Right Right situation. In its upper half, node X has two child trees with a balance factor of +2. Moreover, the inner child t₂₃ of Z (i.e., left child when Z is right child, or right child when Z is left child) is not higher than its sibling t₄. This can happen by a height increase of subtree t₄ or by a height decrease of subtree t₁. In the latter case, also the pale situation where t₂₃ has the same height as t₄ may occur.

The result of the left rotation is shown in the lower half of the figure. Three links (thick edges in figure 2) and two balance factors are to be updated.

Como muestra la figura, antes de una inserción, la capa de hojas se encontraba en el nivel h+1, temporalmente en el nivel h+2 y, tras la rotación, de nuevo en el nivel h+1. En caso de eliminación, la capa de hojas se encontraba en el nivel h+2, donde vuelve a estar cuando t ₂₃ y t ₄ tenían la misma altura. De lo contrario, la capa de hojas alcanza el nivel h+1, por lo que la altura del árbol rotado disminuye.

Fragmento de código para una rotación simple a la izquierda.

nodo * rotar_a_izquierda ( nodo * X , nodo * Z ) {// Z es 2 unidades mayor que su hermanot23 = left_child ( Z ); // Hijo interno de Zhijo_derecho ( X ) = t23 ;si ( t23 != null )padre ( t23 ) = X ;hijo_izquierdo ( Z ) = X ;padre ( X ) = Z ;// 1er caso, BF(Z) == 0,// Esto solo ocurre con la eliminación, no con la inserción:if ( BF ( Z ) == 0 ) { // t23 ha tenido la misma altura que t4BF ( X ) = + 1 ; // t23 ahora es mayorBF ( Z ) = – 1 ; // t4 ahora es menor que X} demás{ // El segundo caso ocurre con la inserción o eliminación:BF ( X ) = 0 ;BF ( Z ) = 0 ;}return Z ; // devuelve la nueva raíz del subárbol rotado}

La figura 3 muestra una situación de derecha a izquierda. En su tercio superior, el nodo X tiene dos árboles hijos con un factor de equilibrio de +2 . Pero a diferencia de la figura 2, el hijo interno Y de Z es más alto que su hermano t4 _. Esto puede ocurrir por la inserción del propio Y o por un aumento de altura de uno de sus subárboles t2 _o t3 ₍ con la consecuencia de que tengan diferente altura) o por una disminución de altura del subárbol t1 _. En este último caso, también puede ocurrir que t2 _y t3 _tengan la misma altura.

El resultado de la primera rotación, la derecha, se muestra en el tercio central de la figura. (Con respecto a los factores de equilibrio, esta rotación no es del mismo tipo que las demás rotaciones simples de AVL, ya que la diferencia de altura entre Y y t ₄ es solo 1). El resultado de la rotación final izquierda se muestra en el tercio inferior de la figura. Se deben actualizar cinco eslabones (bordes gruesos en la figura 3) y tres factores de equilibrio.

Como muestra la figura, antes de una inserción, la capa de hojas estaba en el nivel h+1, temporalmente en el nivel h+2 y después de la doble rotación nuevamente en el nivel h+1. En caso de una eliminación, la capa de hojas estaba en el nivel h+2 y después de la doble rotación está en el nivel h+1, por lo que la altura del árbol rotado disminuye.

Fragmento de código de una doble rotación derecha-izquierda

nodo * rotar_derechaIzquierda ( nodo * X , nodo * Z ) {// Z es 2 unidades mayor que su hermanoY = left_child ( Z ); // Hijo interno de Z// Y es 1 unidad mayor que su hermano/at3 = hijo_derecho ( Y );left_child ( Z ) = t3 ;si ( t3 != null )padre ( t3 ) = Z ;hijo_derecho ( Y ) = Z ;padre ( Z ) = Y ;t2 = left_child ( Y );hijo_derecho ( X ) = t2 ;si ( t2 != null )padre ( t2 ) = X ;hijo_izquierdo ( Y ) = X ;padre ( X ) = Y ;// Primer caso, BF(Y) == 0si ( BF ( Y ) == 0 ) {BF ( X ) = 0 ;BF ( Z ) = 0 ;} else if ( BF ( Y ) > 0 ) {// t3 fue más altoBF ( X ) = – 1 ; // t1 ahora es mayorBF ( Z ) = 0 ;} demás {// t2 fue mayorBF ( X ) = 0 ;BF ( Z ) = + 1 ; // t4 ahora es mayor}BF ( Y ) = 0 ;return Y ; // devuelve la nueva raíz del subárbol rotado}