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
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.
struct avl
{
int dato;
struct avl *izq;
struct avl *der;
}*raiz;
enum {IZQUIERDO, DERECHO};
/*Insertar*/
struct avl *insertar( struct avl *raiz2, struct avl *hoja, int num )
{
if( !hoja )
{
hoja= (struct avl *) malloc( sizeof( struct avl ) );
hoja->izq= NULL;
hoja->der= NULL;
hoja->dato= num;
hoja->FE= 0;
if( !raiz ) return hoja;
else if( num<raiz2->dato )
{
aux= raiz;
raiz2->izq= hoja;
equilibrar( aux, raiz2, IZQUIERDA, VERDADERO );
}
else
{
aux= raiz;
raiz2->der= hoja;
equilibrar( aux, raiz2, DERECHA, VERDADERO );
}
return hoja;
}
else if( num<hoja->dato )
insertar( hoja, hoja->izq, num );
else
insertar( hoja, hoja->der, num );
return raiz;
}
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 !!!...
/* Equilibrar árbol AVL partiendo del nodo nuevo */
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) /*AHI QUE INTERPRETAR ESTO EN MI CODIGO*/
if(nodo->padre->derecho == nodo) rama = DERECHO; else rama = IZQUIERDO;
nodo = nodo->padre; /* Calcular FE, siguiente nodo del camino. */
}
}
Ahora aqui esta MI codigo de la funcion EQUILIBRAR !!!
/*Funciones de Equilibrio*/
void equilibrar( struct avl *raiz, struct avl *nodo, int rama, int nuevo )
{
int salir= FALSO;
while( nodo && !salir )
{
if( nuevo )
{
if( rama == IZQUIERDA ) nodo->FE--;
else nodo->FE++;
}
else
{
if( rama == IZQUIERDA ) nodo->FE++;
else nodo->FE--;
}
if( nodo->FE == 0 ) salir= VERDADERO;
else if( nodo->FE == -2 )
{
if( nodo->izq->FE == 1 ) RDD( raiz, nodo );
else RSD( raiz, nodo );
salir= VERDADERO;
}
else if( nodo->FE == 2 )
{
if( nodo->der->FE == -1 ) RDI( raiz, nodo );
else RSI( raiz, nodo );
salir= VERDADERO;
}
/*falta AQUI*/
}
}
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
