Arboles AVL

Arboles AVLIng. Juan Ignacio Zamora M. M.Sc

Arboles AVL

Desarrollados en 1962 por Adelson-

Velskii y Landis (AVL)

Nacen debido a la diferenciaentre los rendimientos del caso

promedio O(logn) y el peor caso

O(n) en la busqueda del arbol

binario.

Los Arboles AVL son Arboles

Binarios de Busqueda; los cuales

estan definidos segun el Factor de

Equilibrio (Fe)

F L

J

H

P

-1

1

0

1

0

Fe = h(der) – h(izq)

Revision de CodigoArbol Equilibrado no Binario de Busqueda!

Generar un Arbol AVL :: Estrategias

Insertar y generar un arbol AVL

binario de busqueda

Ya se tiene un Arbol Binario de

Busqueda, pero no esta balanceado

Insercion de un Nodo : Proceso

Recuerden que estamos trabajando con arboles binaries de busqueda. Se

debe inserter de la misma forma que en el ABB.

Una vez que insertamos el nodo, debemos regresar por el mismo camino y

vamos a actualizar el Fe de cada nodo. Si, esto quiere decir que la clase

UNode ahora tiene una variable int Fe, que almacena el factor de

Equilibrio.

En el momento en el cual se irrumpa la condicion de equilibrio, se debe

proceder a re-acomodar el arbol con base a rotaciones.

Existen 4 principals violaciones al factor de equilibrio

Caso 1: Rotacion Izq-Izq (ii)

Se insertan C,B,A

C irrumpe el factor de equilibrio

Se hace una rotacion Izq-Izq

Se obtiene el sub arbol balanceado

B

J

C

B

C-1

0

-2

-1

0

B

J C 0

0

0n1

n

• n.Izq = n1.Der

• n1.Der = n

• n = n1

Algoritmo - Rotacion

Caso 2: Rotacion Der-Der (dd)

Se insertan A,B,C

C irrumpe el factor de equilibrio

Se hace una rotacion Izq-Izq

Se obtiene el sub arbol balanceado

B

A

1

00

B

A C 0

0

0B

C

A2

1

n1

n

• n.Der = n1.Izq

• n1.Izq = n

• n = n1

Algoritmo - Rotacion

Caso 3: Rotacion Der-Izq (di)

0

B

A C0

0

0C

B

A2

-1n1

n • n1.Izq = n2.Der

• n2.Der = n1

• n.Der = n2.Izq

• n2.Izq = n

• n = n2 n2

Algoritmo - Rotacion

Caso 4: Rotacion Izq-Der (id)

0

B

A C0

0

0A

B

C-2

1 n1

n • n1.Der = n2.Izq

• n2.Izq = n1

• n.Izq = n2.Der

• n2.Der = n

• n = n2 n2

Algoritmo - Rotacion

Resuelva en Papel

• Indique en cada caso,

que rotacion se debe

aplicar.

• Aplique el Algoritmo de

Rotacion para cada

Arbol

• Calcule los nuevos

Factores de Equilibrio

Caso:Alpha Caso:Beta

Caso:Gamma Caso:Miu

Problem?

1.Utilizandos las estructuras de datos y las

clases Utree y UNode desarrolladas la

semana pasada desarrolle:

1. Insert-AVL(T,x), donde x es un UNode

2.Balance-AVL(T,x) balancea un arbol a

partir del nodo x

3.Delete-AVL(T, v) donde v es el valor

del nodo a borrar

Esta practica junto a todas

las clases desarrolladas se

suben al foro “AVL”.