Inserción En Un Árbol Avl

Inserción en un árbol AVL
La inserción de un elemento en un árbol AVL es idéntica que en un árbol binario de búsqueda, la diferencia se encuentra en la comprobación que hay que realizar posteriormente en los árboles AVL.
En un árbol AVL tras realizar la inserción hay que comprobar que se sigue manteniendo la condición de equilibrio, o lo que es lo mismo, que la altura del subárbol izquierdo yla del subárbol derecho difieran en una unidad o sean iguales. Si se produce un desequilibrio hay que reequilibrar la estructura para que siga siendo un árbol AVL.
Vamos a ver los mecanismos de reequilibrado de los árboles AVL:
Rotación simple.

El nodo insertado es el marcado con una X. Esta inserción provoca un desequilibro en el nodo B, que se soluciona con esta rotación.
Rotación doble.El nodo insertado puede ser una de las dos X, provocando el desequilibrio en el nodo C.
Vamos a ver dos ejemplos reales:
Rotación simple.

Rotación doble.

Ejemplo:
void insertar (AVLTree ** t, int x);
/* inserta x en el árbol en un tiempo O(log(n)) peor caso. */
void
insertar (AVLTree ** t, int x)
{
if (es_vacio (*t))
*t = hacer (x, vacio (), vacio ()); /* altura actualizadaautomáticamente */
else
{
if (x < raiz (*t))
insertar (&(*t)->izq, x);
else
insertar (&(*t)->der, x);
balancear (t);
actualizar_altura (*t);
}
}
Eliminación sobre árboles AVL

La estrategia para diseñar el algoritmo de eliminación sobre árboles AVL es la misma a que para la inserción: Se utiliza el mismo algoritmo que sobre árboles binarios de búsqueda, pero en cadarecursión se detectan y corrigen errores por medio de balancear() y se actualiza la altura del nodo actual.
Recordamos un poco la idea del algoritmo de eliminación sobre árboles binarios de búsqueda. Primero se recorre el árbol para detectar el nodo a eliminar. Una vez hecho esto hay tres casos a diferenciar por su complejidad:
• Si dicho nodo es una hoja procedemos a eliminarlos de inmediato, sin más.• Si dicho nodo tiene un sólo hijo, el nodo puede eliminarse después de ajustar un apuntador del padre para saltar el nodo.
Eliminación de un nodo (7) con un sólo hijo.

• Si dicho nodo tiene dos hijos el caso es un poco más complicado. Lo que se estila hacer (y que de hecho se hace en el algoritmo gracias a la función auxiliar eliminar_min()) reemplazar el nodo actual por el menor nodo desu subárbol derecho (y luego eliminar éste).

Ejemplo:
void eliminar (AVLTree ** t, int x);
/* elimina x del árbol en un tiempo O(log(n)) peor caso.
Precondición: existe un nodo con valor x en el árbol
t. */
int eliminar_min (AVLTree ** t);
/* Función auxiliar a eliminar(). Elimina el menor nodo del árbol
*t devolviendo su contenido (el cual no se libera de memoria). Se actualizan lasalturas de los nodos.
Precondición: !es_vacio(*t) */

• Si dicho nodo tiene dos hijos el caso es un poco más complicado. Lo que se estila hacer (y que de hecho se hace en el algoritmo gracias a la función auxilia eliminar_min()) reemplazar el nodo actual por el menor nodo de su subárbol derecho (y luego eliminar éste).

Ejemplo:

void eliminar (AVLTree ** t, int x);
/* elimina x del árbol enun tiempo O(log(n)) peor caso.
Precondición: existe un nodo con valor x en el árbol t. */
int eliminar_min (AVLTree ** t);
/* Función auxiliar a eliminar(). Elimina el menor nodo del árbol
*t devolviendo su contenido (el cual no se libera de memoria). Se actualizan las alturas de los nodos.
Precondición:!es_vacio(*t) */
Precondición: !es_vacio(*t) */

void
eliminar (AVLTree ** t, int x)
{AVLTree *aux;
if (x < raiz (*t))
eliminar (&(*t)->izq, x);
else if (x > raiz (*t))
eliminar (&(*t)->der, x);
else /* coincidencia! */
{
if (es_vacio (izquierdo (*t)) && es_vacio (derecho (*t)))
{/* es una hoja */
free (*t);
(*t) = vacio();
}
else if (es_vacio (izquierdo (*t)))
{/* subárbol izquierdo vacio */
aux = (*t);
(*t) = (*t)->der;
free...