Definición
La operación de Inserción en un AVL se realiza de la misma forma que en un Árbol Binario de Búsqueda para mantener la propiedad de orden. La diferencia se encuentra en la verificación que hay que realizar posteriormente en cuanto a la propiedad de balanceo. Como esta operación modifica la estructura, entonces, luego de eliminar el elemento se debe comprobar si el árbol se mantiene balanceado; de no estarlo se debe restaurar dicha propiedad. A diferencia de lo que ocurre al insertar un elemento, en donde es suficiente sólo una rotación para restaurar el balanceo del árbol, en la eliminación puede ser necesario aplicar más de una, en el peor de los casos, tantas como la altura del árbol.
Proceso de eliminación:
- Buscar la posición en donde se encuentra el elemento a eliminar (de la misma forma que en un Árbol Binario de Búsqueda).
- Eliminar el elemento con el mismo procedimiento que en el Árbol Binario de Búsqueda.
- Retroceder en el camino obtenido en el paso 1, verificando el balanceo de los nodos, rebalanceando si fuera necesario y actualizando las alturas. Recordar que un árbol no está balanceado si para alguno de sus nodos, la diferencia de altura de sus subárboles es igual a 2.
Veamos en un ejemplo los pasos del proceso de eliminación: