- Árboles AVL
-
Árboles AVL
ÁRBOLES AVL.
El problema que tiene el Árbol binario de búsqueda es que pueden producirse árboles degenerados o parcialmente degenerados, por lo que la búsqueda de un elemento puede llegar a ser de un orden de 0(lg n) y en el peor caso llegar a tener un orden de 0(n).
Gracias a los científicos Giorgii Adelson – Velsky y Yevgeniy Mikhailovich Landis, quedó resuelto este problema ya que idearon los árboles AVL, nombrados de esta forma en su honor, o balanceados en altura.
El árbol AVL es, en computación, Árbol binario de búsqueda el cual es un árbol o bien vacío o bien un árbol binario con hijo izquierdo e hijo derecho que son a su vez AVL, y además la diferencia entre sus alturas es menor o igual que 1.En este tipo de árboles, la búsqueda del elemento puede tener una complejidad de 0(log (n)).
Teorema de AVL
Gn = nº nodos en el AVL de altura n que tiene menos nodos
Entonces: Gn = Gn-1 + Gn-2 +1
OPERACIONES.
Los árboles AVL comparten las mismas operaciones básicas que el Árbol binario de búsqueda. Para conseguir un factor de balance óptimo (diferencia entre las alturas de sus subárboles izquierdo y derecho), es decir, que se encuentre entre los límites establecidos lo conseguiremos con los procesos de inserción y eliminación, junto con las rotaciones hacia la izquierda y hacia la derecha.
BALANCE DEL ÁRBOL.
El inconveniente que presentan estos árboles, es que al realizar modificaciones sobre él (insertar o borrar) podemos perder el equilibrio, por lo que tendremos que proceder al equilibrado del árbol mediante rotaciones.
ROTACIONES.
El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.
ROTACIÓN SIMPLE A LA DERECHA.De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
op rotDer: AVL{X} -> [AVL{X}] . eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) == arbolBin(R2, I2, arbolBin(R1, D2, D)) .
ROTACIÓN SIMPLE A LA IZQUIERDA.
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Precondición : Tiene que tener hijo derecho no vacío.
op rotIzq: AVL{X} -> [AVL{X}] . eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) == arbolBin(R2, arbolBin(R1, I, I2), D2) .
Si la inserción se produce en el hijo derecho del hijo izquierdo del nodo desequilibrado (o viceversa) hay que realizar una doble rotación.
ROTACIÓN DOBLE A LA DERECHA.
ROTACIÓN DOBLE A LA IZQUIERDA.
INSERCIÓN.La inserción de un elemento en un árbol AVL es idéntica que en un árbol binario de búsqueda, la diferencia se encuentra en la comprobación que hay que realizar posteriormente en los árboles AVL. En un árbol AVL tras realizar la inserción hay que comprobar que se sigue manteniendo la condición de equilibrio, o lo que es lo mismo, que la altura del subárbol izquierdo y la del subárbol derecho difieran en una unidad o sean iguales. Si se produce un desequilibrio hay que reequilibrar la estructura para que siga siendo un árbol AVL.
Debido a que las rotaciones son una operación que tienen complejidad constante y a que la altura esta limitada a O (log(n)), el tiempo de ejecución para la inserción es del orden O (log(n)).
op insertar: X$Elt AVL{X} -> AVLNV{X} . eq insertar(R, crear) == arbolBin(R, crear, crear) . ceq insertar(R1, arbolBin(R2, I, D)) == if (R1==R2) then arbolBin(R2, I, D) elseif (R1<R2) then if ( (altura(insertar(R1,I)) – altura(D)) < 2) then arbolBin(R2, insertar(R1, I), D) else ***hay que reequilibrar if (R1 < raiz(I)) then rotarDer(arbolBin(R2, insertar(R1, I), D)) else rotarDer(arbolBin(R2, rotarIzq(insertar(R1, I)), D)) fi . fi . else if ( (altura(insertar(R1,I)) – altura(D)) < 2) then arbolBin(R2, insertar(R1, I), D) else *** hay que reequilibrar if (R1 > raiz(D)) then rotarIzq(arbolBin(R, I, insertar(R1, D))) else rotatIzq(arbolBin(R, I, rotarDer(insertar(R1, D)))) fi . fi . fi .
BORRADO.
En esta operación lo primero que haremos será buscar el elemento que deseamos eliminar, y una vez encontrado procederemos a su borrado, para lo cual se distinguen los siguientes casos:
Que el nodo a eliminar sea:
1. Una hoja, por lo que simplemente, lo eliminaremos sin realizar más operaciones.
2. Posea un solo hijo, con lo que el padre del elemento que queremos eliminar, apuntará al hijo del elemento que deseamos borrar.
3. Posea dos hijos, por lo que procederemos de la siguiente forma: Buscamos el elemento mínimo del hijo derecho, una vez encontrado, sustituimos el elemento a eliminar por dicho elemento y lo eliminamos del hijo derecho, en último lugar observaremos el equilibrio del árbol y procederemos según convenga.
op eliminar: X$Elt AVL{X} -> AVL{X} . eq eliminar(R, crear) == crear . ceq eliminar(R1, arbolBin(R2, I, D)) == if (R1 == R2) then if esVacio(I) then D elseif esVacio(D) then I else if (altura(I) - altura(eliminar(min(D),D)) < 2) then arbolBin(min(D), I, eliminar(min(D), D)) ***tenemos que reequilibrar elseif (altura(hijoIzq(I) >= altura(hijoDer(I)))) then rotDer(arbolBin(min(D), I, eliminar(min(D),D))) else rotDer(arbolBin(min(D), rotIzq(I), eliminar(min(D),D)))
BÚSQUEDA.
La búsqueda en un árbol AVL se implementa igual que en el Árbol binario de búsqueda, pero con la mejora de que al ser diferentes respecto a la altura, tienen una complejidad del orden de 0(log (n)).
Especificación completa, en lenguaje MAUDE
fmod ARBOL-AVL {X :: ORDEN} is protecting ARBOL-BINARIO-BUSQUEDA{X} . sorts AVL{X} AVLNV{X} . subsort AVLNV{X} < AVL{X} . subsort AVL{X} < ABB{X} . subsort AVLNV{X} < ABBNV{X} . ***precondiciones var ANV : ABBNV{X} . vars R R1 R2 : X$Elt . vars I D I1 I2 D1 D2: AVL{X} . mb crear : AVL{X} . cmb ANV : AVLNV{X} if sd(altura(hijoIzq(ANV)), altura(hijoDer(ANV))) <= 1 . ***constructores op hijoIzq: AVLNV{X} -> AVL{X} . op hijoDer: AVLNV{X} -> AVL{X} . eq hijoIzq(arbolBin(R, I, D)) == I . eq hijoDer(arbolBin(R, I, D)) == D . op insertar: X$Elt AVL{X} -> AVLNV{X} . eq insertar(R, crear) == arbolBin(R, crear, crear) . ceq insertar(R1, arbolBin(R2, I, D)) == if (R1==R2) then arbolBin(R2, I, D) elseif (R1<R2) then if ( (altura(insertar(R1,I)) – altura(D)) < 2) then arbolBin(R2, insertar(R1, I), D) else ***hay que reequilibrar if (R1 < raiz(I)) then rotarDer(arbolBin(R2, insertar(R1, I), D)) else rotarDer(arbolBin(R2, rotarIzq(insertar(R1, I)), D)) fi . fi . else if ( (altura(insertar(R1,I)) – altura(D)) < 2) then arbolBin(R2, insertar(R1, I), D) else *** hay que reequilibrar if (R1 > raiz(D)) then rotarIzq(arbolBin(R, I, insertar(R1, D))) else rotatIzq(arbolBin(R, I, rotarDer(insertar(R1, D)))) fi . fi . fi . op eliminar: X$Elt AVL{X} -> AVL{X} . eq eliminar(R, crear) == crear . ceq eliminar(R1, arbolBin(R2, I, D)) == if (R1 == R2) then if esVacio(I) then D elseif esVacio(D) then I else if (altura(I) - altura(eliminar(min(D),D)) < 2) then arbolBin(min(D), I, eliminar(min(D), D)) ***tenemos que reequilibrar elseif (altura(hijoIzq(I) >= altura(hijoDer(I)))) then rotDer(arbolBin(min(D), I, eliminar(min(D),D))) else rotDer(arbolBin(min(D), rotIzq(I), eliminar(min(D),D))) fi . fi . elseif (R1 < R2) then if(altura(D) – altura(eliminar(R1,I)) <= 1) then arbolBin(R2, eliminar(R1,I), D) ***tenemos que reequilibrar elseif (altura(hijoDer(D)) >= altura(hijoIzq(D))) then rotIzq(arbolBin(R2, eliminar(R1,I), D)) else rotIzq(arbolBin(R2, eliminar(R1,I), rotDer(D))) fi . else if ((altura(I) - altura(eliminar(R1, D))) <= 1) then arbolBin(R2, I, eliminar(R1, D)) elseif (altura(hijoIzq(I) >= altura(hijoDer(I)))) then rotDer(arbolBin(R2, I, eliminar(R1, D))) else rotDer(arbolBin(R2, rotIzq(I), eliminar(R1, D))) fi . fi . ***selectores op raiz: AVLNV{X} -> X$Elt . eq raiz(arbolBin(R, I, D)) == R . op esVacio: AVL{X} -> Bool . eq esVacio(crear) == true . eq esVacio(arbolBin(R, I, D)) == false . op altura: AVL{X} -> Nat . eq altura(crear) == 0 . eq altura(arbolBin(R, I, D)) == 1 + max(altura(I), altura(D)) . ***auxiliares op rotDer: AVL{X} -> [AVL{X}] . eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) == arbolBin(R2, I2, arbolBin(R1, D2, D)) . op rotIzq: AVL{X} -> [AVL{X}] . eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) == arbolBin(R2, arbolBin(R1, I, I2), D2) . endfm .
Especificación completa de árbol AVL en C++:
typedef int tElemento;typedef struct NODO_AVL {
tElemento elemento; struct AVL_NODO *izqda; struct AVL_NODO *drcha; int altura;
} nodo_avl;
typedef nodo_avl *arbol_avl;
arbolAVL Crear_AVL() {
return AVL_VACIO;
}
void Destruir_AVL (arbolAVL A) {
if (A) { Destruir_AVL(A->izqda); Destruir_AVL(A->drcha); free(A); }}
int miembro_AVL(tElemento e,arbolAVL A) {
if (A == NULL) return 0; if (e == A->elemento) return 1; else if (e < A->elemento) return miembro_AVL(e,A->izqda); else return miembro_AVL(e,A->drcha);
}
void Simple_derecha(arbolAVL *A) {
nodoAVL *p;
p = (*A)->izqda; (*A)->izqda = p->drcha; p->drcha = (*A); (*A) = p; /* Ajustamos las alturas */ p = (*A)->drcha; p->altura = maximo(altura(p->izqda),altura(p->drcha))+1; (*A)->altura = maximo(a1tura((*T)->izqda),altura((*T)->drcha))+1;
}
void Simple_izquierda(arbolAVL *A) {
nodoAVL *p;
p = (*A)->drcha; (*A)->drcha = p->izqda; p->izqda = (*A); (*A) = p; /*Ajustamos las alturas */ p = (*A)->izqda; p->altura = maximo(altura(p->izqda),altura(p->drcha))+1; (*A)->altura = maximo(altura((*A)->izqda),altura((*A)->drcha))+1;
}
void Doble_izquierda_derecha (arbolAVL *AT) {
simple_izquierda(&((*A)->izqda)); simple_derecha(A);
}
void Doble_derecha_izquierda (arbolAVL *A) {
simple_derecha(&((*A)->drcha)); simple_izquierda(A);
}
void ajusta_AVL (tElemento e, arbolAVL *A) {
if (!(*A)) return; if (e > (*A)->elemento) ajusta_AVL(e,&((*A)->drcha)); else if (e < (*A)->elemento) ajusta_avl(e,&((*A)->izqda));switch (altura((*A)->izqda)-altura((*A)->drcha)) { case 2: if (altura((*A)->izqda->izqda) > altura((*A)->izqda->drcha)) simple_derecha(A); else doble_izquierda_derecha(A); break; case -2: if (altura((*A)->drcha->drcha) > altura((*A)->drcha->izqda)) simple_izquierda(A); else doble_derecha_izquierda(A); break; default: (*A)->altura = maximo(altura((*A)->izqda),altura((*A)->drcha))+1; }}
void insertarAVL (tElemento e, arbolAVL *A) {
nodoAVL **p; p=T; while (*p!=NULL) if ((*p)->elemento > e) p = &((*p)->izqda); else p = &((*p)->drcha);(*p)=(nodo_avl *)malloc(sizeof(nodoAVL)); if (!(*p)) error("Error: Memoria insuficiente.");(*p)->elemento = e; (*p)->altura = 0; (*p)->izqda = NULL; (*p)->drcha = NULL; ajustaAVL(e,A);
}
void borrarAVL (tElemento e, arbolAVL *A) {
nodoAVL **p,**aux,*dest; tElemento elem;
p=A; elem=e; while ((*p)->elemento!=e) { elem=(*p)->elemento; if ((*p)->elemento > e) p=&((*p)->izqda); else p=&((*p)->drcha); }if ((*p)->izqda!=NULL && (*p)->drcha!=NULL) { aux=&((*p)->drcha); elem=(*p)->elemento; while ((*aux)->izqda) { elem=(*aux)->elemento; aux=&((*aux)->izqda); } (*p)->elemento = (*aux)->elemento; p=aux; }- if ((*p)->izqda==NULL && (*p)->drcha==NULL) {
- free(*p);
- (*p) = NULL;
- } else if ((*p)->izqda == NULL) {
- dest = (*p);
- (*p) = (*p)->drcha;
- free(dest);
- } else {
- dest = (*p);
- (*p) = (*p)->izqda;
- free(dest);
- }
- ajustaAVL(elem,A);
}
Véase también
- Árbol binario de búsqueda
- Árbol (programación)
- Árbol binario
- Árbol AVL
- Árbol rojo-negro
- Árbol splay
- Árbol multirrama
Categoría: Árboles (estructura)
Wikimedia foundation. 2010.
