如何修复BST删除功能中的边缘情况?

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

我目前正在编写一个binarysearchtree类,我的delete函数目前在大多数情况下都有效(我相信-我希望<3)。我有一些边缘案件要处理:

• 删除根节点不起作用,因为它没有父节点。
• 在next有两个子代的最后一种情况下,如果其最左边的右后代是右后代本身,那么newcurr将指向next,这将导致问题,因为newcurr(又称next)最终将与new交换。

根删除的建议解决方案:

1. 我的解决方案是删除根并使用bst类的成员函数将根设置为new(使该节点成为根),然后将new的位置设置为0/null。

   A:这行,但我得把案件放得到处都是。

2. 在bst类中有一个虚拟的父节点,它只将根节点作为右手对象(由billyswong建议)。

   A:这可能行得通,但我觉得我应该有专门的个案工作来处理。

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

1. 我的解决方案是临时存储新位置,将新位置在其父级中设置为新的右子级,然后删除临时指针。

   A:这行得通,但没有我想象的那么优雅。

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)是最佳的。

编辑:很抱歉,我在函数末尾前后不一致地使用了camelcaps。我想不出对变量名更好的描述,但是 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;
            }
        }
    }
}