La inserción de un elemento en un árbol AVL es idéntica que en un árbol binario de búsqueda, la diferncia 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 y la 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.
El procedimiento de borrado es el mismo que en el caso de árboles binarios de búsqueda. La diferencia se encuentra en el proceso de reequilibrado posterior. Este proceso es idéntico al que se realiza en la inserción, la única diferencia es que en la inserción tras realizar una rotación el árbol ya estaba equilibrado, mientras que en el borrado puede ser necesario realizar mas de una rotación.
Ejemplo:
Si eliminamos del siguiente árbol el nodo 3, el árbol se desequilibra en el nodo 2.
Tras aplicar una rotación simple, el árbol resultante es:
Otras operaciones
Las operaciones adicionales en un árbol AVl son análogas a las de árboles binarios de búsqueda.
