Estructura de Datos Sesion 11 Arboles AVL

Estructura de Datos
Ing. Manuel Guerra

Sesión 11

Arboles AVL…
Porque Surgen los AVL:
Si un árbol binario de búsqueda crece descontroladamente, el rendimiento
puede disminuir considerablemente(solo una de sus ramas se extiende).
Los Arboles AVL o Balanceados surgen por la necesidad de mejorar el
rendimiento de los arboles Binarios de Búsqueda.

Estos arboles reciben el nombre de AVL enhonor a sus inventores, dos
matemáticos rusos, G.M. Adelson - Velskii y E.M. Landis.

Concepto:

"Para todo nodo T del árbol, la altura de los subárboles izquierdo
y derecho no deben diferir en mas de unaunidad"

Arboles AVL…
Creacion de un Arbol AVL:
Para inserción se deben cumplir con las normas de un Árbol Binario de
Búsqueda (Menores a la Izquierda y Mayores a la Derecha).
 En cada inserciónde nodos en el árbol, este debe evaluar si su estructura
sigue cumpliendo con la condicionante de balanceo de sus Subarboles
Izquierdo y Derecho en cada uno de sus nodos.
Para poder determinar si unárbol esta balanceado debe manejarse
información relativa al equilibrio de cada nodo del árbol.
Surge así el concepto de factor de equilibrio de un nodo (FE) que se define
como : La altura del subarbolderecho menos la altura del subarbol izquierdo.

FE = Ard – Ari

(Valores permitidos para FE : -1, 0, 1)

Re-Estructuración de Arboles AVL…
Re-Estructuracion Izquierda-Izquierda (RII):

Debe
BajarDesbalance
entre C y A

C
B

A

B
Generando

Debe
Subir

A

C

Re-Estructuracion de Arboles AVL…
Re-Estructuracion Derecha-Derecha (RDD):
Debe
Bajar

Desbalance
entre A y C
A

B
B

Debe
SubirGenerando
C

A

C

Re-Estructuracion de Arboles AVL…
Re-Estructuracion Derecha-Izquierda (RDI):
Debe
Bajar

Desbalance
entre A y C

A

B

C
Generando
B

Debe
Subir

A

C

Re-Estructuracion de ArbolesAVL…
Re-Estructuracion Izquierda-Derecha (RID):
Desbalance
entre C y A
C
A

Debe
Bajar

B
Generando

A
B
Debe
Subir

C

Creación de Arboles AVL…
Ejemplo: Recibe los valores 40, 45, 60.

40
45...