在二进制搜索树中删除

Question

教师向我们解释了该算法，用于删除二进制搜索树中的节点，但我无法理解它在要删除的节点时，它是如何工作的，只有一个孩子（我已经知道它是理论步的方式）。

算法：

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

.

例如，我想删除节点号 $ 7 $ ：

但是，最终结果应该是这个吗？

Answer 1

你选择肯定是正确的。

但是，您的老师的代码也没有问题。这是来自CLR的摘录。

插入和删除的操作导致由二进制搜索树表示的动态集更改。必须修改数据结构以反映此更改，但以这样的方式，即二进制搜索树属性继续保持。

我们肯定更喜欢以最简单的方式或最快的方式进行操作。但是，不需要修改必须以最简单的方式或以任何简单的方式制作。它也没有要求修改以最快的方式或甚至以任何快速的方式进行。所有它都要求删除的操作应该生成另一个二进制搜索树，该树具有来自给定二进制搜索树的所有节点，而没有该特定节点（并且没有更多节点）。剩下的节点如何形成二进制搜索树是完全没有约束的。

另一方面，您的老师的代码可能是作业的最短明确代码。我越多，我发现的更加聪明才智。

Answer 2

你的绘图是正确的解决方案，但是你对你的教师代码解析不准确（你的错误是代码的错误）

当我第一次看到你的qi没有彻底读取代码，我想（从第一个照片/绘图）你的老师正在为特殊类型的BST进行删除操作，具有比相对顺序的额外条件，但是这不是案例

从bst删除时（尝试遵循您的代码变量，z是要删除的节点）

如果z是叶节点（没有孩子），只需用null替换父指针到它

如果z有1个孩子（无论是左还是右无关紧要）使父指针指向其唯一的子女

是非常简单的编码，在半伪代码

if（z.left== null）{pharesal_delete（z，zright）;返回（）; //要么我们只有正确的子树或没有 }

//在这里，我们肯定有一个左子树

if（z. right== null）{photical_delete（z，z.left）;返回（）; }

// physical_delete有替换为第二个参数，你的老师代码中的所有循环都是找出它的IT incase我们有两个子树

如果z有2个孩子，那么你必须选择其中一个拿它的地方，这里是你的老师的代码（不在之前的情况下）

在你的照片中想象你删除“5”这个长代码是用于调整其2个孩子的剩余子树（如何将7＆3及其孩子链接到节点12保持BST约束）

如果你需要详细的跟踪，我们可能会这样做，但只有你发现这个有用作为一个开始