Balancear arbol AVL

Iniciado por aynerd2ag, 8 Noviembre 2010, 03:21 AM

0 Miembros y 1 Visitante están viendo este tema.

aynerd2ag

Hola necesito ayuda para balancear el nodo en un arbol AVL
ya cree el insertar y borrar.... lo q necesito es balancear el nodo q acabo de insertar...
llevo dias intentando hacerlo pero no funciona al 100%...
si alguien me lo pasa seria genial..
les agradezco mucho su ayuda...

mi trabajo lo tengo en java Netbeans... por si alguien lo quiere
todo lo grafico perfectamente... solo le falta balancear


Gracias

elmath.-

Hola, nose si ya lo solucionaste, por las dudas te respondo igual.

estos serian los procedimientos para las rotaciones:


void AVLPRotarLL (AVLProgramas* &P){
    AVLProgramas* aux = P->izq->der;
   P->izq->der = P;
   P->izq->factor = 0;
   AVLProgramas* aux2 = P->izq;
   P->izq = aux;
   P->factor = 0;
   P = aux2;
};
void AVLPRotarRR (AVLProgramas* &P){
    AVLProgramas* aux = P->der->izq;
   P->der->izq = P;
   P->der->factor = 0;
   AVLProgramas* aux2 = P->der;
   P->der = aux;
   P->factor = 0;
   P = aux2;
};
void AVLPRotarLR (AVLProgramas* &P){
    AVLPRotarRR(P->izq);
    AVLPRotarLL(P);
};
void AVLPRotarRL (AVLProgramas* &P){
    AVLPRotarLL(P->der);
    AVLPRotarRR(P);
};

Y despues en el insertar segun el factor de balanceo que te quede ves que rotaciones debes aplicar.

Espero que te haya quedado claro, cualquier cosa pregunta.

Saludos

egyware

Hola, te recomiendo que busques este libro http://bit.ly/aDRoO9 "Introduction to algorithms / Thomas H. Cormen ... [et al.]" ahi hay un pseudo-codigo en Pascal el cual es super facil de traducir a cualquier lenguaje (te lo digo por que no se pascal xD) yo en esa ocación lo traduje a C++, pero sera facil traducirlo a Java.
En el libro solo sale la rotación a la derecha(o la izquierda) pero la otra rotación es analoga a la otra.

Saludos!!