Rotaciones simples

Veremos a continuación una operación sencilla sobre un árbol binario de búsqueda que conserva el órden en sus nodos y que nos ayudará a restaurar la propiedad de equilibrio de un árbol AVL al efectuar operaciones sobre el mismo que puedan perturbarla.

Figure 3. Árbol antes de la rotación simple

Miremos por un momento el árbol de Figure 3. Dado que este es un árbol de búsqueda se debe cumplir x < y y además todos los nodos del subárbol A deben ser menores que x y y; todos los nodos del subárbol B deben ser mayores que x pero menores que y; y todos los nodos del subárbol C deben ser mayores que y y por lo tanto que x.

En Figure 4 se ha modificado sencillamante el árbol. Como puede verificarse fácilmente por las desigualdades descriptas en el párrafo anterior, el nuevo árbol sigue manteniendo el órden entre sus nodos, es decir, sigue siendo un árbol binario de búsqueda. A esta transformación se le denomina rotación simple (o sencilla).

Figure 4. Árbol luego de la rotación simple

Veamos un ejemplo concreto. Deseamos insertar el número 3 en el árbol de enteros de Figure 5. La inserción se muestra punteada en Figure 6. Sin embargo, como puede verse, la inserción a provocado la pérdida de la propiedad de equilibrio del árbol ya que dicha propiedad no se cumple en el nodo marcado con rojo. ¿Qué hacemos para recomponer dicha pripiedad? Simplemente realizamos una rotación simple. En este caso se dice que la rotación es izquierda ya que la "pérdida de equilibrio se produce hacia la izquierda. En Figure 7 puede verse el árbol luego de la rotación: la propiedad de equilibrio ha sido reestablecida. Como mostramos atrás, la rotación conserva el orden entre los nodos, por lo que podemos afirmar que este último árbol si es AVL.

Figure 5. Árbol AVL

Figure 6. Árbol luego de la inserción: pérdida de la propiedad de equilibrio marcada con rojo.

Figure 7. Reestablecimiento de la propiedad de equilibrio mediante una rotación simple sobre el nodo de valor 5.

Como podemos observar, el resultado luego de la rotación es un árbol AVL: posee tanto el órden correcto de un árbol de búsqueda entre sus nodos y la propiedad de equilibrio. En este caso el "desequilibrio" en el árbol con raíz 5 era enteramente hacia la izquierda y por lo tanto, como ya dijimos, la rotación efectuada se denomina rotación simple izquierda. En el caso de un "desequilibrio" hacia la derecha, la rotación es análoga y se denomina rotación simple derecha. En Figure 8 se ven dos árboles: el primero tiene un "desequilibrio hacia la derecha" marcado en rojo y el segundo es el resultado de aplicar una rotación simple derecha.

Figure 8. Ejemplo de reestablecimiento de propiedad de equilibrio gracias a una rotación simple derecha.

Ilustración de la operación rotación simple. en Figure 9 se ilustra la operación rotación simple. Los arcos de colores son los que se eliminan o agregan, según sea la rotación izquierda o derecha.

Figure 9. Rotación simple

Implementación de la rotación simple:

Declaración de la función rotar_s(). Esta declaración y el siguiente comentario deberían ir en el archivo de cabecera, interfaz del tipo abstracto árbol AVL con el usuario.

Un breve comentario que explica lo que hace la función, los parámetros que acepta y las precondiciones que éstos deben cumplir para que la función se ejecute correctamente.

Como el programador de C más experimentado puede ver, el paso a la función es el paso por referencia clásico en C. Lo que se pasa no es un puntero a la raiz del árbol sino la dirección de dicho puntero. De esta manera, dentro de la función podremos cambiar la misma raiz si es necesario (lo que justamente hacemos en las rotaciones).

También se acepta como segundo parámetro un valor boleano que determina si la rotación simple a efectuar sobre el árbol es izquierda o derecha.