1

Arboles AVL

• Introducción• Arboles AVL (Adel’son-Vel’skii and Landis

2

Arbol AVL

• Los árboles AVL son balanceados.

• Un árbol AVL es un árbol binario de búsqueda tal que para cada nodo v de T, las alturas de los hijos de v difieren como mucho en 1.

88

44

17 78

32 50

48 62

2

4

1

1

2

3

1

1

Ejemplo de árbol AVL donde las alturas se muestran junto a los nodos

3

Altura de un árbol AVL

• Proposición: La altura de un árbol AVL T que almacena n llaves es O(log n).

• Justificación: ....

4

Inserción

88

44

17 78

32 50

48 62

2

5

1

1

3

4

2

1

54

1

T0T2

T3

x

y

z

2

3

4

5

67

1

88

44

17

7832 50

48

622

4

1

1

2 2

3

154

1

T0 T1

T2

T3

x

y z

inserta(54) -> desbalanceado...

...balanceado

1

2

3

4

5

6

7

5

Restructuración• Hay cuatro formas de rotar nodos en un árbol AVL:

- Rotación simple:

T0T1

T2

T3

c = xb = y

a = z

T0 T1 T2

T3

c = xb = y

a = zsingle rotation

T3T2

T1

T0

a = xb = y

c = z

T0T1T2

T3

a = xb = y

c = zsingle rotation

6

Restructuración (cont.)• Rotaciones dobles:

double rotationa = z

b = xc = y

T0T2

T1

T3 T0

T2T3T1

a = zb = x

c = y

double rotationc = z

b = xa = y

T0T2

T1

T3 T0

T2T3 T1

c = zb = x

a = y

7

Eliminación• eliminar(32)