3.3.2. Operación de eliminación en un AVL.
La eliminación de un nodo es más compleja, ya que puede ser necesario balancear a varios niveles.
Buscar el elemento a eliminar en el árbol:
- Si es un nodo terminal (hoja) se elimina directamente.
- Si el nodo eliminado sólo tiene un hijo, conectar el padre del nodo eliminado con ese hijo.
- Si el nodo eliminado tiene dos subárboles, escoger el nodo más a la derecha del subárbol izquierdo (o el más a la izquierda del subárbol derecho).
Al eliminar un nodo, ir al nodo padre (recursivamente). Comprobar si cumple la condición de balanceo. En caso negativo comprobar en cual de las 3 posibles situaciones nos encontramos (suponemos que se ha eliminado en el subárbol izquierdo).