25/01/17 22:24
light00
Buonasera, sto implementando un RBT per un progetto universitario, ma il codice ha un paio di bug..
Quando provo ad inserire nell'albero la sequenza di numeri 1 2 3 4 5 6 7 .. arrivati all'8 mi da segmentation fault!
Inoltre quando inserisco una quindicina di nodi, mi da sempre errore di segmentation fault.
L'altro bug è nel delete : A volte quando cancello la radice mi da segment, a volte non riesce proprio a cancellarla..
Per favore, se potete datemi na mano, perchè sto sbattendo la testa ma non riesco a capire dove siano gli errori :/
Questo il codice :
Quando provo ad inserire nell'albero la sequenza di numeri 1 2 3 4 5 6 7 .. arrivati all'8 mi da segmentation fault!
Inoltre quando inserisco una quindicina di nodi, mi da sempre errore di segmentation fault.
L'altro bug è nel delete : A volte quando cancello la radice mi da segment, a volte non riesce proprio a cancellarla..
Per favore, se potete datemi na mano, perchè sto sbattendo la testa ma non riesco a capire dove siano gli errori :/
Questo il codice :
Metodo insert
Codice: Seleziona tutto
void RBtree::insert()
{
int z,i=0;
cout<<"\nEnter key of the node to be inserted: "; cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
Metodo insertfix
Codice: Seleziona tutto
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
t->color='b';
return;
}
while(t->parent!=NULL&&t->parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
}
Metodo delete
Codice: Seleziona tutto
void RBtree::del()
{
if(root==NULL)
{
cout<<"\nEmpty Tree." ;
return ;
}
int x;
cout<<"\nEnter the key of the node to be deleted: "; cin>>x;
node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x) p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<"\nElement Not Found.";
return ;
}
else
{
cout<<"\nDeleted Element: "<<p->key;
cout<<"\nColour: "; if(p->color=='b')
cout<<"Black\n";
else
cout<<"Red\n"; if(p->parent!=NULL)
cout<<"\nParent: "<<p->parent->key;
else
cout<<"\nThere is no parent of the node. "; if(p->right!=NULL)
cout<<"\nRight Child: "<<p->right->key;
else
cout<<"\nThere is no right child of the node. "; if(p->left!=NULL)
cout<<"\nLeft Child: "<<p->left->key;
else
cout<<"\nThere is no left child of the node. ";
cout<<"\nNode Deleted."; if(p->left==NULL||p->right==NULL)
y=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
if(y->right!=NULL)
q=y->right;
else
q=NULL;
}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b' && q != NULL )
delfix(q);
}
}
Metodo delete fix
Codice: Seleziona tutto
void RBtree::delfix(node *p)
{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
s->color='r';
leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}
Ringrazio in anticipo chi mi aiuterà :D :D
Top
Ultima modifica effettuata da light00 04/02/17 18:31
aaa
