samedi 28 mars 2015

Binary search tree left rotation


I'm going over rotations and trying to rotate courses that have been to my binary search tree to the left or right depending on what method I call. There is a bug somewhere in my code and I think I've isolated it to the rotation method since everytime I try to print after I successfully do a rotation, it goes into an infinite loop. Is there some type of pointer or call mixup in my method? I feel that my logic is right but can't seem to figure out where the bug is(or even if it's in this method).


Here's my left rotation method:



bool BinarySearchTree::leftRotate(string number)
{
Course *x, *y;

if (treeSearch(number) == NULL){
return false;
}
else{
x = treeSearch(number);
}

if (x->getRight() == NULL){
return false;
}
else{
y = x->getRight();
x->setRight(y->getLeft());
}

if (y->getLeft() != NULL){
y->getLeft()->setParent(x);
}
y->getParent()->setParent(x);

if(x->getParent() == NULL){
root = y;
}
else if( x->getParent()->getRight() == x){
x->getParent()->setLeft(y);
}
else{
x->getParent()->setRight(y);
}
y->setLeft(x);
x->setParent(y);
return true;
}


Thanks in advance.




Aucun commentaire:

Enregistrer un commentaire