|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-06-23 14:25:15
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12112/src Modified Files: avl.cpp avlt.cpp avlt.h bst.cpp bst.h Log Message: Index: bst.h =================================================================== RCS file: /cvsroot/avl/avl/src/bst.h,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** bst.h 21 Jun 2004 20:14:36 -0000 1.1 --- bst.h 23 Jun 2004 14:25:05 -0000 1.2 *************** *** 64,68 **** Bst *search(int); //OK void insert(int); //OK ! void erase(int); //No nel caso che di nodo con 2 figli in cui il succ è il figlio destro del nodo da eliminare Bst *max(); //OK Bst *min(); //OK --- 64,68 ---- Bst *search(int); //OK void insert(int); //OK ! void erase(int); //No nel caso di nodo con 2 figli in cui il succ è il figlio destro del nodo da eliminare Bst *max(); //OK Bst *min(); //OK *************** *** 71,74 **** --- 71,75 ---- void print(); + void print1(); }; Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** bst.cpp 21 Jun 2004 20:14:36 -0000 1.1 --- bst.cpp 23 Jun 2004 14:25:05 -0000 1.2 *************** *** 208,212 **** if( !aux1->getParent() ) ! aux2 = root(); else if( aux1 == aux1->getParent()->getLeft() ) --- 208,212 ---- if( !aux1->getParent() ) ! aux2 = root();//Il contrario else if( aux1 == aux1->getParent()->getLeft() ) *************** *** 226,230 **** { aux->erase(); ! // delete aux; } } --- 226,230 ---- { aux->erase(); ! //delete aux; } } *************** *** 324,329 **** } ! /* ! void Bst::print() { printf("\n\n%d\t",value); --- 324,329 ---- } ! ! void Bst::print1() { printf("\n\n%d\t",value); *************** *** 333,339 **** printf("destro-->%d\t",getRight()->getValue()); if( getLeft() ) ! getLeft()->print(); if( getRight() ) ! getRight()->print(); } ! */ --- 333,339 ---- printf("destro-->%d\t",getRight()->getValue()); if( getLeft() ) ! getLeft()->print1(); if( getRight() ) ! getRight()->print1(); } ! Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** avl.cpp 21 Jun 2004 20:14:36 -0000 1.1 --- avl.cpp 23 Jun 2004 14:25:05 -0000 1.2 *************** *** 62,82 **** a = new Avlt(0,1); ! for (int i=0;i<80;i++) { int aaa=(rand()%1000)-500; ! a= a->insert( aaa ); ! //if(i>=10) { ! printf("%d->%d\n",i,aaa); if(!a->checkBalance()) { a->print(); printf("\n-------------------------------------------------------------\n"); ! } } } ! ! //printf("%d",a->checkBalance()); ! a->print(); /*vector<Avlt *> v; v = a->getWrongs(); --- 62,82 ---- a = new Avlt(0,1); ! for (int i=0;i<600;i++) { int aaa=(rand()%1000)-500; ! a = a->insert_ric( aaa ); ! //if(i>=19) { ! /* printf("%d->%d\n",i,aaa); if(!a->checkBalance()) { a->print(); printf("\n-------------------------------------------------------------\n"); ! }*/ } } ! a->erase(1); ! printf("%d",a->checkBalance()); ! // a->print(); /*vector<Avlt *> v; v = a->getWrongs(); Index: avlt.h =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.h,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** avlt.h 21 Jun 2004 20:14:36 -0000 1.1 --- avlt.h 23 Jun 2004 14:25:05 -0000 1.2 *************** *** 52,55 **** --- 52,57 ---- Avlt *insert(int); + Avlt *insert_ric(int); + void erase(int); Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** avlt.cpp 21 Jun 2004 20:14:36 -0000 1.1 --- avlt.cpp 23 Jun 2004 14:25:05 -0000 1.2 *************** *** 131,136 **** } ! Avlt *Avlt::insert(int key) //FARE RICORSIVO (forse viene più elegante) { /* --- 131,190 ---- } + Avlt *Avlt::insert_ric(int key) + { + Avlt *aux; + aux = this; + if(key == getValue()) + return this; + if(key < getValue()) + { + if( getLeft() ) + { + ((Avlt *)getLeft())->insert_ric(key); + setFdb(); + if( getFdb() == 2 ) + if( key < getLeft()->getValue() ) + aux = rightRotate(); + else + { + ((Avlt *)(getLeft()))->leftRotate(); + aux = aux->rightRotate(); + } + } + else + { + setLeft(new Avlt); + getLeft()->setParent(this); + getLeft()->setValue(key); + setFdb(); + } + } + else + { + if( getRight() ) + { + ((Avlt *)getRight())->insert_ric(key); + setFdb(); + if( getFdb() == -2 ) + if( key > getRight()->getValue() ) + aux = leftRotate(); + else + { + ((Avlt *)(getRight()))->rightRotate(); + aux = aux->leftRotate(); + } + } + else + { + setRight(new Avlt); + getRight()->setParent(this); + getRight()->setValue(key); + setFdb(); + } + } + return aux; + } ! Avlt *Avlt::insert(int key) { /* *************** *** 155,159 **** aux = this; aux1 = this; ! aux2 = NULL; while( aux1 ) --- 209,213 ---- aux = this; aux1 = this; ! aux2 = NULL;//si può anche levare una variabile while( aux1 ) *************** *** 165,174 **** { aux1 = (Avlt *)aux1->getLeft(); ! if(aux1) { if( ((Avlt *)(aux2))->getFdb() == 1 ) { aux = aux2; ! if( key < aux1->getValue() ) caso = 1; else --- 219,228 ---- { aux1 = (Avlt *)aux1->getLeft(); ! if(aux1)//per levare una var fare lo shift dopo questo if e la condizione va fatta su aux1->getLeft() { if( ((Avlt *)(aux2))->getFdb() == 1 ) { aux = aux2; ! if( key < aux1->getValue() ) //per levare la var anche qui utilizzare aux1->getLeft()->getValue() caso = 1; else *************** *** 205,252 **** } } ! // if(aux->getRight()) ! // printf("fdb:%d;val:%d",((Avlt *)(aux->getRight()))->getFdb(),((Avlt *)(aux->getRight()))->getValue()); ! /* ! aux1 = new Avlt; ! aux1->setParent( aux2 ); ! aux1->setValue( key ); ! ! if ( key < aux2->getValue() ) ! aux2->setLeft( aux1 ); ! else ! aux2->setRight( aux1 ); ! */ aux->setFdb(); if(aux->getFdb()==2 || aux->getFdb()==-2) { ! switch(caso) ! { ! case 1: ! aux = aux->rightRotate(); ! // printf("<<<<<<<caso1"); ! break; ! case 2: ! if( aux->getLeft() ) ! ((Avlt *)(aux->getLeft()))->leftRotate(); ! aux = aux->rightRotate(); ! // printf("<<<<<<<caso2"); ! ! break; ! case 3: ! aux = aux->leftRotate(); ! // printf("<<<<<<<caso3"); ! ! break; ! case 4: ! if( aux->getRight() ) ! ((Avlt *)(aux->getRight()))->rightRotate(); ! aux = aux->leftRotate(); ! // printf("<<<<<<<caso4"); ! ! break; ! default:; ! } } ! setFdb( aux , aux2 ); //aggiorna il fdb nel percorso giusto ( forse si deve spostare prima delle rotazioni e poi controllare se fdb==2 ) return (Avlt *)root(); } --- 259,289 ---- } } ! aux->setFdb(); if(aux->getFdb()==2 || aux->getFdb()==-2) { ! switch(caso) ! { ! case 1: ! aux = aux->rightRotate(); ! break; ! case 2: ! if( aux->getLeft() ) ! ((Avlt *)(aux->getLeft()))->leftRotate(); ! aux = aux->rightRotate(); ! break; ! case 3: ! aux = aux->leftRotate(); ! break; ! case 4: ! if( aux->getRight() ) ! ((Avlt *)(aux->getRight()))->rightRotate(); ! aux = aux->leftRotate(); ! break; ! default:; ! } } ! setFdb( aux , aux2 ); ! return (Avlt *)root(); } *************** *** 254,257 **** --- 291,363 ---- void Avlt::erase(int key) { + Avlt *aux1, *aux2; + + if(key == getValue()) + { + if ( !getLeft() || !getRight() ) + aux1 = this; + else + aux1 = (Avlt *)successor(); + + if( getLeft() ) + { + aux2 = (Avlt *)getLeft(); + setLeft( NULL ); + } + else + { + aux2 = (Avlt *)getRight(); + setRight( NULL ); + } + + if( aux2 ) + aux2->setParent( aux1->getParent() ); + + if( !aux1->getParent() ) + aux2 = (Avlt *)root();//Il contrario + else + if( aux1 == aux1->getParent()->getLeft() ) + aux1->getParent()->setLeft( aux2 ); + else + aux1->getParent()->setRight( aux2 ); + + if( aux1 != this ) + setValue( aux1->getValue() ); + setFdb(); + return; + } + + if(key < getValue()) + { + if( getLeft() ) + { + ((Avlt *)getLeft())->erase( key ); + setFdb(); + if( getFdb() == -2 ) + if( ((Avlt *)getRight())->getFdb() == +1) + { + ((Avlt *)getRight())->rightRotate(); + leftRotate(); + } + else + leftRotate(); + } + } + else + { + if( getRight() ) + { + ((Avlt *)getRight())->erase( key ); + setFdb(); + if( getFdb() == 2 ) + if( ((Avlt *)getRight())->getFdb() == -1) + { + ((Avlt *)getLeft())->leftRotate(); + rightRotate(); + } + else + rightRotate(); + } + } } *************** *** 262,265 **** --- 368,372 ---- bool l, r; l = r = true; + setFdb(); if( getLeft() ) l = ((Avlt *)getLeft())->checkBalance(); |
