Á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).

rotación simple a la derecha‎ iniciorotación simple a la derecha final

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.

rotación a la izquierda iniciorotación a la izquierda final

 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 a la izquierda iniciorotación a la izquierda final

ROTACIÓN DOBLE A LA IZQUIERDA.


rotación a la izquierda iniciorotación a la izquierda final


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.


Reequilibrado de arboles,inserción2.JPG

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. Eliminacion1.JPG

2. Posea un solo hijo, con lo que el padre del elemento que queremos eliminar, apuntará al hijo del elemento que deseamos borrar.

Eliminacion2.JPG

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.

Eliminacion3.JPG

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 AVL (INGLES)

Árbol Binario (INGLES)

Obtenido de "%C3%81rboles AVL"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Árbol AVL — es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson Velskii y Landis. Fue el primer árbol de búsqueda binario auto balanceable que se ideó. Contenido 1 Descripción 2 Definición formal 2.1 Definición de la …   Wikipedia Español

  • Árbol rojo-negro — Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en… …   Wikipedia Español

  • Árbol binario de búsqueda — Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática. Contenido 1 Descripción 2 Operaciones 2.1 Búsqueda …   Wikipedia Español

  • Árbol biselado — Un Árbol biselado o Árbol Splay es un Árbol binario de búsqueda auto balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como… …   Wikipedia Español

  • Árbol (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Estructura de datos — En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema. Una estructura de datos… …   Wikipedia Español

  • Maude — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 10 de septiembre de 2008. También… …   Wikipedia Español

  • Árbol de Fibonacci — Árboles de Fibonacci de orden 1, 2, 3 y 4. Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci. El árbol de Fibonacci se define de la siguiente manera: El… …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

  • Valencia — Para otros usos de este término, véase Valencia (desambiguación). Valencia …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.