Capítulo 8 Árboles AVL

8.1 Árboles equilibrados

Ya vimos al final del capítulo anterior que el comportamiento de los ABB no es siempre tan bueno como nos gustaría. Pues bien, para minimizar el problema de los ABB desequilibrados, sea cual sea el grado de desequilibrio que tengan, se puede recurrir a algoritmos de equilibrado de árboles globales. En cuanto a estos algoritmos, existen varios, por ejemplo, crear una lista mediante la lectura en inorden del árbol, y volver a reconstruirlo equilibrado. Conociendo el número de elementos no es demasiado complicado.

El problema de estos algoritmos es que requieren explorar y reconstruir todo el árbol cada vez que se inserta o se elimina un elemento, de modo que lo que ganamos al acortar las búsquedas, teniendo que hacer menos comparaciones, lo perdemos equilibrando el árbol.

Para resolver este inconveniente podemos recurrir a los árboles AVL.

8.2 Definición

Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.

No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos.

El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o borrado.

8.3 Operaciones en AVL

Los AVL son también ABB, de modo que mantienen todas las operaciones que poseen éstos. Las nuevas operaciones son las de equilibrar el árbol, pero eso se hace como parte de las operaciones de insertado y borrado.

8.4 Factor de equilibrio

Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los ABB, y además un miembro nuevo: el factor de equilibrio.

El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:

FE = altura subárbol derecho - altura subárbol izquierdo;

Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

8.5 Rotaciones simples de nodos

Los reequilibrados se realizan mediante rotaciones, en el siguiente punto veremos cada caso, ahora vamos a ver las cuatro posibles rotaciones que podemos aplicar.

Rotación simple a la derecha (SD)

Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de -1 ó 0, es decir, que esté cargado a la izquierda o equilibrado.

Árbol desequilibrado a la izquierda
Árbol desequilibrado a la izquierda

Procederemos del siguiente modo:

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de -2. Y llamaremos Q al nodo raíz del subárbol izquierdo de P. Además, llamaremos A al subárbol izquierdo de Q, B al subárbol derecho de Q y C al subárbol derecho de P.

En el gráfico que puede observar que tanto B como C tienen la misma altura (n), y A es una unidad mayor (n+1). Esto hace que el FE de Q sea -1, la altura del subárbol que tiene Q como raíz es (n+2) y por lo tanto el FE de P es -2.

  1. Pasamos el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P.
  2. El árbol P pasa a ser el subárbol derecho del nodo Q.
  3. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
RSD paso 1 RSD paso 2 RSD paso 3
Rotación simple a la derecha

En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque sus dos subárboles tienen la misma altura (n), en el caso de Q, porque su subárbol izquierdo A tiene una altura (n+1) y su subárbol derecho también, ya que a P se añade la altura de cualquiera de sus subárboles.

Árbol equilibrado
Árbol resultante equilibrado

En el caso de que el subárbol izquierdo esté equilibrado, el procedimiento es similar, pero los FE de los nodos P y Q en el árbol resultante son diferentes.

En principio, parece poco probable que nos encontremos un árbol con esta estructura, pero es posible encontrarlos cuando se borran nodos.

Árbol desequilibrado a la izquierda (b)
Árbol desequilibrado a la izquierda (caso b)

Aplicamos el mismo algoritmo para la rotación:

RSD paso 1 RSD paso 2 RSD paso 3
Rotación simple a la derecha

En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque su subárbol izquierdo es una unidad más alto que el derecho, quedando su FE en -1. En el caso de Q, porque su subárbol derecho una altura (n+1) y su subárbol izquierdo, una altura de n.

Árbol equilibrado
Árbol resultante equilibrado

De modo que, aunque aplicamos el mismo algoritmo, ya que en ambos casos se trata de una rotación simple, deberemos tener en cuenta estos detalles a la hora de ajustar los nuevos valores de FE en nuestro programa.

Rotación simple a la izquierda (SI)

Se trata del caso simétrico del anterior. Esta rotación se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de 1 ó 0, es decir, que esté cargado a la derecha o esté equilibrado.

Árbol desequilibrado a la derecha
Árbol desequilibrado a la derecha

Procederemos del siguiente modo:

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Y llamaremos Q al nodo raíz del subárbol derecho de P. Además, llamaremos A al subárbol izquierdo de P, B al subárbol izquierdo de Q y C al subárbol derecho de Q.

En el gráfico que puede observar que tanto A como B tienen la misma altura (n), y C es una unidad mayor (n+1). Esto hace que el FE de Q sea 1, la altura del subárbol que tiene Q como raíz es (n+2) y por lo tanto el FE de P es 2.

  1. Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.
  2. El árbol P pasa a ser el subárbol izquierdo del nodo Q.
  3. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
RSI paso 1 RSI paso 2 RSI paso 3
Rotación simple a la izquierda

En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque sus dos subárboles tienen la misma altura (n), en el caso de Q, porque su subárbol izquierdo A tiene una altura (n+1) y su subárbol derecho también, ya que a P se añade la altura de cualquiera de sus subárboles.

Árbol equilibrado
Árbol resultante equilibrado

