8.9 Ejemplo de árbol AVL en C

No ha demasiado que añadir, construiremos los ejemplos de árboles AVL basándonos en los ejemplos que hicimos para árboles binarios de búsqueda.

Sólo tenemos que añadir cinco nuevas funciones: una para equilibrar el árbol, y cuatro para las cuatro posibles rotaciones.

Además, modificaremos ligeramente las funciones de inserción y borrado para que se equilibre el árbol automáticamente después de cada inserción o borrado.

En la estructura de nodo para árbol AVL añadiremos un puntero al nodo padre y un valor entero para almacenar el factor de equilibrio.

Cuando se inserten nuevos nodos hay que ajustar los valores de los nuevos miembros de nodo: FE y padre. Seguidamente, llamaremos a la función "Equilibrar", salvo que el nodo insertado sea el raíz, ya que en ese caso no es necesario, evidentemente.

El procedimiento de equilibrar consiste en la implementación del algoritmo que vimos en el punto anterior:

/* Equilibrar árbol AVL partiendo de un nodo*/
void Equilibrar(Arbol *a, pNodo nodo, int rama, int nuevo) {
   int salir = FALSE;

   /* Recorrer camino inverso actualizando valores de FE: */
   while(nodo && !salir) {
      if(nuevo)
         if(rama == IZQUIERDO) nodo->FE--; /* Depende de si añadimos ... */
         else                  nodo->FE++;
      else
         if(rama == IZQUIERDO) nodo->FE++; /* ... o borramos */
         else                  nodo->FE--;
      if(nodo->FE == 0) salir = TRUE; /* La altura de las rama que
                                         empieza en nodo no ha variado,
                                         salir de Equilibrar */
      else if(nodo->FE == -2) { /* Rotar a derechas y salir: */
         if(nodo->izquierdo->FE == 1) RDD(a, nodo); /* Rotación doble  */
         else RSD(a, nodo);                         /* Rotación simple */
         salir = TRUE;
      }
      else if(nodo->FE == 2) {  /* Rotar a izquierdas y salir: */
         if(nodo->derecho->FE == -1) RDI(a, nodo); /* Rotación doble  */
         else RSI(a, nodo);                        /* Rotación simple */
         salir = TRUE;
      }
      if(nodo->padre)
         if(nodo->padre->derecho == nodo) rama = DERECHO; else rama = IZQUIERDO;
      nodo = nodo->padre; /* Calcular FE, siguiente nodo del camino. */
   }
}

Las funciones para rotar son también sencillas, por ejemplo, la rotación simple a la derecha:

/* Rotación simple a derechas */
void RSD(Arbol *a, pNodo nodo) {
   pNodo Padre = nodo->padre;
   pNodo P = nodo;
   pNodo Q = P->izquierdo;
   pNodo B = Q->derecho;

   if(Padre)
     if(Padre->derecho == P) Padre->derecho = Q;
     else Padre->izquierdo = Q;
   else *a = Q;

   /* Reconstruir árbol: */
   P->izquierdo = B;
   Q->derecho = P;

   /* Reasignar padres: */
   P->padre = Q;
   if(B) B->padre = P;
   Q->padre = Padre;

   /* Ajustar valores de FE: */
   P->FE = 0;
   Q->FE = 0;
}

Y la rotación doble a la derecha:

/* Rotación doble a derechas */
void RDD(Arbol *raíz, Arbol nodo) {
   pNodo Padre = nodo->padre;
   pNodo P = nodo;
   pNodo Q = P->izquierdo;
   pNodo R = Q->derecho;
   pNodo B = R->izquierdo;
   pNodo C = R->derecho;

   if(Padre)
     if(Padre->derecho == nodo) Padre->derecho = R;
     else Padre->izquierdo = R;
   else *raíz = R;

   /* Reconstruir árbol: */
   Q->derecho = B;
   P->izquierdo = C;
   R->izquierdo = Q;
   R->derecho = P;

   /* Reasignar padres: */
   R->padre = Padre;
   P->padre = Q->padre = R;
   if(B) B->padre = Q;
   if(C) C->padre = P;

   /* Ajustar valores de FE: */
   switch(R->FE) {
      case -1: Q->FE = 0; P->FE = 1; break;
      case 0:  Q->FE = 0; P->FE = 0; break;
      case 1:  Q->FE = -1; P->FE = 0; break;
   }
   R->FE = 0;
}

8.10 Ejemplo de árbol AVL en C++

Usando clases el ejemplo también está basado en el que hicimos para árboles binarios de búsqueda, añadiendo las cinco funciones anteriores: Equilibrar, RSD, RSI, RDD y RDI. Además de las modificaciones en Insertar y Borrar.

8.11 Ejemplo de árbol AVL en C++ con plantillas

Usando plantillas no hay más que generalizar el ejemplo de clases, cambiando en tipo de dato a almacenar por el parámetro de la plantilla.

Fichero con el código fuente.

Ir a página de descargas: Descargar programa

Comentarios de los usuarios (18)

Manuel
2011-03-18 19:53:39

Hola, he descargado el código en c parar árboles AVL, pero da un segmentation fault cuando insertas un elemento y luego lo borras.

El problema es que accedes a padre->derecho cuando padre es NULL.

Ricardo
2011-08-17 13:27:44

Hola he descargado el codigo en C++ para un arbol AVL y hay unas lineas de codigo que no llego a entender

void AVL::RSI(Nodo* nodo)

{

cout << "RSI" << endl;

Nodo *Padre = nodo->padre;

Nodo *P = nodo;

Nodo *Q = P->derecho;

Nodo *B = Q->izquierdo;

/*Aqui es donde me pierdo.....en esta comparación......no entiendo lo que realmente esta comparando cuando hace Padre->derecho == P......que compara los diferentes punteros de estos nodos??? Please ayudaaaaaa.....un saludo por anticipado*/

if(Padre)

if(Padre->derecho == P) Padre->derecho = Q;

else Padre->izquierdo = Q;

else raiz = Q;

// Reconstruir árbol:

P->derecho = B;

Q->izquierdo = P;

// Reasignar padres:

P->padre = Q;

if(B) B->padre = P;

Q->padre = Padre;

// Ajustar valores de FE:

P->FE = 0;

Q->FE = 0;

}

Steven R. Davidson
2011-08-17 16:57:48

Hola Ricardo,

Efectivamente, compara los valores de ambos punteros:

if( Padre->derecho == P )

Esto significa que comparamos las direcciones de memoria de los nodos apuntados. Si el nodo apuntado por 'Padre->derecho' es el mismo que el nodo apuntado por 'P', el cual en este caso apunta al nodo apuntado por 'nodo' (el parámetro), entonces 'Padre->derecho' apuntará al mismo nodo apuntado por 'Q', que es el mismo nodo apuntado por 'P->derecho' y por tanto por 'nodo->derecho'.

Esto es mejor mirar la explicación anterior en el capítulo acerca de las rotaciones simples a la izquierda: http://c.conclase.net/edd/index.php?cap=008#8_5

Espero haber aclarado la duda.

Steven

Ricardo
2011-08-18 11:23:54

Entiendo que compara los nodos a los cuales apunta, pero lo que no entiendo es que al tener varios punteros cada nodo que estariamos comparando puntero a puntero que apuntasen al mismo sitio, me da la sensación que no me explico....a ver si con un ejemplo concreto lo logro. Aqui hay k hacer una Rotacion simple a la derecha...pero bueno es analogo a la RSI.

          [15]
        [4]  [20]
      [3]
    [2]

Al agregar el nodo con valor 2, se produce un desequilibrio en el arbol en el nodo con valor 4, debido FE de los nodos hacemos una rotación simple a la derecha

Tengo claro (espero) que el arbol debería quedar de la siguiente manera

           [15]
         [3]  [20]
       [2] [4]

El codigo de la rotación sería este

void AVL::RSD(Nodo* nodo)
{
  cout << \\\"RSD\\\" << endl;

/*Despues de recorrer el arbol desde el nodo insertado hacia arriba ajustando los valores del FE llegamos al nodo con valor 4*/

  if(nodo)
  Nodo *Padre = nodo->padre; -->Valor 15
  Nodo *P = nodo;            -->Valor 4
  Nodo *Q = P->izquierdo;    -->Valor 3
  Nodo *B = Q->derecho;      -->Valor NULL

  if(Padre)
    if(Padre->derecho == P) Padre->derecho = Q;
/*No comprendo esta comparacion el Padre->derecho, osea el 20, y P el 4 estan los dos apuntando el 15 y bueno sus punteros izquierdo y derecho apuntan a NULL y a 3 respectivamente..........la duda es jeje...realmente lo que estamos comparando es a donde apuntan los diferentes punteros de estos nodos????  EN ESTE CASO PADRE->DERECHO ES DIFERENTE A P Y EL CODIGO ENTRARIA POR EL PRIMER ELSE PERO REALMENTE NO ENTIENDO PORQUE*/
    else Padre->izquierdo = Q;
  else raiz = Q;

  // Reconstruir árbol:
  P->izquierdo = B;
  Q->derecho = P;

  // Reasignar padres:
  P->padre = Q;
  if(B) B->padre = P;
  Q->padre = Padre;

  // Ajustar valores de FE:
  P->FE = 0;
  Q->FE = 0;
}
Salvador Pozo
2011-08-19 11:04:24

