/* * AVL.cpp * nlivarot * * Created by fred on Mon Jun 16 2003. * */ #include "AVL.h" /* * the algorithm explanation for this code comes from purists.org, which seems to have disappeared since * it's a classic AVL tree rebalancing, nothing fancy */ AVLTree::AVLTree() { MakeNew(); } AVLTree::~AVLTree() { MakeDelete(); } void AVLTree::MakeNew() { for (int i = 0; i < 2; i++) { elem[i] = NULL; son[i] = NULL; } dad = NULL; balance = 0; } void AVLTree::MakeDelete() { for (int i = 0; i < 2; i++) { if (elem[i]) { elem[i]->elem[1 - i] = elem[1 - i]; } elem[i] = NULL; } } AVLTree *AVLTree::Leftmost() { return leafFromDad(NULL, LEFT); } AVLTree *AVLTree::leaf(AVLTree *from, Side s) { if (from == son[1 - s]) { if (son[s]) { return son[s]->leafFromDad(this, s); } else if (dad) { return dad->leaf(this, s); } } else if (from == son[s]) { if (dad) { return dad->leaf(this, s); } } return NULL; } AVLTree *AVLTree::leafFromDad(AVLTree *from, Side s) { if (son[s]) { return son[s]->leafFromDad(this, s); } return this; } int AVLTree::RestoreBalances (AVLTree * from, AVLTree * &racine) { if (from == NULL) { if (dad) return dad->RestoreBalances (this, racine); } else { if (balance == 0) { if (from == son[LEFT]) balance = 1; if (from == son[RIGHT]) balance = -1; if (dad) return dad->RestoreBalances (this, racine); return avl_no_err; } else if (balance > 0) { if (from == son[RIGHT]) { balance = 0; return avl_no_err; } if (son[LEFT] == NULL) { // cout << "mierda\n"; return avl_bal_err; } AVLTree *a = this; AVLTree *b = son[LEFT]; AVLTree *e = son[RIGHT]; AVLTree *c = son[LEFT]->son[LEFT]; AVLTree *d = son[LEFT]->son[RIGHT]; if (son[LEFT]->balance > 0) { AVLTree *r = dad; a->dad = b; b->son[RIGHT] = a; a->son[RIGHT] = e; if (e) e->dad = a; a->son[LEFT] = d; if (d) d->dad = a; b->son[LEFT] = c; if (c) c->dad = b; b->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = b; if (r->son[RIGHT] == a) r->son[RIGHT] = b; } if (racine == a) racine = b; a->balance = 0; b->balance = 0; return avl_no_err; } else { if (son[LEFT]->son[RIGHT] == NULL) { // cout << "mierda\n"; return avl_bal_err; } AVLTree *f = son[LEFT]->son[RIGHT]->son[LEFT]; AVLTree *g = son[LEFT]->son[RIGHT]->son[RIGHT]; AVLTree *r = dad; a->dad = d; d->son[RIGHT] = a; b->dad = d; d->son[LEFT] = b; a->son[LEFT] = g; if (g) g->dad = a; a->son[RIGHT] = e; if (e) e->dad = a; b->son[LEFT] = c; if (c) c->dad = b; b->son[RIGHT] = f; if (f) f->dad = b; d->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = d; if (r->son[RIGHT] == a) r->son[RIGHT] = d; } if (racine == a) racine = d; int old_bal = d->balance; d->balance = 0; if (old_bal == 0) { a->balance = 0; b->balance = 0; } else if (old_bal > 0) { a->balance = -1; b->balance = 0; } else if (old_bal < 0) { a->balance = 0; b->balance = 1; } return avl_no_err; } } else if (balance < 0) { if (from == son[LEFT]) { balance = 0; return avl_no_err; } if (son[RIGHT] == NULL) { // cout << "mierda\n"; return avl_bal_err; } AVLTree *a = this; AVLTree *b = son[RIGHT]; AVLTree *e = son[LEFT]; AVLTree *c = son[RIGHT]->son[RIGHT]; AVLTree *d = son[RIGHT]->son[LEFT]; AVLTree *r = dad; if (son[RIGHT]->balance < 0) { a->dad = b; b->son[LEFT] = a; a->son[LEFT] = e; if (e) e->dad = a; a->son[RIGHT] = d; if (d) d->dad = a; b->son[RIGHT] = c; if (c) c->dad = b; b->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = b; if (r->son[RIGHT] == a) r->son[RIGHT] = b; } if (racine == a) racine = b; a->balance = 0; b->balance = 0; return avl_no_err; } else { if (son[RIGHT]->son[LEFT] == NULL) { // cout << "mierda\n"; return avl_bal_err; } AVLTree *f = son[RIGHT]->son[LEFT]->son[RIGHT]; AVLTree *g = son[RIGHT]->son[LEFT]->son[LEFT]; a->dad = d; d->son[LEFT] = a; b->dad = d; d->son[RIGHT] = b; a->son[RIGHT] = g; if (g) g->dad = a; a->son[LEFT] = e; if (e) e->dad = a; b->son[RIGHT] = c; if (c) c->dad = b; b->son[LEFT] = f; if (f) f->dad = b; d->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = d; if (r->son[RIGHT] == a) r->son[RIGHT] = d; } if (racine == a) racine = d; int old_bal = d->balance; d->balance = 0; if (old_bal == 0) { a->balance = 0; b->balance = 0; } else if (old_bal > 0) { a->balance = 0; b->balance = -1; } else if (old_bal < 0) { a->balance = 1; b->balance = 0; } return avl_no_err; } } } return avl_no_err; } int AVLTree::RestoreBalances (int diff, AVLTree * &racine) { if (balance > 0) { if (diff < 0) { balance = 0; if (dad) { if (this == dad->son[RIGHT]) return dad->RestoreBalances (1, racine); if (this == dad->son[LEFT]) return dad->RestoreBalances (-1, racine); } return avl_no_err; } else if (diff == 0) { } else if (diff > 0) { if (son[LEFT] == NULL) { // cout << "un probleme\n"; return avl_bal_err; } AVLTree *r = dad; AVLTree *a = this; AVLTree *b = son[RIGHT]; AVLTree *e = son[LEFT]; AVLTree *f = e->son[RIGHT]; AVLTree *g = e->son[LEFT]; if (e->balance > 0) { e->son[RIGHT] = a; e->son[LEFT] = g; a->son[RIGHT] = b; a->son[LEFT] = f; if (a) a->dad = e; if (g) g->dad = e; if (b) b->dad = a; if (f) f->dad = a; e->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = e; if (r->son[RIGHT] == a) r->son[RIGHT] = e; } if (racine == this) racine = e; e->balance = 0; a->balance = 0; if (r) { if (e == r->son[RIGHT]) return r->RestoreBalances (1, racine); if (e == r->son[LEFT]) return r->RestoreBalances (-1, racine); } return avl_no_err; } else if (e->balance == 0) { e->son[RIGHT] = a; e->son[LEFT] = g; a->son[RIGHT] = b; a->son[LEFT] = f; if (a) a->dad = e; if (g) g->dad = e; if (b) b->dad = a; if (f) f->dad = a; e->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = e; if (r->son[RIGHT] == a) r->son[RIGHT] = e; } if (racine == this) racine = e; e->balance = -1; a->balance = 1; return avl_no_err; } else if (e->balance < 0) { if (son[LEFT]->son[RIGHT] == NULL) { // cout << "un probleme\n"; return avl_bal_err; } AVLTree *i = son[LEFT]->son[RIGHT]->son[RIGHT]; AVLTree *j = son[LEFT]->son[RIGHT]->son[LEFT]; f->son[RIGHT] = a; f->son[LEFT] = e; a->son[RIGHT] = b; a->son[LEFT] = i; e->son[RIGHT] = j; e->son[LEFT] = g; if (b) b->dad = a; if (i) i->dad = a; if (g) g->dad = e; if (j) j->dad = e; if (a) a->dad = f; if (e) e->dad = f; f->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = f; if (r->son[RIGHT] == a) r->son[RIGHT] = f; } if (racine == this) racine = f; int oBal = f->balance; f->balance = 0; if (oBal > 0) { a->balance = -1; e->balance = 0; } else if (oBal == 0) { a->balance = 0; e->balance = 0; } else if (oBal < 0) { a->balance = 0; e->balance = 1; } if (r) { if (f == r->son[RIGHT]) return r->RestoreBalances (1, racine); if (f == r->son[LEFT]) return r->RestoreBalances (-1, racine); } return avl_no_err; } } } else if (balance == 0) { if (diff < 0) { balance = -1; } else if (diff == 0) { } else if (diff > 0) { balance = 1; } return avl_no_err; } else if (balance < 0) { if (diff < 0) { if (son[RIGHT] == NULL) { // cout << "un probleme\n"; return avl_bal_err; } AVLTree *r = dad; AVLTree *a = this; AVLTree *b = son[LEFT]; AVLTree *e = son[RIGHT]; AVLTree *f = e->son[LEFT]; AVLTree *g = e->son[RIGHT]; if (e->balance < 0) { e->son[LEFT] = a; e->son[RIGHT] = g; a->son[LEFT] = b; a->son[RIGHT] = f; if (a) a->dad = e; if (g) g->dad = e; if (b) b->dad = a; if (f) f->dad = a; e->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = e; if (r->son[RIGHT] == a) r->son[RIGHT] = e; } if (racine == this) racine = e; e->balance = 0; a->balance = 0; if (r) { if (e == r->son[RIGHT]) return r->RestoreBalances (1, racine); if (e == r->son[LEFT]) return r->RestoreBalances (-1, racine); } return avl_no_err; } else if (e->balance == 0) { e->son[LEFT] = a; e->son[RIGHT] = g; a->son[LEFT] = b; a->son[RIGHT] = f; if (a) a->dad = e; if (g) g->dad = e; if (b) b->dad = a; if (f) f->dad = a; e->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = e; if (r->son[RIGHT] == a) r->son[RIGHT] = e; } if (racine == this) racine = e; e->balance = 1; a->balance = -1; return avl_no_err; } else if (e->balance > 0) { if (son[RIGHT]->son[LEFT] == NULL) { // cout << "un probleme\n"; return avl_bal_err; } AVLTree *i = son[RIGHT]->son[LEFT]->son[LEFT]; AVLTree *j = son[RIGHT]->son[LEFT]->son[RIGHT]; f->son[LEFT] = a; f->son[RIGHT] = e; a->son[LEFT] = b; a->son[RIGHT] = i; e->son[LEFT] = j; e->son[RIGHT] = g; if (b) b->dad = a; if (i) i->dad = a; if (g) g->dad = e; if (j) j->dad = e; if (a) a->dad = f; if (e) e->dad = f; f->dad = r; if (r) { if (r->son[LEFT] == a) r->son[LEFT] = f; if (r->son[RIGHT] == a) r->son[RIGHT] = f; } if (racine == this) racine = f; int oBal = f->balance; f->balance = 0; if (oBal > 0) { a->balance = 0; e->balance = -1; } else if (oBal == 0) { a->balance = 0; e->balance = 0; } else if (oBal < 0) { a->balance = 1; e->balance = 0; } if (r) { if (f == r->son[RIGHT]) return r->RestoreBalances (1, racine); if (f == r->son[LEFT]) return r->RestoreBalances (-1, racine); } return avl_no_err; } } else if (diff == 0) { } else if (diff > 0) { balance = 0; if (dad) { if (this == dad->son[RIGHT]) return dad->RestoreBalances (1, racine); if (this == dad->son[LEFT]) return dad->RestoreBalances (-1, racine); } return avl_no_err; } } return avl_no_err; } /* * removal */ int AVLTree::Remove (AVLTree * &racine, bool rebalance) { AVLTree *startNode = NULL; int remDiff = 0; int res = Remove (racine, startNode, remDiff); if (res == avl_no_err && rebalance && startNode) res = startNode->RestoreBalances (remDiff, racine); return res; } int AVLTree::Remove (AVLTree * &racine, AVLTree * &startNode, int &diff) { if (elem[LEFT]) elem[LEFT]->elem[RIGHT] = elem[RIGHT]; if (elem[RIGHT]) elem[RIGHT]->elem[LEFT] = elem[LEFT]; elem[LEFT] = elem[RIGHT] = NULL; if (son[LEFT] && son[RIGHT]) { AVLTree *newMe = son[LEFT]->leafFromDad(this, RIGHT); if (newMe == NULL || newMe->son[RIGHT]) { // cout << "pas normal\n"; return avl_rm_err; } if (newMe == son[LEFT]) { startNode = newMe; diff = -1; newMe->son[RIGHT] = son[RIGHT]; son[RIGHT]->dad = newMe; newMe->dad = dad; if (dad) { if (dad->son[LEFT] == this) dad->son[LEFT] = newMe; if (dad->son[RIGHT] == this) dad->son[RIGHT] = newMe; } } else { AVLTree *oDad = newMe->dad; startNode = oDad; diff = 1; oDad->son[RIGHT] = newMe->son[LEFT]; if (newMe->son[LEFT]) newMe->son[LEFT]->dad = oDad; newMe->dad = dad; newMe->son[LEFT] = son[LEFT]; newMe->son[RIGHT] = son[RIGHT]; if (dad) { if (dad->son[LEFT] == this) dad->son[LEFT] = newMe; if (dad->son[RIGHT] == this) dad->son[RIGHT] = newMe; } if (son[LEFT]) son[LEFT]->dad = newMe; if (son[RIGHT]) son[RIGHT]->dad = newMe; } newMe->balance = balance; if (racine == this) racine = newMe; } else if (son[LEFT]) { startNode = dad; diff = 0; if (dad) { if (this == dad->son[LEFT]) diff = -1; if (this == dad->son[RIGHT]) diff = 1; } if (dad) { if (dad->son[LEFT] == this) dad->son[LEFT] = son[LEFT]; if (dad->son[RIGHT] == this) dad->son[RIGHT] = son[LEFT]; } if (son[LEFT]->dad == this) son[LEFT]->dad = dad; if (racine == this) racine = son[LEFT]; } else if (son[RIGHT]) { startNode = dad; diff = 0; if (dad) { if (this == dad->son[LEFT]) diff = -1; if (this == dad->son[RIGHT]) diff = 1; } if (dad) { if (dad->son[LEFT] == this) dad->son[LEFT] = son[RIGHT]; if (dad->son[RIGHT] == this) dad->son[RIGHT] = son[RIGHT]; } if (son[RIGHT]->dad == this) son[RIGHT]->dad = dad; if (racine == this) racine = son[RIGHT]; } else { startNode = dad; diff = 0; if (dad) { if (this == dad->son[LEFT]) diff = -1; if (this == dad->son[RIGHT]) diff = 1; } if (dad) { if (dad->son[LEFT] == this) dad->son[LEFT] = NULL; if (dad->son[RIGHT] == this) dad->son[RIGHT] = NULL; } if (racine == this) racine = NULL; } dad = son[RIGHT] = son[LEFT] = NULL; balance = 0; return avl_no_err; } /* * insertion */ int AVLTree::Insert (AVLTree * &racine, int insertType, AVLTree * insertL, AVLTree * insertR, bool rebalance) { int res = Insert (racine, insertType, insertL, insertR); if (res == avl_no_err && rebalance) res = RestoreBalances ((AVLTree *) NULL, racine); return res; } int AVLTree::Insert (AVLTree * &racine, int insertType, AVLTree * insertL, AVLTree * insertR) { if (racine == NULL) { racine = this; return avl_no_err; } else { if (insertType == not_found) { // cout << "pb avec l'arbre de raster\n"; return avl_ins_err; } else if (insertType == found_on_left) { if (insertR == NULL || insertR->son[LEFT]) { // cout << "ngou?\n"; return avl_ins_err; } insertR->son[LEFT] = this; dad = insertR; insertOn(LEFT, insertR); } else if (insertType == found_on_right) { if (insertL == NULL || insertL->son[RIGHT]) { // cout << "ngou?\n"; return avl_ins_err; } insertL->son[RIGHT] = this; dad = insertL; insertOn(RIGHT, insertL); } else if (insertType == found_between) { if (insertR == NULL || insertL == NULL || (insertR->son[LEFT] != NULL && insertL->son[RIGHT] != NULL)) { // cout << "ngou?\n"; return avl_ins_err; } if (insertR->son[LEFT] == NULL) { insertR->son[LEFT] = this; dad = insertR; } else if (insertL->son[RIGHT] == NULL) { insertL->son[RIGHT] = this; dad = insertL; } insertBetween (insertL, insertR); } else if (insertType == found_exact) { if (insertL == NULL) { // cout << "ngou?\n"; return avl_ins_err; } // et on insere if (insertL->son[RIGHT]) { insertL = insertL->son[RIGHT]->leafFromDad(insertL, LEFT); if (insertL->son[LEFT]) { // cout << "ngou?\n"; return avl_ins_err; } insertL->son[LEFT] = this; this->dad = insertL; insertBetween (insertL->elem[LEFT], insertL); } else { insertL->son[RIGHT] = this; dad = insertL; insertBetween (insertL, insertL->elem[RIGHT]); } } else { // cout << "code incorrect\n"; return avl_ins_err; } } return avl_no_err; } void AVLTree::Relocate (AVLTree * to) { if (elem[LEFT]) elem[LEFT]->elem[RIGHT] = to; if (elem[RIGHT]) elem[RIGHT]->elem[LEFT] = to; to->elem[LEFT] = elem[LEFT]; to->elem[RIGHT] = elem[RIGHT]; if (dad) { if (dad->son[LEFT] == this) dad->son[LEFT] = to; if (dad->son[RIGHT] == this) dad->son[RIGHT] = to; } if (son[RIGHT]) { son[RIGHT]->dad = to; } if (son[LEFT]) { son[LEFT]->dad = to; } to->dad = dad; to->son[RIGHT] = son[RIGHT]; to->son[LEFT] = son[LEFT]; } void AVLTree::insertOn(Side s, AVLTree *of) { elem[1 - s] = of; if (of) of->elem[s] = this; } void AVLTree::insertBetween(AVLTree *l, AVLTree *r) { if (l) l->elem[RIGHT] = this; if (r) r->elem[LEFT] = this; elem[LEFT] = l; elem[RIGHT] = r; } /* Local Variables: mode:c++ c-file-style:"stroustrup" c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) indent-tabs-mode:nil fill-column:99 End: */ // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :