Eliminar un elemento de un árbol AVL es lo mismo que eliminarlo de un BST, excepto que es posible que sea necesario reequilibrar el árbol. Como se analizó en la Sección Eliminación de elementos de un BST, para eliminar un elemento de un árbol binario, el algoritmo primero localiza el nodo que contiene el elemento. Deje que current apunte al nodo que contiene el elemento en el árbol binario y parent apunte al padre del nodo current. El nodo actual puede ser un hijo izquierdo o un hijo derecho del nodo principal.
Se presentan dos casos al eliminar un elemento.

Caso 1: El nodo actual no tiene un hijo izquierdo, como se muestra en la Figura siguiente (a). Para eliminar el nodo actual, simplemente conecte el nodo principal con el hijo derecho del nodo actual, como se muestra en la Figura siguiente (b). Es posible que la altura de los nodos a lo largo de la ruta desde el nodo principal hasta la raíz haya disminuido. Para asegurarse de que el árbol esté equilibrado, invoque

balancePath(elemento.padre);

Caso 2: El nodo actual tiene un hijo izquierdo. Deje que rightMost apunte al nodo que contiene el elemento más grande en el subárbol izquierdo del nodo actual y parentOfRightMost apunte al nodo padre de rightMost Nodo , como se muestra en la figura siguiente (a). El nodo rightMost no puede tener un hijo derecho, pero puede tener un hijo izquierdo. Reemplace el valor del elemento en el nodo actual con el del nodo rightMost, conecte el nodo parentOfRightMost con el hijo izquierdo del rightMost y elimine el nodo rightMost, como se muestra en la figura siguiente (b).

La altura de los nodos a lo largo de la ruta desde parentOfRightMost hasta la raíz puede haber disminuido. Para asegurarse de que el árbol esté equilibrado, invoque

balancePath(parentOfRightMost);