Hola:

Ten en cuenta que el algoritmo de rotación debe ser válido para cualquier configuración inicial del árbol. Las condiciones que no tienen sentido en tu ejemplo, pueden tenerlo (y lo tienen) en otros.

Prueba a ver cómo funciona el código con esta configuración del árbol:

          [15]
          /  \
        [4]  [20]
             /
           [19]
           /
         [17]

En este caso, P apunta al nodo de valor 20, Q al de valor 19, y padre al de valor 15.

  if(Padre)
    if(Padre->derecho == P) Padre->derecho = Q;

Ahora se cumplen las condiciones de los dos if: el nodo padre apunta a un nodo válido (no es NULL), y Padre->derecho es el nodo P, por lo que se toma un camino diferente para equilibrar el árbol.

En lo que respecta al código, en las rotaciones se comparan punteros, pero el algoritmo lo que compara son subárboles.

El segundo if verifica si el subárbol derecho de Padre es el subárbol P, y actúa en función del resultado.

Steven R. Davidson
2011-08-19 11:36:52

Hola Ricardo,

Bueno, Salvador se me ha adelantado, pero agrego un poco más a lo que ha dicho.

El problema que tienes en tu ejemplo es que has elegido incorrectamente P y Q. Recuerda que las condiciones para hacer una RSD son que un nodo tiene un FE de -2 y su nodo izquierdo tenga un FE de -1. En tu ejemplo, P sería el nodo de valor 15 y Q sería el nodo izquierdo de valor 4.

De todas maneras, como dice Salvador, el código de la implementación de la RSD toma en cuenta si el nodo padre - de P - es nulo o no. Eso sí, el algoritmo sigue siendo el mismo.

Espero que las cosas se vayan aclarando.

Steven

Ricardo
2011-08-19 17:35:49

OOOOOk, ahora todo mucho mas claro.

No aporto nada al hilo con este comentario pero tenia que daros las gracias por vuestras respuestas en tiempo record.

De verdad muchas gracias.

Un saludo Ricardo

Ricardo
2011-08-22 15:07:10

Buenas tardes!!

Estoy intentando mostrar un arbol AVL por pantalla, InOrden....pero no soy capaz. Llevo un par de dias tecleando código pero nada....estoy ya desesperado.

Además no me puedo ayudar de ningún sitio porque todo lo que he visto esta programado de manera recursiva y a mi me lo piden de manera iterativa.

Si alguien me pudiese echar una mano, le estaría eternamente agradecido.

Sin más, un saludo

Ricardo
2011-08-22 15:16:47

Por cierto no puedo crearme una pila e ir guardando los datos ahi para mostrarlos.

Ricardo
2011-08-24 20:21:17

Buenas tardes!

Consegui mostrar el arbol Inoden de manera iterativa :)

Pero ahora tengo otro problema, en el ejemplo de AVL en C++ (que es genial, por cierto). La funcion de borrado tiene un error al actualizar los FE, le estoy dando vueltas y no se como solucionarlo.

Estoy probando con el siguiente arbol:

       [15]         15->FE=1
    [4]    [19]     4->FE=0   19->FE=0 
        [17]  [20]  17->FE=0  20->FE=0

Borro el nodo con valor 19 y el arbol queda asi:

       [15]         15->FE=0 /*ERROR*/ El FE de 15 es 1
    [4]    [20]     4->FE=0   20->FE=-1 
        [17]        17->FE=0  

Esta actualizacion la hacemos en la funcion de Equilibrar,

lo único que se me ocurre es que si el nodo al que tenemos que actualizar su FE es el nodo raíz, solo actualizaremos su FE si la altura del subArbol donde hemos borrado un nodo ha cambiado......

Creeis que es esto lo que falla? Veis otra solución?

Muchas gracias por anticipado

Ricardo
2011-08-25 12:31:48

Lo que he hecho y creo(espero) que podria ser una solución es:

Si el equilibrio del nodo eliminado cambia de 0 a +-1 el forzar a que el algoritmo concluya.

El código sería el siguiente:

