Arboles AVL

Árboles AVL
Factor de equilibrio
0

1

-1

FE = ASD - ASI

2

FE: Factor de Equilibrio
ASD: Altura del Subárbol Derecho
ASI: Altura del Subárbol Izquierdo

-2

1

-1

Facto
r2

2

-2

-1

1

Desequilibrio hacia la derecha

1
0

Equilibrado

-1
-2

Desequilibrio hacia la
izquierda

©® 2006 M.S.I. Alfredo Gutiérrez Hdez.

1

Árboles AVL
¿Quérotación aplicar?
Si un árbol está desbalanceado hacia la
izquierda (-2), aplicar rotación hacia derecha

Si un árbol está desbalanceado hacia la
derecha (2), aplicar rotación hacia izquierda

Enun árbol que está desbalanceado hacia
la izquierda revisar el factor de equilibrio
del subárbol izquierdo

En un árbol que está desbalanceado hacia
la derecha revisar el factor de equilibrio
delsubárbol derecho
2

-2
1

Si el signo de los factores coincide,
se aplica una rotación simple

-1

-2
2

-1

Si el signo de los factores no coincide,
se aplica una rotación doble©® 2006 M.S.I. Alfredo Gutiérrez Hdez.

1

2

Árboles AVL
Rotaciones Simples

A la izquierda
(RSI)
Pivote

A la derecha
(RSD)

d

a
c
b

c
d

a

c
a

Pivote

b
c

da

b

d
b

Árboles opcionales, pueden o no existir

©® 2006 M.S.I. Alfredo Gutiérrez Hdez.

3

Árboles AVL
Rotaciones Simples

A la izquierda
(RSI)
Pivote

A

a

2

aux1=(*A)->der;
aux2 = aux1->izq;
(*A)->der = aux2;
aux1->izq = (*A);
(*A) = aux1;

3

c

aux1

a
b

d

aux2
1

c

c
a

d

b

d

b

©® 2006 M.S.I. Alfredo Gutiérrez Hdez.4

Árboles AVL
Rotaciones Simples

A la derecha
(RSD)

d

A

Pivote
2
3

c

aux1

d
a

aux1 =(*A)->izq;
aux2 = aux1->der;
(*A)->izq = aux2;
aux1->der = (*A);
(*A) =aux1;

b
1

c

c
a

d

a

aux2

b

b

©® 2006 M.S.I. Alfredo Gutiérrez Hdez.

5

Árboles AVL
Ejemplo con rotaciones simples a la izquierda
Inserte en un árbol AVL la...