Proceso de eliminación y balanceo. Ejemplos
Proceso de eliminación de un elemento :
El proceso de eliminación en árboles AVL es igual al de los árboles binarios de búsqueda salvo que una vez eliminado el elemento se debe tener en cuenta si esta eliminación produjo un desbalanceo. Por lo tanto, una vez eliminado el elemento, se debe deshacer el camino tomado verificando que los nodos del camino se encuentran balanceados. En caso de que se detecte uno que no lo esté, se deberá determinar y aplicar la rotación que corresponda. A continuación se describe el proceso para detectar el nodo desbalanceado y la forma de rebalancearlo.
Proceso de balanceo de un nodo :
Dado un nodo, si la diferencia entre las alturas de sus subárboles es igual a 2, hay que determinar cuál de los dos subáboles tiene mayor altura (eso nos va a indicar qué rotación corresponde aplicar: izquierda o derecha), y dentro de ese subárbol determinar nuevamente cuál de sus hijos tiene más altura (eso nos va a indicar si la rotación será simple o doble). Visto en pseudocódigo sería:
si ( altura subárbol izquierdo del nodo - altura subárbol derecho del nodo = 2 )
entonces si (altura subárbol izquierdo del subárbol izquierdo del nodo >= altura subárbol derecho del subárbol izquierdo del nodo)
entonces hacer una Rotacion Simple Izquierda sobre el nodo
sino hacer una Rotacion Doble Izquierda sobre el nodo
si ( altura subárbol derecho del nodo - altura subárbol izquierdo del nodo = 2 )
entonces si ( altura subárbol derecho del subárbol derecho del nodo >= altura subárbol izquierdo del subárbol derecho del nodo )
entonces hacer una Rotación Simple Derecha sobre el nodo
sino hacer una Rotación Doble Derecha sobre el nodo
retornar nuevo nodo raíz
En los siguientes ejemplos encontrará una animación donde podrá observar detalladamente cada paso del proceso de eliminación donde se utiliza el proceso de balanceo presentado previamente. En cada animación se puede observar cómo detectar el nodo desbalanceado y cómo determinar la rotación a aplicar.