二叉查找树左旋

Question

我将进行轮换，并尝试根据我调用的方法将进入我的二叉搜索树的课程向左或向右轮换。我的代码中某处有一个错误，我想我已经将它与旋转方法隔离开来，因为每次我在成功旋转后尝试打印时，它都会进入无限循环。我的方法中是否存在某种类型的指针或调用混淆？我觉得我的逻辑是正确的，但似乎无法弄清楚错误在哪里（或者即使它在这个方法中）。

这是我的左旋转方法：

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

二叉查找树左旋

Binary search tree left rotation

c++

rotation

binary-search-tree

data-structures