AVL.cpp revision a4030d5ca449e7e384bc699cd249ee704faaeab0
/*
* 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
*/
{
MakeNew();
}
{
MakeDelete();
}
{
for (int i = 0; i < 2; i++)
{
}
balance = 0;
}
void AVLTree::MakeDelete()
{
for (int i = 0; i < 2; i++) {
if (elem[i]) {
}
}
}
{
}
{
if (son[s]) {
return son[s]->leafFromDad(this, s);
}
else if (dad) {
}
}
if (dad) {
}
}
return NULL;
}
{
if (son[s]) {
return son[s]->leafFromDad(this, s);
}
return this;
}
int
{
{
if (dad)
}
else
{
if (balance == 0)
{
balance = 1;
balance = -1;
if (dad)
return avl_no_err;
}
else if (balance > 0)
{
{
balance = 0;
return avl_no_err;
}
{
// cout << "mierda\n";
return avl_bal_err;
}
AVLTree *a = this;
{
a->dad = b;
if (e)
e->dad = a;
if (d)
d->dad = a;
if (c)
c->dad = b;
b->dad = r;
if (r)
{
}
if (racine == a)
racine = b;
a->balance = 0;
b->balance = 0;
return avl_no_err;
}
else
{
{
// cout << "mierda\n";
return avl_bal_err;
}
a->dad = d;
b->dad = d;
if (g)
g->dad = a;
if (e)
e->dad = a;
if (c)
c->dad = b;
if (f)
f->dad = b;
d->dad = r;
if (r)
{
}
if (racine == a)
racine = d;
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)
{
{
balance = 0;
return avl_no_err;
}
{
// cout << "mierda\n";
return avl_bal_err;
}
AVLTree *a = this;
{
a->dad = b;
if (e)
e->dad = a;
if (d)
d->dad = a;
if (c)
c->dad = b;
b->dad = r;
if (r)
{
}
if (racine == a)
racine = b;
a->balance = 0;
b->balance = 0;
return avl_no_err;
}
else
{
{
// cout << "mierda\n";
return avl_bal_err;
}
a->dad = d;
b->dad = d;
if (g)
g->dad = a;
if (e)
e->dad = a;
if (c)
c->dad = b;
if (f)
f->dad = b;
d->dad = r;
if (r)
{
}
if (racine == a)
racine = d;
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
{
if (balance > 0)
{
if (diff < 0)
{
balance = 0;
if (dad)
{
}
return avl_no_err;
}
else if (diff == 0)
{
}
else if (diff > 0)
{
{
// cout << "un probleme\n";
return avl_bal_err;
}
AVLTree *a = this;
if (e->balance > 0)
{
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 (racine == this)
racine = e;
e->balance = 0;
a->balance = 0;
if (r)
{
}
return avl_no_err;
}
else if (e->balance == 0)
{
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 (racine == this)
racine = e;
e->balance = -1;
a->balance = 1;
return avl_no_err;
}
else if (e->balance < 0)
{
{
// cout << "un probleme\n";
return avl_bal_err;
}
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 (racine == this)
racine = f;
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)
{
}
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)
{
{
// cout << "un probleme\n";
return avl_bal_err;
}
AVLTree *a = this;
if (e->balance < 0)
{
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 (racine == this)
racine = e;
e->balance = 0;
a->balance = 0;
if (r)
{
}
return avl_no_err;
}
else if (e->balance == 0)
{
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 (racine == this)
racine = e;
e->balance = 1;
a->balance = -1;
return avl_no_err;
}
else if (e->balance > 0)
{
{
// cout << "un probleme\n";
return avl_bal_err;
}
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 (racine == this)
racine = f;
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)
{
}
return avl_no_err;
}
}
else if (diff == 0)
{
}
else if (diff > 0)
{
balance = 0;
if (dad)
{
}
return avl_no_err;
}
}
return avl_no_err;
}
/*
* removal
*/
int
{
int remDiff = 0;
return res;
}
int
{
{
{
// cout << "pas normal\n";
return avl_rm_err;
}
{
diff = -1;
if (dad)
{
}
}
else
{
diff = 1;
if (dad)
{
}
}
if (racine == this)
}
{
diff = 0;
if (dad)
{
diff = -1;
diff = 1;
}
if (dad)
{
}
if (racine == this)
}
{
diff = 0;
if (dad)
{
diff = -1;
diff = 1;
}
if (dad)
{
}
if (racine == this)
}
else
{
diff = 0;
if (dad)
{
diff = -1;
diff = 1;
}
if (dad)
{
}
if (racine == this)
}
balance = 0;
return avl_no_err;
}
/*
* insertion
*/
int
{
return res;
}
int
{
{
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)
{
{
// cout << "ngou?\n";
return avl_ins_err;
}
}
else if (insertType == found_on_right)
{
{
// cout << "ngou?\n";
return avl_ins_err;
}
}
else if (insertType == found_between)
{
{
// cout << "ngou?\n";
return avl_ins_err;
}
{
}
{
}
}
else if (insertType == found_exact)
{
{
// cout << "ngou?\n";
return avl_ins_err;
}
// et on insere
{
{
// cout << "ngou?\n";
return avl_ins_err;
}
}
else
{
}
}
else
{
// cout << "code incorrect\n";
return avl_ins_err;
}
}
return avl_no_err;
}
void
{
if (dad)
{
}
{
}
{
}
}
{
if (of)
}
{
if (l)
if (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:fileencoding=utf-8:textwidth=99 :