// Equilibrar árbol AVL partiendo del nodo nuevo
void AVL::Equilibrar(Nodo *nodo, int rama, bool nuevo)
{
   bool salir = false;

   // Recorrer camino inverso actualizando valores de FE:
   while(nodo && !salir){       
      if(nuevo)
         if(rama == IZQUIERDO) nodo->FE--; // Depende de si añadimos ...
         else                  nodo->FE++;
      else{
         if(rama == IZQUIERDO) nodo->FE++; // ... o borramos
         else                  nodo->FE--;
      }   
      if(nodo->FE == 0) salir = true; // La altura de las rama que
                                      // empieza en nodo no ha variado,
                                      // salir de Equilibrar
      else if(nodo->FE == -2) { // Rotar a derechas y salir:
         if(nodo->izquierdo->FE == 1) RDD(nodo); // Rotación doble
         else RSD(nodo);                         // Rotación simple
         salir = true;
      }
      else if(nodo->FE == 2) {  // Rotar a izquierdas y salir:
         if(nodo->derecho->FE == -1) RDI(nodo); // Rotación doble
         else RSI(nodo);                        // Rotación simple
         salir = true;
      }
      if(!nuevo && (nodo->FE == 1 || nodo->FE == -1)) salir = true; /*ESTA SERÍA LA LINEA QUE HE AGREGADO*/
      if(nodo->padre) 
         if(nodo->padre->derecho == nodo) rama = DERECHO; else rama = IZQUIERDO;
      nodo = nodo->padre; // Calcular FE, siguiente nodo del camino.
   }   
}

Podrías ser un solución? De momento las pruebas que he hizo realizando han actualizado los FE correctamente.

Un saludo

junco
2011-08-29 21:49:38

Vaya veo que las preguntas un poco complejas se obvian!

Salvador Pozo
2011-08-30 11:17:54

Hola:

Perdonad el retraso, hace muchos años que escribí este programa, y me ha costado un poco analizarlo y buscar el error.

Efectivamente, el programa tiene un "bug" en la función de equilibrado. Debería dejar de ajustar los valores de FE cuando ninguna de las dos ramas del nodo actual haya cambiado de altura.

Sin embargo, haciendo algunas pruebas, he encontrado más errores. Por ejemplo, dado este árbol:

      [15]
      /  \
   [ 4]   [19]
    /      / \
[ 2]    [17] [20]
        / \
     [16] [18]

Se producen errores en el FE al intentar borrar el nodo 20.

Repasaré el código y corregiré los ejemplos en los próximos días.

Lamento las molestias.

Gracias Ricardo, por tus mensajes.

Hasta pronto.

Salvador Pozo
2011-08-30 17:42:08

Hola:

Bueno, he corregido algunos errores detectados en el curso, referentes a rotaciones simples, en las que es necesario recalcular los FE después de las rotaciones.

Además, se han corregido varios errores en el programa en C++ (en próximos días lo haré en los programas en C y con plantillas).

Los errores afectaban a las rotaciones simples, pero también a la función de equilibrado, a la de borrado (que fallaba cuando se intentaba eliminar el único nodo de un árbol avl), y otras funciones que fallaban con árboles vacíos.

Hasta pronto.

Paola
2012-01-28 22:09:30

Solo quería agradecerles por su trabajo en esta página, no se imaginan lo mucho que me ha ayudado, incluso mas que mi propio profesor de programación =S ... Muchas Gracias! Excelente trabajo.

Jose
2012-03-20 15:12:06

Mira el ejemplo excelente pero tenia una pregunta como se logra para que puedas trabajar con palabras, vi el codigo que tenias comentada esa parte pero no se como implementar el template de ese tipo de dato .... me pudieran ayudar con ese tema muchas gracias.

Salvador Pozo
2012-03-20 17:05:27

Hola, José:

El ejemplo en C++ sólo define una clase para crear árboles AVL de enteros, si quieres crear árboles de palabras tendrás que reescribir parte del código.

El ejemplo con plantillas es más general, y la parte comentada de la que hablas son los restos de adaptar ese programa a la versión C++ sin plantillas.

Para adaptar el ejemplo para trabajar con palabras necesitas una clase para trabajar con cadenas, puedes usar la de otros ejemplos, definida en "CCadena.h". Luego basta con cambiar el tipo de datos en la declaración del Nodo y en todas las apariciones en que un "int" se refiera al tipo de dato.

Si quieres puedo enviarte un ejemplo.

Hasta pronto.

Jose Tapia
2012-03-21 00:39:57

Hola Salvador, de verdad que te lo agradeceria sucede que tengo que ordenar palabra por palabra, en el arbol ejm

Hola

Alberto Denisse

de esa forma ...

te agradeceria infinitamente que pudieras enviarme el ejemplo en base a lo que nesecito muchisimoas gracias