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 insertar el elemento se debe comprobar si el árbol se mantiene balanceado; de no estarlo se debe restaurar dicha propiedad. Esto se lleva a cabo aplicando sólo una rotación, la que corresponda según la forma que le quedó al árbol.

Proceso de inserción:

1. Buscar la posición en la que debe ser insertado el elemento (de la misma forma que en un Árbol Binario de Búsqueda).
2. Insertar el nuevo nodo con altura en 0.
3. 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 inserción: