c++ - 二叉搜索树向左旋转

我要进行轮换，并尝试根据我所调用的方法将到我的二进制搜索树的类(class)向左或向右旋转。我的代码中某处有一个错误，我认为我已经将其隔离到旋转方法中，因为每次成功旋转后每次尝试打印时，都会陷入无限循环。我的方法中是否存在某种类型的指针或调用混合？我觉得我的逻辑是正确的，但似乎无法弄清楚该错误在哪里(即使在此方法中也是如此)。

这是我的左旋转方法:

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;
}

提前致谢。

最佳答案

好像

y->getParent()->setParent(x);

应该

y->setParent(x->getParent());

但是在检查x-> getParent为NULL之后执行此操作。

就像是

// Remove this line: y->getParent()->setParent(x);

if(x->getParent() == NULL){
    root = y;
}
else if( x->getParent()->getRight() == x){
    y->setParent(x->getParent());   // Insert this line
    x->getParent()->setLeft(y);
}

编辑:
再次查看代码后，我认为即使x-> getParent()返回NULL，也应调用y-> setParent(x-> getParent())。原因是，如果y成为新的根，则y还应将Parent设置为NULL。

因此，以下代码可能是一个更好的答案:

// Remove this line: y->getParent()->setParent(x);

y->setParent(x->getParent());   // Insert this line

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