Arboles AVL Insercion

Factor de equilibrio
Tipos de Rotación
Cómo se mueven los

apuntadores
Cómo se actualiza el FE

Un árbol AVL (llamado así por

las iníciales de sus inventores:
(Adelson-Velskii y Landis) es
unárbol binario de búsqueda
en el que para cada nodo, las
alturas de sus subárboles
izquierdo y derecho no difieren
en más de 1.

 El

factor de equilibrio es la
diferencia entre las alturas del
árbolderecho y el izquierdo:

 FE = altura subárbol derecho - altura

subárbol izquierdo

 Por definición, para un árbol AVL,

este valor debe ser -1, 0 ó 1.

 A) SIMPLE
2

 DD

0

A

B

1
B

0

0

0A

C

C

I I

-2
-1
0
C

B

0

A

B

0
C

0
A

 B) COMPUESTA
2

 DI

0

A

-1
B

0

C

0

0

A

B

C

I D

-2

0

A

C

1

0

B

0
C

B

0
A

 A) SIMPLE
 DD
Nodo^. Der ← Nodo1^. Izq

Nodo1^.Izq ← Nodo
Nodo ← Nodo1
I I

Nodo^. Izq ← Nodo1^. Der
Nodo1^. Der ← Nodo
Nodo ← Nodo1

 B) COMPUESTA

 DI

 ID

Nodo1^. Izq ← Nodo2^. Der
Nodo2^. Der ← Nodo1
Nodo^. Der ← Nodo2^. Izq
Nodo2^. Izq← Nodo
Nodo ← Nodo2
Nodo1^. Der ← Nodo2^. Izq
Nodo2^. Izq ← Nodo1
Nodo ^. Izq ← Nodo2^. Der
Nodo2^. Der ← Nodo
Nodo ← Nodo2

 Se quiere insertar las siguientes claves

en un árbol AVL que seencuentra
vacío:

65, 50, 23, 70, 82, 68, 39
AVL tree applet
http://www.gedlc.ulpgc.es/docencia/ed_ii/simulaciones/
arboles_binarios/applet.html

 Determine el árbol resultante después

de insertar lassiguientes claves en un
árbol AVL que se encuentra vacío:

58, 43, 75, 86, 65, 70, 67, 73, 93, 69,
25, 66, 68, 47, 62, 10, 60

 1) INSERTAR CLAVE
 2) ACTUALIZAR F.E. (RUMBO A LA RAIZ)
 Si F.E. = -1,0,1Continuar en Paso 1

 SI NO
 2.1) Etiquetar con NODO a esa clave
 2.2) Si F.E. de NODO es negativo
Etiquetar NODO1 a hijo izquierdo
SI NO
Etiquetar NODO1 a hijo derecho
 2.3) Si signo de F.E.de NODO y NODO1 son iguales
ROTACION SIMPLE DD si son Positivos
ROTACION SIMPLE I I si son Negativos
SI NO ROTACIÓN COMPUESTA
FE-NODO FE-NODO1
NODO2

Rotación D I Positivo
Rotación I D...