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

Question

我正在进行旋转，并尝试根据我调用的方法将已经进入我的二叉搜索树的类(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; 
}

提前致谢。

Answer 1

好像

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