3.3.1. Operación de inserción en un AVL.
Inserción en un árbol AVL.
- Inserción normal como en los árboles binarios de búsqueda.
- Si la altura del árbol (en cada nodo) no se modifica, acabar.
- Si la altura se incrementa en 1 entonces:
- Si hi = hd, el árbol se desequilibra en altura, pero sigue manteniéndose la condición de balanceo.
- Si hi < hd y la inserción es en el subárbol izquierdo (ó hi > hd e insertamos en el derecho), se han equilibrado los subárboles.
- Si hi > hd y la inserción es en el subárbol izquierdo (ó hi < hd e insertamos en el derecho), es necesario hacer un rebalanceo, ya que la diferencia de alturas aumenta.
El rebalanceo usa una operación de rotación simple un a.b.b.