ALGORITMOS . ARBOLES BALANCEADOS

Los arboles balanceados surgen con el fin de realizar reacomodos o balanceos después de inserción o eliminación de elementos.

Estos arboles también reciben el nombre de AVL en honor a sus inventores, dos matemáticos rusos, G.M. Aleson – Velskii y E.M. Landis.

Formalmente se define un árbol balanceado como un árbol binario de búsqueda, en el cual se debe cumplir la siguiente condición: para todo nodo T del árbol, la altura de los subárboles izquierdo y derecho no deben diferir en mas de una unidad.

Ejemplo de arboles balanceados:

Observe que si se insertan las claves 10,18,27 en el árbol balanceado A, este pierde el equilibrio. Pero si insertamos la clave 37 o 45, este mantiene su equilibrio o hasta lo mejora.

Ahora si hablamos de la eliminación, si le quitamos las claves 15, 20 o 25, el árbol continua siendo balanceado; incluso se pueden quitar las 3 claves y el árbol no pierde su equilbrio. Pero si se elimina la clave 40 el árbol pierde el equilibrio y es necesario reestructurarlo.

Los arboles balanceados se parecen mucho, en su mecanisco de formación, a los números Fibonacci. El árbol de altura 0 es vacio. El árbol de altura 1 tiene un único nodo, y en general, el numero de nodos del árbol con altura h>1 se calcula aplicando la siguiente formula recursiva.

Kh=Kh-1 + 1 + Kh-2

Donde K indica el numero de nodos del árbol y h la altura.

Ejemplo: supongamos que desea calcular el numero de nodos de un árbol balanceado con altura 5. La forma en que se efectua el calculo es la siguiente:

K5= K4+1+K3

K4=K3+1+K2

K3=K2+1+K1

K2=K1+1+K0

K1=1

K0=0

K2=2

K3=4

K4=7

K5=12

INSERCION EN ARBOLES BALANCEADOS

Al momento de querer insertar en un árbol balanceado debemos distinguir los siguientes casos:

1. Las ramas izquierda (RI) y derecha (RD) del árbol tienen la misma altura (HRI=HRD) por lo tanto.

1.1. Si se inserta un elemento en RI entonces HRI será mayor que HRD

1.2. Si se inserta un elemento RD, entonces HRD será mayor que HRI

Observe que en cualquiera de los dos casos mencionados, no se viola el critero de equilibrio del árbol.

2. La rama izquierda (RI) y derecha (RD) del árbol tienen altura diferente( HRI =! HRD)

2.1. Suponiendo que HRI < HRD

2.1.1. Si se inserta un elemento en RI entonces HRI será igual a HRD(la rama tiene la misma altura, por lo que se mejora el equilibrio del árbol)

2.1.2. Si se inserta un elemento en RD entonces se rompe el critero del equilibrio del árbol y es necesario restructurarlo.

2.2. Suponiendo que HRI > HRD

2.2.1. Si

...