Proceso de inserción y balanceo. Ejemplos
Proceso de inserción de un elemento :
El proceso de inserción en árboles AVL es igual al de los árboles binarios de búsqueda salvo que una vez insertado el elemento se debe tener en cuenta si esta inserción produjo un desbalanceo. Por lo tanto, una vez insertado 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árboles tiene mayor altura (eso nos va a indicar qué rotación corresponde, si se debe aplicar una rotación 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 - altura subárbol derecho = 2 )
entonces si ( altura subárbol izquierdo del subábol izquierdo del nodo >= altura subárbol derecho del subárbol izquierdo )
entonces hacer una Rotación Simple Izquierda sobre el nodo
sino hacer una Rotación Doble Izquierda sobre el nodo
si ( altura subárbol derecho - altura subárbol izquierdo = 2 )
entonces si ( altura subárbol derecho del subárbol derecho del nodo >= altura subárbol izquierdo del subárbol derecho )
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 inserció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.