Rotaciones dobles

Hemos visto cómo restaurar la propiedad de equilibrio cuando se presentan desequilibrios "hacia la izquierda" o "hacia la derecha" luego de realizar inserciones en un árbol AVL. Sin embargo y como veremos, pueden ocurrir "desequilibrios en zig-zag", es decir desequilibios que no son ni a la derecha ni a la izquierda como es el caso de los árboles de Figure 10.

Figure 10. Ejemplos de "desequilibrios" en los cuales no funciona la rotación simple.

En estos casos se aplica otro tipo de rotación denominado rotación doble la cual, análogamente a la rotación simple, puede ser izquierda o derecha según el caso.

En realidad, la rotación doble constará de dos rotaciones simples. El caso general de la rotación doble izquierda en un árbol AVL se puede observar en Figure 11.

Figure 11. Rotación doble izquierda

La rotación doble derecha es el proceso inverso a la rotación doble izquierda.

Dado que, como vimos, una rotación doble es en realidad dos rotaciones simples, podemos implementar la función para la rotación doble tan sólo utilizando rotar_s vista en the Section called Implementación de la rotación simple: lo cual se hace a continuación:

void rotar_d (AVLTree ** t, bool izq);                      /* realiza una rotación doble. Funciona análogamente a    rotar_s(). */   void rotar_d (AVLTree ** t, bool izq)                          

{   if (izq)       /* rotación izquierda */     {       rotar_s (&(*t)->izq, false);       rotar_s (t, true);     }   else       /* rotación derecha */     {       rotar_s (&(*t)->der, true);       rotar_s (t, false);     }    /* la actualización de las alturas se realiza en las rotaciones      simples */ }

Declaración de la función rotar_d(); debería ir en un archivo de cabecera.

Los parámetros de rotar_d() son análogos a los de rotar_s() vistos en the Section called Implementación de la rotación simple:.