SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Diabliyo en Sábado 10 de Abril de 2004, 22:04

Título: Ayuda Con Avl !!
Publicado por: Diabliyo en Sábado 10 de Abril de 2004, 22:04
Hola:

Bueno tengo dificultades para realizar mi Arbol AVL, pero aqui les va la explicacion lo mas clara y entendible que puedo sobre el problema que tengo :D

NOTA:: aparte de MI codigo, me apoyo en el codigo que esta en el tuto de c.conclase.com (ya que es el unico sitio donde encontre sobre este tema) (tambien les pego los codigos del c.conclase)

El AVL o Equilibrio del Arbol solo realiza en las funciones de INSERTAR y BORRAR un NODO, lo demas sigue normal como un Arbol Binario de Busqueda (ABB), al igual cuento con 5 funciones:

-Equilibrar
-RSD (Rotacion Simple a la Derecha)
-RSI (Rotacion Simpel a la Izquierda)
-RDD (Rotacion Doble a la Derecha)
-RDI (Rotacion Doble a la Izquierda)

Aqui esta el codigo de MI funcion de INSERTAR.

Código: Text
  1. struct avl
  2.   {
  3.   int dato;
  4.   struct avl *izq;
  5.   struct avl *der;
  6.   }*raiz;
  7.  
  8. enum {IZQUIERDO, DERECHO};
  9.  
  10. /*Insertar*/
  11. struct avl *insertar( struct avl *raiz2, struct avl *hoja, int num )
  12.    {
  13.    if( !hoja )
  14.       {
  15.       hoja= (struct avl *) malloc( sizeof( struct avl ) );
  16.       hoja->izq= NULL;
  17.       hoja->der= NULL;
  18.       hoja->dato= num;
  19.       hoja->FE= 0;
  20.       if( !raiz ) return hoja;
  21.       else if( num<raiz2->dato )
  22.          {
  23.          aux= raiz;
  24.          raiz2->izq= hoja;
  25.          equilibrar( aux, raiz2, IZQUIERDA, VERDADERO );
  26.          }
  27.       else
  28.          {
  29.          aux= raiz;
  30.          raiz2->der= hoja;
  31.          equilibrar( aux, raiz2, DERECHA, VERDADERO );
  32.         }
  33.       return hoja;
  34.       }
  35.    else if( num<hoja->dato )
  36.       insertar( hoja, hoja->izq, num );
  37.    else
  38.       insertar( hoja, hoja->der, num );
  39.    return raiz;
  40.    }
  41.  

Bueno en  MI codigo ya esta TODO bien, ya que al insertar un NODO, se manda llamar la funcion EQUILIBRAR y dentro de ella se llevane stos valores que significan:

AUX= nodo que apunta al INICIO del Arbol (osea al primer NODO insertado).
RAIZ2=  este puntero LIGADO o APUNTA la rama IZQ o DEr hacia el nodo INSERTADO. (ya sea IZQ o DER).
DERECHA ó IZQUIERDA= solo indica la posicion del nodo que se inserto, para saber hacia DONDE haremos al rotacion.
VERDADERO= parametro para recorrer TODO el arbol dentro de la funcion de EQUILIBRAR. Mientras sea VERDADERO estara recorriendo el Arbol Completo y rotandolo.

--------------------------------------------------------------------------------------

Ahora aqui esta el codigo de C.CONCLASE de la funcion EQUILIBRAR !!!...

