|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-06-21 20:14:46
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26739/src Added Files: avl.cpp avlt.cpp avlt.h bst.cpp bst.h Log Message: --- NEW FILE: bst.h --- /*************************************************************************** * Copyright (C) 2004 by Gianlorenzo D'Angelo * * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #ifndef BST_H #define BST_H #include "stdio.h" /** @author Gianlorenzo D'Angelo */ class Bst { private: int value; Bst *left; Bst *right; Bst *parent; void erase(); void print_ric( int, int ); public: Bst(); Bst(int); ~Bst(); Bst *getLeft(); Bst *getRight(); Bst *getParent(); int getValue(); void setLeft(Bst *); void setRight(Bst *); void setParent(Bst *); void setValue(int); //operazioni sugli alberi Bst *root(); bool isLeaf(); //OK bool isRoot(); //OK int level(); //OK int nodes(); //OK int leaves(); int height(); //operazioni tipiche dei BST 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 Bst *predecessor(); //OK Bst *successor(); //OK void print(); }; #endif --- NEW FILE: bst.cpp --- /*************************************************************************** * Copyright (C) 2004 by Gianlorenzo D'Angelo * * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #include "bst.h" Bst::Bst() { Bst(0); } Bst::Bst(int val) { value = val; left = right = parent = NULL; } Bst::~Bst() { } Bst *Bst::getLeft() { return left; } Bst *Bst::getRight() { return right; } Bst *Bst::getParent() { return parent; } int Bst::getValue() { return value; } void Bst::setLeft(Bst * l) { left = l; } void Bst::setRight(Bst * r) { right = r; } void Bst::setParent(Bst * p) { parent = p; } void Bst::setValue(int val) { value = val; } Bst *Bst::root() { Bst *aux; for( aux=this; aux->getParent(); aux=aux->getParent() ); return aux; } bool Bst::isLeaf() { return !(getLeft()||getRight()); } bool Bst::isRoot() { return !getParent(); } int Bst::level() { Bst *aux; int count; for( count=0,aux=this; aux->getParent(); aux=aux->getParent(),count++ ); return count; } int Bst::nodes() { if( isLeaf() ) return 1; int node = 1; if( getLeft() ) node += getLeft()->nodes(); if( getRight() ) node += getRight()->nodes(); return node; } int Bst::leaves() { if( isLeaf() ) return 1; int node = 0; if( getLeft() ) node = getLeft()->leaves(); if( getRight() ) node += getRight()->leaves(); return node; } int Bst::height() { if( isLeaf() ) return 0; int l, r; l = r = 0; if( getLeft() ) l = getLeft()->height(); if( getRight() ) r = getRight()->height(); return 1 + ( l>r ? l : r ); } Bst *Bst::search(int key) { Bst *aux; aux = this; while( aux ) { if( aux->getValue() == key ) return aux; if( key < aux->getValue() ) aux = aux->getLeft(); else aux = aux->getRight(); } return NULL; } void Bst::insert(int key) { Bst *aux1, *aux2; aux1 = this; aux2 = NULL; while( aux1 ) { if ( key == aux1->getValue() ) return; aux2 = aux1; if ( key < aux1->getValue() ) aux1 = aux1->getLeft(); else aux1 = aux1->getRight(); } aux1 = new Bst; aux1->setParent( aux2 ); aux1->setValue( key ); if ( key < aux2->getValue() ) aux2->setLeft( aux1 ); else aux2->setRight( aux1 ); } void Bst::erase() { Bst *aux1, *aux2; if ( !getLeft() || !getRight() ) aux1 = this; else aux1 = successor(); if( getLeft() ) { aux2 = getLeft(); setLeft( NULL ); } else { aux2 = getRight(); setRight( NULL ); } if( aux2 ) aux2->setParent( aux1->getParent() ); if( !aux1->getParent() ) aux2 = root(); else if( aux1 == aux1->getParent()->getLeft() ) aux1->getParent()->setLeft( aux2 ); else aux1->getParent()->setRight( aux2 ); if( aux1 != this ) setValue( aux1->getValue() ); } void Bst::erase(int val) { Bst *aux; aux = search( val ); if( aux ) { aux->erase(); // delete aux; } } Bst *Bst::max() { Bst *aux; for( aux=this; aux->getRight(); aux=aux->getRight() ); return aux; } Bst *Bst::min() { Bst *aux; for( aux=this; aux->getLeft(); aux=aux->getLeft() ); return aux; } Bst *Bst::predecessor() { if ( getLeft() ) return getLeft()->max(); Bst *aux1, *aux2; aux1 = getParent(); aux2 = this; while( aux1 && aux2==aux1->getLeft() ) { aux2 = aux1; aux1 = aux1->getParent(); } return aux1; } Bst *Bst::successor() { if ( getRight() ) return getRight()->min(); Bst *aux1, *aux2; aux1 = getParent(); aux2 = this; while( aux1 && aux2==aux1->getRight() ) { aux2 = aux1; aux1 = aux1->getParent(); } return aux1; } /*void Bst::print_ric(Bst* root, int level) { int i; if(root == NULL) return; print_ric(root->left, level+1); printf("%d[%d],", root->getValue(),level); print_ric(root->right, level+1); } void Bst::print() { print_ric(this, 0); }*/ void Bst::print_ric(int lev, int tab) { if(level() == lev) { printf("%d ",getValue()); } else { if( getLeft() ) getLeft()->print_ric( lev , tab ); if( getRight() ) getRight()->print_ric( lev , tab ); } } void Bst::print() { int lev, alt; Bst *aux; aux = this; alt = this->height(); lev = 0; while( lev != alt +1 ) { print_ric(lev, alt - lev); printf("\n"); lev++; } } /* void Bst::print() { printf("\n\n%d\t",value); if( getLeft() ) printf("sinistro-->%d\t",getLeft()->getValue()); if( getRight() ) printf("destro-->%d\t",getRight()->getValue()); if( getLeft() ) getLeft()->print(); if( getRight() ) getRight()->print(); } */ --- NEW FILE: avl.cpp --- /*************************************************************************** * Copyright (C) 2004 by Gianlorenzo D'Angelo * * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #ifdef HAVE_CONFIG_H #include <config.h> #endif #include "avlt.h" #include <iostream> #include <cstdlib> using namespace std; int main(int argc, char *argv[]) { // Bst a(1 ), *b; Avlt *a, *b; /* a.insert(3); a.insert(5); a.insert(4); a.insert(2); a.insert(10); a.insert(-10); a.insert(-1); a.insert(20); a.insert(-20); a.insert(-25); a.insert(-15); a.insert(-6); a.insert(-200); a.insert(-300); a.insert(-400); a.insert(-500); a.insert(-600); a.insert(-700); */ /* a.insert(6); a.insert(3); // a.insert(-3); */ 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(); for (int i=0; i<v.size(); i++) cout << (v[i])->getValue() << endl; */ // printf("%d",a->getFdb()); // a->print(); // b = (a.getLeft())->getLeft()->getRight(); // printf("%d",b->getValue()); return EXIT_SUCCESS; } --- NEW FILE: avlt.h --- /*************************************************************************** * Copyright (C) 2004 by Gianlorenzo D'Angelo * * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #ifndef AVLT_H #define AVLT_H #include <vector> #include <bst.h> using namespace std; /** @author Gianlorenzo D'Angelo */ class Avlt : public Bst { private: int fdb; Avlt *rightRotate(); Avlt *leftRotate(); public: Avlt(); Avlt( int, int ); ~Avlt(); void setFdb( int ); void setFdb(); void setFdb(Avlt *, Avlt *); int getFdb(); bool checkBalance(); vector<Avlt *> getWrongs(); Avlt *insert(int); void erase(int); }; #endif --- NEW FILE: avlt.cpp --- /*************************************************************************** * Copyright (C) 2004 by Gianlorenzo D'Angelo * * jah@notebook0 * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #include "avlt.h" Avlt::Avlt() : Bst() { Avlt( 0,0 ); } Avlt::Avlt(int s,int val) : Bst(val) { setFdb( s ); } void Avlt::setFdb( int s ) { fdb = s; } void Avlt::setFdb() { int l, r; l = r = 0; if( getLeft() ) l = getLeft()->height() + 1; if( getRight() ) r = getRight()->height() + 1; setFdb( l-r ); } void Avlt::setFdb( Avlt * start , Avlt * end) { while( end != start ) { end->setFdb(); //forse si può migliorare end = (Avlt *)end->getParent(); } if( end ) end->setFdb(); } int Avlt::getFdb() { return fdb; } Avlt *Avlt::leftRotate() //dd { Avlt *aux; aux = (Avlt *)getRight(); if( aux ) { setRight( getRight()->getLeft() ); if( getRight() ) getRight()->setParent( this ); aux->setLeft( this ); aux->setParent( getParent() ); if( getParent() ) if( this == getParent()->getLeft() ) getParent()->setLeft( aux ); else getParent()->setRight( aux ); setParent( aux ); ((Avlt *)(aux->getLeft()))->setFdb(); return aux; } else return this; } Avlt *Avlt::rightRotate() //ss { Avlt *aux; aux = (Avlt *)getLeft(); if( aux ) { setLeft( getLeft()->getRight() ); if( getLeft() ) getLeft()->setParent( this ); aux->setRight( this ); aux->setParent( getParent() ); if( getParent() ) if( this == getParent()->getLeft() ) getParent()->setLeft( aux ); else getParent()->setRight( aux ); setParent( aux ); ((Avlt *)(aux->getRight()))->setFdb(); return aux; } else return this; } Avlt *Avlt::insert(int key) //FARE RICORSIVO (forse viene più elegante) { /* 1. si cerca il posto dove inserire l'elemento (come in bst) e intanto si memorizza il più basso +1 o -1 (aux) 2. si inserisce 3. si aggiornano i fdb del cammino tra aux e il nodo inserito (stanno tutti a 0 tranne aux) 4. se il fdb di aux è +1 [o -1] e l'inserimento viene fatto a destra [o sinistra] di aux l'albero si ribilancia da solo altrimenti viene fatta una rotazione: 4 casi: fdb==1 si inserisce in ll => rightrotation si inserisce in lr => leftrotation e poi rightrotation fdb==-1 si inserisce in rr => leftrotation si inserisce in rl => rightrotation e poi leftrotation */ Avlt *aux1, *aux2, *aux; int caso=0; aux = this; aux1 = this; aux2 = NULL; while( aux1 ) { if ( key == aux1->getValue() ) return this; aux2 = aux1; if ( key < aux1->getValue() ) { aux1 = (Avlt *)aux1->getLeft(); if(aux1) { if( ((Avlt *)(aux2))->getFdb() == 1 ) { aux = aux2; if( key < aux1->getValue() ) caso = 1; else caso = 2; } } else { aux2->setLeft(new Avlt); aux2->getLeft()->setParent(aux2); aux2->getLeft()->setValue(key); } } else { aux1 = (Avlt *)aux1->getRight(); if(aux1) { if( ((Avlt *)(aux2))->getFdb() == -1 ) { aux = aux2; if( key < aux1->getValue() ) caso = 4; else caso = 3; } } else { aux2->setRight(new Avlt); aux2->getRight()->setParent(aux2); aux2->getRight()->setValue(key); } } } // 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(); } void Avlt::erase(int key) { } bool Avlt::checkBalance() { if( isLeaf() ) return true; bool l, r; l = r = true; if( getLeft() ) l = ((Avlt *)getLeft())->checkBalance(); if( getRight() ) r = ((Avlt *)getRight())->checkBalance(); return l && r && (getFdb()==0 || getFdb()==-1 || getFdb()==1); } vector<Avlt *> Avlt::getWrongs() { vector<Avlt *> v , aux; if( getLeft() ) { aux = ((Avlt *)getLeft())->getWrongs(); for(int i=0;i < aux.size();i++) v.push_back(aux[i]); } if( getRight() ) { aux = ((Avlt *)getRight())->getWrongs(); for(int i=0;i<aux.size();i++) v.push_back(aux[i]); } if( getFdb()!=0 && getFdb()!=-1 && getFdb()!=1 ) v.push_back(this); return v; } Avlt::~Avlt() { } |
