6.18. Implementación de un árbol AVL¶
Ahora que hemos demostrado que mantener un árbol AVL en equilibrio va a ser una gran mejora de desempeño, veremos cómo vamos a aumentar el procedimiento para insertar una clave nueva en el árbol. Dado que todas las claves nuevas se insertan en el árbol como nodos hoja y que sabemos que el factor de equilibrio para una hoja nueva es cero, no hay nuevos requisitos para el nodo que se acaba de insertar. Pero una vez que se agrega la hoja nueva, debemos actualizar el factor de equilibrio de su padre. La forma en que esta hoja nueva afecta al factor de equilibrio del padre depende de si el nodo hoja es un hijo izquierdo o un hijo derecho. Si el nuevo nodo es un hijo derecho, el factor de equilibrio del padre se reducirá en uno. Si el nuevo nodo es un hijo izquierdo, entonces el factor de equilibrio del padre se incrementará en uno. Esta relación puede aplicarse recursivamente al abuelo del nuevo nodo, y posiblemente a cada antepasado hasta la raíz del árbol. Dado que se trata de un procedimiento recursivo, examinemos los dos casos base para actualizar los factores de equilibrio:
La llamada recursiva ha llegado a la raíz del árbol.
El factor de equilibrio del padre ha sido ajustado a cero. Usted debe convencerse de que una vez que un subárbol tiene un factor de equilibrio cero, entonces el equilibrio de sus nodos ancestrales no cambia.
Implementaremos el árbol AVL como una subclase de ArbolBinarioBusqueda. Para empezar, reescribiremos el método _agregar y escribiremos un nuevo método auxiliar actualizarEquilibrio. Estos métodos se muestran en el Programa 1. Usted notará que la definición de _agregar es exactamente la misma que en los árboles binarios de búsqueda simples, excepto porque se han incluido llamadas a actualizarEquilibrio en las líneas 7 y 13.
Programa 1
def _agregar(self,clave,valor,nodoActual):
if clave < nodoActual.clave:
if nodoActual.tieneHijoIzquierdo():
self._agregar(clave,valor,nodoActual.hijoIzquierdo)
else:
nodoActual.hijoIzquierdo = NodoArbol(clave,valor,padre=nodoActual)
self.actualizarEquilibrio(nodoActual.hijoIzquierdo)
else:
if nodoActual.tieneHijoDerecho():
self._agregar(clave,valor,nodoActual.hijoDerecho)
else:
nodoActual.hijoDerecho = NodoArbol(clave,valor,padre=nodoActual)
self.actualizarEquilibrio(nodoActual.hijoDerecho)
def actualizarEquilibrio(self,nodo):
if nodo.factorEquilibrio > 1 or nodo.factorEquilibrio < -1:
self.reequilibrar(nodo)
return
if nodo.padre != None:
if nodo.esHijoIzquierdo():
nodo.padre.factorEquilibrio += 1
elif nodo.esHijoDerecho():
nodo.padre.factorEquilibrio -= 1
if nodo.padre.factorEquilibrio != 0:
self.actualizarEquilibrio(nodo.padre)
El nuevo método actualizarEquilibrio es donde se realiza la mayor parte del trabajo. Éste implementa el procedimiento recursivo que acabamos de describir. El método actualizarEquilibrio comprueba primero si el nodo actual está lo suficientemente desequilibrado como para requerir el reequilibrio (línea 16). Si ése es el caso, entonces se realiza el reequilibrio y no se requiere hacer ninguna nueva actualización a los padres. Si el nodo actual no requiere reequilibrio entonces se ajusta el factor de equilibrio del padre. Si el factor de equilibrio del padre no es cero, entonces el algoritmo continúa ascendiendo en el árbol, hacia la raíz, llamando recursivamente a actualizarEquilibrio con el padre como parámetro.
Cuando es necesario reequilibrar el árbol, ¿cómo lo hacemos? El reequilibrio eficiente es la clave para que el árbol AVL funcione bien sin sacrificar el desempeño. Con el fin de reequilibrar un árbol AVL vamos a realizar una o más rotaciones en el árbol.
Para entender lo que es una rotación, veamos un ejemplo muy simple. Considere el árbol mostrado en la mitad izquierda de la Figura 3. Este árbol está desequilibrado con un factor de equilibrio de -2. Para equilibrar este árbol usaremos una rotación a la izquierda alrededor del subárbol con raíz en el nodo A.
Figura 3: Transformación de un árbol desequilibrado usando una rotación a la izquierda¶
Figura 3: Transformación de un árbol desequilibrado usando una rotación a la izquierda
Para realizar una rotación a la izquierda, hacemos esencialmente lo siguiente:
Promover el hijo derecho (B) para que sea la raíz del subárbol.
Mover la raíz antigua (A) para que sea el hijo izquierdo de la nueva raíz.
Si la nueva raíz (B) ya tenía un hijo izquierdo, entonces lo convertimos en el hijo derecho del nuevo hijo izquierdo (A). Nota: Dado que la nueva raíz (B) era el hijo derecho de A, está garantizado que el hijo derecho de A está vacío en este punto. Esto nos permite agregar un nuevo nodo como hijo derecho sin consideraciones adicionales.
A pesar que este procedimiento es conceptualmente bastante sencillo, los detalles del código son un poco complicados ya que tenemos que mover cosas justo en el orden correcto para que todas las propiedades de un Árbol Binario de Búsqueda se conserven. Además debemos asegurarnos de actualizar apropiadamente todos los punteros de los padres.
Veamos un árbol un poco más complicado para ilustrar la rotación a la derecha. El lado izquierdo de la Figura 4 muestra un árbol que es pesado a la izquierda y con un factor de equilibrio de 2 en la raíz. Para realizar una rotación a la derecha, hacemos esencialmente lo siguiente:
Promover el hijo izquierdo (C) para que sea la raíz del subárbol.
Mover la raíz antigua (E) para que sea el hijo drecho de la nueva raíz.
Si la nueva raíz (C) ya tenía un hijo derecho (D), entonces lo convertimos en el hijo izquierdo del nuevo hijo derecho (E). Nota: Como la nueva raíz (C) era el hijo izquierdo de E, está garantizado que el hijo izquierdo de E está vacío en este punto. Esto nos permite agregar un nuevo nodo como hijo izquierdo sin consideraciones adicionales.
Figura 4: Transformación de un árbol desequilibrado usando una rotación a la derecha¶
Figura 4: Transformación de un árbol desequilibrado usando una rotación a la derecha
Veamos el código ahora que usted ha visto las rotaciones y tiene la idea básica de cómo funciona una rotación. El Programa 2 muestra el código para las rotaciones a la derecha y a la izquierda. En la línea 2 creamos una variable temporal para realizar un seguimiento de la nueva raíz del subárbol. Como dijimos antes, la nueva raíz es el hijo derecho de la raíz anterior. Ahora que se ha almacenado una referencia al hijo derecho en esta variable temporal, reemplazamos el hijo derecho de la raíz antigua con el hijo izquierdo de la nueva.
El siguiente paso es ajustar los punteros a los padres de los dos nodos. Si nuevaRaiz tiene un hijo izquierdo entonces el nuevo padre del hijo izquierdo se convierte en la raíz antigua. Al padre de la nueva raíz se le asigna el padre de la raíz antigua. Si la raíz antigua era la raíz de todo el árbol, debemos asignar la raíz del árbol para que apunte a esta nueva raíz. De lo contrario, si la raíz antigua es un hijo izquierdo, entonces cambiamos al padre del hijo izquierdo para que apunte a la nueva raíz; de lo contrario cambiamos al padre del hijo derecho para que apunte a la nueva raíz. (Líneas 10-13). Finalmente asignamos la nueva raíz como padre de la raíz antigua. Esto es un montón de contabilidad complicada, por lo que lo animamos a rastrear el funcionamiento de esta función mientras mira la Figura 3. El método rotarDerecha es simétrico a rotarIzquierda, por lo que dejaremos que usted estudie por sí mismo el código de rotarDerecha.
Programa 2
def rotarIzquierda(self,rotRaiz):
nuevaRaiz = rotRaiz.hijoDerecho
rotRaiz.hijoDerecho = nuevaRaiz.hijoIzquierdo
if nuevaRaiz.hijoIzquierdo != None:
nuevaRaiz.hijoIzquierdo.padre = rotRaiz
nuevaRaiz.padre = rotRaiz.padre
if rotRaiz.esRaiz():
self.raiz = nuevaRaiz
else:
if rotRaiz.esHijoIzquierdo():
rotRaiz.padre.hijoIzquierdo = nuevaRaiz
else:
rotRaiz.padre.hijoDerecho = nuevaRaiz
nuevaRaiz.hijoIzquierdo = rotRaiz
rotRaiz.padre = nuevaRaiz
rotRaiz.factorEquilibrio = rotRaiz.factorEquilibrio + 1 - min(nuevaRaiz.factorEquilibrio, 0)
nuevaRaiz.factorEquilibrio = nuevaRaiz.factorEquilibrio + 1 + max(rotRaiz.factorEquilibrio, 0)
Finalmente, las líneas 16-17 requieren cierta explicación. En estas dos líneas actualizamos los factores de equilibrio de las raíces vieja y nueva. Puesto que todos los otros movimientos están cambiando de lugar subárboles completos, los factores de equilibrio de todos los otros nodos no son afectados por la rotación. Pero, ¿cómo podemos actualizar los factores de equilibrio sin recalcular completamente las alturas de los nuevos subárboles? La siguiente derivación debería convencerlo a usted de que estas líneas son correctas.
Figura 5: Una rotación a la izquierda¶
Figura 5: Una rotación a la izquierda
La Figura 5 muestra una rotación a la izquierda. B y D son los nodos pivotales y A, C, E son sus subárboles. Sea \(h_x\) la altura de un subárbol particular con raíz en el nodo \(x\). Por definición sabemos lo siguiente:
Pero sabemos que la altura antigua de D también puede estar dada por \(1 + max (h_C, h_E)\), es decir, la altura de D es uno más la altura máxima entre aquéllas de sus dos hijos. Recuerde que \(h_C\) y \(h_E\) no han cambiado. Por lo tanto, sustituyamos esto en la segunda ecuación, lo que nos da
\(viejoEquilibrio(B) = h_A - (1 + max(h_C,h_E))\)
y luego restamos las dos ecuaciones. Los siguientes pasos hacen la resta y usan ciertas operaciones algebraicas para simplificar la ecuación de \(nuevoEquilibrio(B)\).
A continuación vamos a mover \(viejoEquilibrio(B)\) al lado derecho de la ecuación y haremos uso del hecho de que \(max(a,b) -c = max(a-c, b-c)\).
Pero, \(h_E - h_C\) es lo mismo que \(-viejoEquilibrio(D)\). Así que podemos usar otra identidad que dice que \(max(-a,-b) = -min(a,b)\). Así entonces, podemos terminar nuestra derivación de \(nuevoEquilibrio(B)\) con los siguientes pasos:
Ahora tenemos todas las partes en términos que reconocemos fácilmente. Si recordamos que B es rotRaiz y D es nuevaRaiz entonces podemos ver que la ecuación anterior corresponde exactamente a la instrucción en la línea 16, o:
rotRaiz.factorEquilibrio = rotRaiz.factorEquilibrio + 1 - min(0,nuevaRaiz.factorEquilibrio)
Una derivación similar nos da la ecuación para el nodo actualizado D, así como los factores de equilibrio después de una rotación a la derecha. Los dejamos como ejercicios para usted.
Ahora usted podría pensar que hemos terminado. Sabemos cómo hacer nuestras rotaciones a izquierda y derecha, y sabemos cuándo debemos hacer una rotación a la izquierda o a la derecha, pero eche un vistazo a la Figura 6. Dado que el nodo A tiene un factor de equilibrio de -2, deberíamos hacer una rotación a la izquierda. Pero, ¿qué sucede cuando hacemos la rotación a la izquierda alrededor de A?
Figura 6: Un árbol desequilibrado que es más difícil de equilibrar¶
Figura 6: Un árbol desequilibrado que es más difícil de equilibrar
La Figura 7 nos muestra que, después de la rotación a la izquierda, estamos ahora desequilibrados en la otra dirección. Si hacemos una rotación a la derecha para corregir la situación, estamos de regreso en la situación con que empezamos.
Figura 7: Después de una rotación a la izquierda el árbol está desequilibrado en la otra dirección¶
Figura 7: Después de una rotación a la izquierda el árbol está desequilibrado en la otra dirección
Para corregir este problema debemos utilizar el siguiente conjunto de reglas:
Si un subárbol necesita una rotación a la izquierda para equilibrarlo, compruebe primero el factor de equilibrio del hijo derecho. Si el hijo derecho es pesado a la izquierda entonces aplique una rotación a la derecha al hijo derecho, seguida por la rotación a la izquierda original.
Si un subárbol necesita una rotación a la derecha para equilibrarlo, compruebe primero el factor de equilibrio del hijo izquierdo. Si el hijo izquierdo es pesado a la derecha, aplique una rotación a la izquierda al hijo izquierdo, seguida por la rotación a la derecha original.
La Figura 8 muestra cómo estas reglas resuelven el dilema que encontramos en la Figura 6 y en la Figura 7. Comenzar con una rotación a la derecha alrededor del nodo C pone el árbol en una posición en la que la rotación a la izquierda alrededor de A reequilibrará el subárbol completo.
Figura 8: Una rotación a la derecha seguida de una rotación a la izquierda¶
Figura 8: Una rotación a la derecha seguida de una rotación a la izquierda
El código que implementa estas reglas se puede encontrar en nuestro método reequilibrar, que se muestra en el Programa 3. La regla número 1 desde arriba es implementada por la instrucción if empezando en la línea 2. La regla número 2 es implementada por la instrucción elif empezando en la línea 8.
Programa 3
1def reequilibrar(self,nodo):
2 if nodo.factorEquilibrio < 0:
3 if nodo.hijoDerecho.factorEquilibrio > 0:
4 self.rotarDerecha(nodo.hijoDerecho)
5 self.rotarIzquierda(nodo)
6 else:
7 self.rotarIzquierda(nodo)
8 elif nodo.factorEquilibrio > 0:
9 if nodo.hijoIzquierdo.factorEquilibrio < 0:
10 self.rotarIzquierda(nodo.hijoIzquierdo)
11 self.rotarDerecha(nodo)
12 else:
13 self.rotarDerecha(nodo)
Las preguntas de discusión le dan a usted la oportunidad de reequilibrar un árbol que requiere una rotación a la izquierda seguida de una rotación a la derecha. Además, las preguntas de discusión le brindan la oportunidad de reequilibrar algunos árboles que son un poco más complejos que el árbol de la Figura 8.
Manteniendo el árbol equilibrado en todo momento, podemos asegurar que el método obtener se ejecutará en un tiempo del orden de \(O(log_2(n))\). Pero la pregunta es ¿a qué costo para nuestro método agregar? Descompongamos esto en las operaciones realizadas por agregar. Puesto que un nuevo nodo se inserta como una hoja, la actualización de los factores de equilibrio de todos los padres requerirá un máximo de \(log_2(n)\) operaciones, una por cada nivel del árbol. Si un subárbol está desequilibrado, se requiere un máximo de dos rotaciones para reequilibrarlo el árbol. No obstante, cada una de las rotaciones funciona en tiempo \(O(1)\), así que incluso nuestra operación agregar seguirá siendo \(O(log_2(n))\).
En este punto hemos implementado un árbol AVL funcional, a menos que usted necesite la capacidad de eliminar un nodo. Dejamos la eliminación del nodo y su posterior actualización y reequilibrio como ejercicio para usted.