Consideraciones del proceso de eliminación
La operación de eliminación podría destruir la propiedad de balanceo del árbol AVL
Problema: Desbalanceo de nodos
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. Veamos que sucede en los siguientes casos:
Caso b: Si las diferencias de las alturas es igual a 1, eliminando en el subárbol con menor altura, se produciría un desbalanceo. Esto pasaría por ejemplo, si se eliminara en el subárbol X. Tener en cuenta que una situación simétrica se produce si el subárbol de menor altura fuera el subárbol Y.
|
Chequeo las alturas de los hijos de K1 y noto que está desbalanceado: Como la diferencia entre las alturas de los subárboles derecho e izquierdo de K1 es igual a 2, K1 se desbalanceó => Es necesario rebalancearlo para reestablecer la propiedad de balanceo de K1. ¿Qué rotación se debe aplicar?
Como la altura del subárbol derecho de K2 es mayor o igual que la altura del subárbol izquierdo de K2 entonces se debe aplicar una Rotación Simple Derecha sobre K1 (RSD(K1)).
|
|
|
---------------------------------------------------------------------------------------------------------- |
|
|
Chequeo las alturas de los hijos de K2 y noto que está desbalanceado: Como la diferencia entre las alturas de los subárboles izquierdo y derecho de K2 es igual a 2, K2 se desbalanceó => Es necesario rebalancearlo para reestablecer la propiedad de balanceo de K2. ¿Qué rotación se debe aplicar? Como la altura del subárbol izquierdo de K1 es mayor o igual que la altura del subárbol derecho de K1 entonces se debe aplicar una Rotación Simple Izquierda sobre K2 (RSI(K2)). |
|
|
---------------------------------------------------------------------------------------------------------- |
|
|
Chequeo las alturas de los hijos de K1 y noto que está desbalanceado: Como la diferencia entre las alturas de los subárboles derecho e izquierdo de K1 es igual a 2, K1 se desbalanceó => Es necesario rebalancearlo para reestablecerla propiedad de balanceo de K1. ¿Qué rotación se debe aplicar? Como la altura del subárbol derecho de K1 es mayor que la altura del subárbol izquierdo de K1 entonces se debe aplicar una Rotación sobre el subárbol Derecho de K1. Como la altura del subárbol izquierdo de K3 es mayor que la del derecho, entonces se aplica una Rotación Doble Derecha sobre K1 (RDD(K1)). |
|
|
---------------------------------------------------------------------------------------------------------- |
|
|
Chequeo las alturas de los hijos de K3 y noto que está desbalanceado: Como la diferencia entre las alturas de los subárboles izquierdo y derecho de K3 es igual a 2, K3 se desbalanceó => Es necesario rebalancearlo para reestablecer la propiedad de balanceo.
¿Qué rotación se debe aplicar? Como la altura del subárbol izquierdo de K3 es mayor que la altura del subárbol derecho de K3 entonces se debe aplicar una Rotación sobre el subárbol Izquierdo de K3. Como la altura del subárbol derecho de K1 es mayor que la del izquierdo, entonces se aplica una Rotación Doble Izquierda sobre K3 (RDI(K3)). |
 |