Código: Text
  1. /* Equilibrar árbol AVL partiendo del nodo nuevo */
  2. void Equilibrar(Arbol *a, pNodo nodo, int rama, int nuevo)
  3. {
  4.   int salir = FALSE;
  5.  
  6.   /* Recorrer camino inverso actualizando valores de FE: */
  7.   while(nodo && !salir) {
  8.      if(nuevo)
  9.         if(rama == IZQUIERDO) nodo->FE--; /* Depende de si añadimos ... */
  10.         else                  nodo->FE++;
  11.      else
  12.         if(rama == IZQUIERDO) nodo->FE++; /* ... o borramos */
  13.         else                  nodo->FE--;
  14.      if(nodo->FE == 0) salir = TRUE; /* La altura de las rama que
  15.                                         empieza en nodo no ha variado,
  16.                                         salir de Equilibrar */
  17.      else if(nodo->FE == -2) { /* Rotar a derechas y salir: */
  18.         if(nodo->izquierdo->FE == 1) RDD(a, nodo); /* Rotación doble  */
  19.         else RSD(a, nodo);                         /* Rotación simple */
  20.         salir = TRUE;
  21.      }
  22.      else if(nodo->FE == 2) {  /* Rotar a izquierdas y salir: */
  23.         if(nodo->derecho->FE == -1) RDI(a, nodo); /* Rotación doble  */
  24.         else RSI(a, nodo);                        /* Rotación simple */
  25.         salir = TRUE;
  26.      }
  27.      if(nodo->padre)   /*AHI QUE INTERPRETAR ESTO EN MI CODIGO*/
  28.         if(nodo->padre->derecho == nodo) rama = DERECHO; else rama = IZQUIERDO;
  29.      nodo = nodo->padre; /* Calcular FE, siguiente nodo del camino. */
  30.   }
  31. }
  32.  
  33.  

Ahora aqui esta MI codigo de la funcion EQUILIBRAR !!!

Código: Text
  1. /*Funciones de Equilibrio*/
  2.  
  3. void equilibrar( struct avl *raiz, struct avl *nodo, int rama, int nuevo )
  4.    {
  5.    int salir= FALSO;
  6.  
  7.    while( nodo && !salir )
  8.       {
  9.       if( nuevo )
  10.          {
  11.          if( rama == IZQUIERDA ) nodo->FE--;
  12.          else nodo->FE++;
  13.          }
  14.       else
  15.          {
  16.          if( rama == IZQUIERDA ) nodo->FE++;
  17.          else nodo->FE--;
  18.          }
  19.       if( nodo->FE == 0 ) salir= VERDADERO;
  20.       else if( nodo->FE == -2 )
  21.          {
  22.          if( nodo->izq->FE == 1 ) RDD( raiz, nodo );
  23.          else RSD( raiz, nodo );
  24.          salir= VERDADERO;
  25.          }
  26.       else if( nodo->FE == 2 )
  27.          {
  28.          if( nodo->der->FE == -1 ) RDI( raiz, nodo );
  29.          else RSI( raiz, nodo );
  30.          salir= VERDADERO;
  31.          }
  32.       /*falta AQUI*/
  33.       }
  34.    }
  35.  
  36.  

Como ven AQUI esta mi problema, ya que NO se como interpretar el pedazo de codigo que va en la parte donde esta mi comenario: /*falta AQUI*/. El Pedazo de codigo que tengo que interpretar esta en la funcion de Equilibrar de C.CONCLASE, puesta mas arriba de mi codigo y señalando con el comentario: /*AHI QUE INTERPRETAR ESTO EN MI CODIGO*/.

Bueno NO es que sea webon o flojo, pero ya me duele la cabeza de tanto pensar, y pue sla verdad me urge ya que me falta poco para ENTRAR de vacaciones (osea a mis clases normales), y pues entrando SON MIS EXAMENES, y pues este tema lo tengo atrazado :(....

Quien se tome la molestia porfavor....muchas gracias !!

Acepto comentarios, pero porfavor ayudenme !!

byeeeeeeeeeee
Título: Re: Ayuda Con Avl !!
Publicado por: Diabliyo en Sábado 10 de Abril de 2004, 22:16
Hola:

Aqui les dejo el codigo de c.conclase del Arbol AVL. (el codigo solo incluye: la estructura, funcion INSERTAR, funcion RSD, RSI, RDD, RDI, funcion Borrar).

Al igual dentro dle ZIP biene MI codigo.(incluye TODO).


Ya que si no se les hes comodo estar leyendo el codigo, ya que no explico la funcion del puntero  *padre  que va dentro del codigo de C.CONCLASE, pues qui tienen los 2 codigo...

Gracias de Antemano a quien me quiera yudar !!

byeeee