Arboles AVL (Adelson-Velskii-Landis) Son rboles de bsqueda con una condicin de equilibrio: para todo nodo del rbol, la altura de los subrboles izquierdo y derecho puede diferir a lo sumo en 1 (la altura de un rbol vaco se define como -1). Hay que mantener la informacin de altura de cada nodo (en el registro nodo). Es fcil (?) mostrar que la altura de un AVL es a lo sumo ~1.44log(n + 2) 0.328, pero en la prctica es cercana a log(n + 1) + 0.25. El nmero mnimo de nodos de un AVL de altura h est dado por N(h) = N(h - 1) + N(h - 2) + 1. Para h = 0, N(h) = 1. Para h = 1, N(h) = 2. (Parecido a Fibonacci) Cuando se hace una insercin es necesario actualizar toda la informacin de equilibrio de los nodos en el camino a la raz. Y quizs, para mantener la condicin de equiibrio haga falta hacer alguna rotacin.

Rotacin simple Los dos rboles de la figura contienen los mismos elementos y ambos son ABB. Ante todo, en ambos rboles k1 < k2. Segundo, todos los elementos de X son menores que k1, todos los de Z son mayores que k2 y los de Y estn entre k1 y k2. La conversin de uno a otro se denomina rotacin. Consiste en algunos cambios de punteros, y cambia la estructura del rbol pero preserva la propiedad de ABB. Se puede hacer una rotacin en cualquier nodo, no slo en la raz. Esto da un mtodo fcil para arreglar un AVL si por la insercin de un nodo se pierde la condicin de equilibrio: se hace una rotacin es ese nodo. El algoritmo bsico consiste en iniciar en el nodo insertado y subir en el rbol actualizando la informacin del equilibrio en cada nodo del camino. Se termina si se llega a la raz sin ningn nodo desequilibrado. Si no, se aplica una rotacin al primer nodo incorrecto que se encuentre, y se ajusta su equilibrio (hay que ver si hace falta seguir hasta la raz). En muchos casos, esto basta para reequilibrar el rbol. Rotacin doble La rotacin simple tiene un problema. Es el caso en que la insercin debe realizarse en el arbol de los elementos medios (el rbol Y) y los otros dos rboles tienen la misma altura. La solucin es la rotacin doble, que es parecida a la simple pero abarca cuatro subrboles. En la primer figura (rotacin doble izquierda-derecha), es lo mismo que si se hiciera una rotacin simple entre k1 y k2 y despus entre k2 y k3. La otra figura muestra el caso simtrico (rotacin doble derecha-izquierda).

k1

k2

X Y Z

k1 k2

X

Y Z

k1

k3

A

Dk2

B C

k1

k3

A

D k2

B C

k2

k1

A B

k3

C D

k2

k3

A B

k1

C D

type ap_avl = ^nodo_avl; nodo_avl = record elemento: tipo_elemento; izq: ap_avl; der: ap_avl; altura: integer; end; ARBOL_DE_BUSQUEDA = ^nodo_avl; function altura (p: ap_avl): integer begin if p=nil then altura := -1 else altura := p^.altura; end; procedure insertar (x: tipo_elemento; var A: ARBOL_DE_BUSQUEDA) begin if A=nil then begin {Crear un rbol de un nodo} new(A); A^.elemento := x; A^.izq := nil; A^.der := nil; A^.altura := 0; end {if A=nil}

else begin if x

{k2 tiene un hijo izquierdo} procedure rotar_s_izq (var k2: ap_avl) var k1: ap_avl; begin

k1 := k2^.izq; k2^.izq := k1^.der; k1^.der := k2; k2^.altura := max(altura(k2^.izq),altura(k2^.der))+1; k1^.altura := max(altura(k1^.izq),k2^.altura)+1; k2 := k1;

end; {k3 tiene un hijo izquierdo, que tiene un hijo derecho} procedure rotar_d_izq (var k2: ap_avl) var k1: ap_avl; begin

rotar_s_der(k3^.izq); {rotar entre k1 y k2} rotar_s_izq(k3); {rotar entre k3 y k2}

end;