Proceso de inserción y balanceo. Ejemplos

Proceso de inserción de un elemento :

El proceso de inserción en árboles AVL es igual al de los árboles binarios de búsqueda salvo que una vez insertado el elemento se debe tener en cuenta si esta inserción produjo un desbalanceo. Por lo tanto, una vez insertado el elemento, se debe deshacer el camino tomado verificando que los nodos del camino se encuentran balanceados. En caso de que se detecte uno que no lo esté, se deberá determinar y aplicar la rotación que corresponda. A continuación se describe el proceso para detectar el nodo desbalanceado y la forma de rebalancearlo.

Proceso de balanceo de un nodo

Dado un nodo, si la diferencia entre las alturas de sus subárboles es igual a 2, hay que determinar cual de los dos subáboles tiene mayor altura (eso nos va a indicar que rotación corresponde, si se debe aplicar una rotacion izquierda o derecha), y dentro de ese subárbol determinar nuevamente cuál de sus hijos tiene más altura (eso nos va a indicar si la rotación será simple o doble).  Visto en pseudocódigo sería:

si la altura subárbol izquierdo -  altura subárbol derecho = 2
    entonces si la altura subárbol izquierdo del subábol izquierdo del nodo  >= altura subárbol izquierdo del subábol derecho
                          entonces hacer una Rotacion Simple Izquierda sobre el nodo
                          sino hacer una Rotacion Doble Izquierda sobre el nodo
 si ( altura subárbol derecho - altura subárbol izquierdo = 2 )
      entonces si la altura subárbol derecho del subárbol derecho del nodo >= altura subárbol derecho del subárbol izquierdo
                           entonces hacer una Rotación Simple Derecha sobre el nodo
                          sino hacer una Rotación Doble Derecha sobre el nodo
retornar nuevo nodo raíz

En los siguientes ejemplos encontrará una animación donde podrá observar detalladamente cada paso del proceso de inserción donde se utiliza el proceso debalanceo presentado previamente. En cada animación se puede observar cómo detectar el nodo desbalanceado y cómo determinar la rotación a aplicar.

  1. Ejemplo de inserción aplicando Rotación Simple Derecha - RSD

  2. Ejemplo de inserción aplicando Rotación Simple Izquierda - RSI

  3. Ejemplo de inserción aplicando Rotación Doble Derecha - RDD