c++ - 如何修复 BST 删除功能中的边缘案例？

Question

假设我的删除尝试按顺序(从左到右)重新平衡树。

我目前正在编写一个 BinarySearchTree 类，我的删除功能目前在大多数情况下都有效(我相信 - 我希望 <3)。我有一些边缘案例需要处理:

• 删除根节点是行不通的，因为它没有父节点。
• 在 next 有两个 child 的最后一种情况下，如果它最左边的后代是右 child 本身，那么 newCurr 将指向 next，这将导致问题，因为 newCurr(又名 next)最终将与 New 交换。

建议的根删除解决方案:

1. 我的解决方案是删除根并使用我的 BST 类的成员函数将 Root 设置为 New(使该节点成为根)，然后将 New 过去所在的位置设置为 0/NULL。

   A:这行得通，但我必须到处进行案例研究。

2. 在 BST 类中有一个虚拟父节点，它只包含根节点，因为它是右手对象(由 billyswong 建议)。

   A:这可能行得通，但我觉得我应该有特殊情况的工作来处理它。

两个 child 删除的建议解决方案:

1. 我的解决办法，就是临时保存New的位置，将New在父节点的位置设置为New的右 child ，然后删除临时指针。

   答:这样可以，但没有我想象的那么优雅。

2. “旋转节点”(不知道我会怎么做，Agor 建议)。

这是我的代码:

if (root()->value() == val)
{
    delete root();
    this->setRoot(New);
    newCurr->setLeft(0);
}    
else if (newCurr == next)
{
    Node *temp = New;
    newCurr->setRight(New->right());
    delete temp;
} 

张贴者请告诉我此代码 1) 是否有效 2) 是否最佳。

编辑:对于我在函数末尾附近不一致地使用驼峰帽感到抱歉。对于我的变量名，我想不出更好的描述，但是 new 是 C++ 中定义的关键字。

Edit2:发布重构代码，但错误仍然存​​在。

void BinarySearchTree::del(int val)
{
//curr refers to the parent of next
//next is the node we will want to delete
    Node* curr = 0;
    Node* next = root(); 

//these will only be used if you get into
//the last case, where you have two children
//on next
    Node* newCurr = curr;
    Node* New = next;

//boolean value to check if you found the value
//in the binary search tree
    bool found;

//set curr and next; will be false if val not found
    found = setCurrAndNext(val, curr, next);


//get next to the node needing deletion
//and set curr to its parent
//pass by ref function  
//return value is that you found it  
    if (found)
    {
        setNewCurrAndNew (newCurr, New);
    }   
    else
    { 
        return;    
    }

/* next is a leaf */

    if (nextIsLeaf(next))
    {
        handleLeafCase(curr, next);
        return;
    }   
/* next has a single child */        
    else if (nextHasSingleChild(next))       
    {
        if(leftIsChild(next))  
        {
            handleLeftCase(curr, next);
        }
        else
        {
            handleRightCase(curr, next);
        }
    }
/* next has two children */    
    else
    {  
       if (newCurr == next)
       {
            Node *temp = New;
            newCurr->setRight(New->right());
            delete temp;
       } 
       else if (next == curr->left())
       {
            if (New == newCurr->left())
            {
               curr->setLeft(New);
               newCurr->setLeft(next);
            }
            else
            {
               curr->setLeft(New);
               newCurr->setRight(next);
            }
       }
       else
       {
            if (New == newCurr->left())
            {
               curr->setRight(New);
               newCurr->setLeft(next);
            }    
            else
            {
               curr->setRight(New);
               newCurr->setRight(next);
            }
       }

       if (next->left() == 0 && next->right() == 0)
       {
            newCurr->setRight(0);
            newCurr->setLeft(0);

            delete next;
       }
       else
       {
            if (next->left() == 0)
            {
               newCurr->setRight(next->left());
            }
            else
            {
               newCurr->setLeft(next->right());
            }

               delete next;
            }
        }
    }
}

Answer 1

我不能给你代码或任何东西，但你正在寻找的是一个“旋转”运算符。基本上，它处理“烦人”的删除情况——当您删除一棵有 2 个 child 的树时，这些 child 都有 2 个 child ，例如根节点，还有树中的任何其他节点。

rotate 所做的基本上是在一个非常局部的区域中，在所涉及的节点之间交换子节点(我知道这是一种创伤)，以便维持子节点的顺序(左边较小，右边较大)。它类似于优先队列的“冒泡”功能。

这是维基百科 ( http://en.wikipedia.org/wiki/Tree_rotation ) 页面。

希望这能让您走上正轨!

编辑回应评论:对不起，我应该解释一下。当我说“树”时，我指的是节点，维基百科页面应该仍然有帮助。由于二叉搜索树的数学递归定义，您可以将每个节点视为其自己的子树，因此我的初始声明(保持不变)。但这只是与你的问题无关，所以继续...... :)