Comentarios de los usuarios (5)

Iván
2012-06-20 22:12:49

Bueno quiero hacer un aporte de listas circulares pero estático, es algo que yo hice espero que a más de alguien le sirva el Algoritmo (si alguien desea modificar estos programas es libre de modificarlos siempre y cuando al utilizarlo aporten su idea y funcione de una mejor manera)

y si tiene algunos fallos, *si le pongo un pop en medio de los push() pues tiende a descontrolarse un poco....*

Bueno espero a que se mejore y así se perfeccione

//////////////////////////////////////////////////

//Listas circulares Estáticas Cola

//////////////////////////////////////////////////

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int vector [4];

unsigned int s=0;

unsigned int m=0;

void iniciar ()

{

unsigned int i;

for (i=0; i<4; i++)

{

vector[i]=0;

}

s=0;

m=0;

}

void mostrar()

{

unsigned int j;

cout<<"=====Mostrando datos==========="<<endl;

for (j=0; j<4; j++)

{

cout<<"\t\t"<<vector[j]<<endl;

}

cout<<"==============================="<<endl;

}

void Push (int dato)

{

if ((m>3)&&(vector[0]!=0))

{

cout<<"lista llena"<<endl;

}

else

{

if (m>3)

{

m=0;

}

else

{

vector[m]=dato;

cout<<"\t#dato insertado ["<<vector[m]<<"]"<<endl;

m++;

}

}

}

void Pop ()

{

if ((s==m)&&(vector[0]==0))

{

cout<<"cola vacia \n";

iniciar();

}

else

{

if(vector[s]!=0)

{

cout<<"sacando datos["<<vector[s]<<"]"<<endl;

vector[s]=0;

s++;

}

else

{

cout<<"casilla vacia"<<endl;

}

}

}

int main()

{

iniciar();

Pop();

Push(7);

Push(9);

Push(4);

Push(6);

Push(3);

mostrar ();

Pop();

Pop();

Pop();

Pop();

Pop();

Pop();

iniciar ();

Push(9);

Push(10);

Push(11);

Push(12);

mostrar ();

Pop();

Pop();

Pop();

Pop();

Pop();

return 0;

}

///////////////////////////////////////////////////////

///////////////////////////////////////////////////

//////////////////////////////////////////////////////////

/////////////////////////////////////////////////////

//Listas circulares estáticas Pila

////////////////////////////////////////////////////

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int vector[4];

unsigned int t=3;

unsigned int s=0;

void iniciar ()

{

unsigned int i;

for (i=0; i<4;i++)

{

vector[i]=0;

}

t=3;

s=0;

}

void Push(int dato)

{

if ((vector[0]!=0)&&(s>3))

{

cout<<"lista llena"<<endl;

}

else

{

vector[s]=dato;

cout<<"\t\tdato insertado ["<<vector[s]<<"]\n";

s++;

}

}

void Pop()

{

if((t!=s)&&(vector[0]==0))

{

cout<<"Lista vacia"<<endl;

iniciar ();

}

else

{

if (vector[t]==0)

{

cout<<"casilla vacia";

iniciar ();

}

cout<<"====================================="<<endl;

cout<<"sacando dato ["<<vector[t]<<"]"<<endl;

cout<<"====================================="<<endl;

vector[t]=0;

t--;

}

}

int main()

{

cout<<"|*==============================*|\n";

cout<<"|*=Listas circulares estáticas==*|\n";

cout<<"|*==============Pila============*|\n\n";

iniciar ();

Push(7);

Push(4);

Push(9);

Push(5);

Push(14);

Pop();

Pop();

Pop();

Pop();

Pop();

Pop();

Push(1);

Push(6);

Push(9);

Push(15);

//mostrar();

return 0;

}

2M
2012-10-20 19:41:01

Un saludo a todos, ¿alguien puede decirme por que el FE del ejemplo Rotación simple a la derecha (SD)es -2?

Según mi opinión:

El subárbol derecho de P tiene una altura= 1, Y FE=0

El subárbol izquierdo de P tiene una altura= 2, Y FE=0

Por lo que queda FE de P= 1-2= -1... ¿?

Agradecería saber en que me he euqivocado, para comprender los árboles AVL.. :)

2M
2012-10-20 21:29:32

Ya les entendí el ejemplo!!

Los nodos A, B y C pueden tener más nodos hijos.

Lo que importa es que el FE de P sea=-2 y el FE de su subárbol izq.(osea, el nodo Q) sea=-1 ó 0 (en el ejemplo es igual a -1) para realizar la rotación simple a la derecha SD.

Muchas gracias por la información y sus explicaciones!!

Krlos
2013-05-09 23:04:22

Hola amigos un SALUDO me podrían ayudar con una duda que tengo

pueden decirme por que el FE del ejemplo de rotación simple a la izquierda es 2

y de como sacar el factor de equilibrio a cada nodo....

....Agradeceria mucho su AYUDA...!!!

Nicolás
2017-05-19 04:34:19

Hola, conocen una función para poder agregar datos desde un archivo y que sea compatible con el árbol avl en c que esta para descargar en esta página.