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.

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.

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 */
}