BST删除实际上并没有删除

Question

我有这个删除函数，它将 BST 中的一个节点作为参数来删除它。它在做任何事情之前检查三种情况：

如果节点没有children - 那么直接删除节点
如果节点有一个 child - 那么只需将节点替换为 child
如果节点有两个children - 在右树中找到最小的节点，将其替换为我们要删除的节点（实质上删除它）然后删除我们找到的最小节点

前两种情况有效，但最后一种情况有两个 children。这种情况的代码如下

AccNode* smallest = pointer->getRight();
bool foundSmallest = false;

// Find the smallest node in the right branch
while (foundSmallest == false) {
    if (smallest->getLeft() == NULL && smallest->getRight() == NULL) {
        foundSmallest = true;
    } else {
        if (smallest->getLeft() == NULL && smallest->getRight() != NULL) {
            smallest = smallest->getRight();
        } else {
            smallest = smallest->getLeft();
        }
    }
}

// Replace the node we want to delete with the data in
// smallest node we found and delete smallest node in that tree
pointer->setData(smallest->getData());
delete smallest;

为了进一步调试，Xcode 有一些非常酷的工具可以让您可视化树，我发现了一些非常有趣的东西。在我们到达 delete smallest; 行之前，树中最小的节点看起来像这样

我们删除该行后它看起来像这样

这是怎么回事？我使用指针的方式有问题吗？

编辑： 我刚刚意识到一件事。在树上的图像 post 删除中，在折叠起来的部分中，右侧节点不再为 NULL，现在具有值。我打开它，它是我们想要从一开始就删除的节点的整个右分支（所以是原始指针的右分支）。所以我觉得我现在肯定在指针上做错了什么。关于它是什么的任何线索？

Answer 1

您忘记将指向最小的指针（在最小的 parent 节点中）置空。这使得该指针成为一个 悬空指针 ，一个指向已释放内存的指针。调试器显示此类内存的任意内容，在许多情况下就是之前的内容。

您需要跟踪 parent 节点。

另外，当前的逻辑在不能左分支时右分支，右分支是可能的。但这会导致一个节点具有更大的价值，包括其所有 children。所以这个逻辑不好。

在 parent 中复制数据、删除和清零指针的替代方法是重新排列树（将最小的节点移动到您真正要删除的节点所在的位置），然后直接删除您真正要删除的节点。这有两个优点，一是通常做的工作更少，二是保持指向节点的其他指针有效。

Niklaus Wirth 的书“算法 + 数据结构 = 程序”对此 gem 很少。我阅读了它基于 Pascal 的原始版本。我相信现在有一个基于Oberon的免费电子版。

一般建议：在现代 C++ 中，使用 nullptr 代替宏 NULL 可能是个好主意。一般来说，它更安全。

此外，而不是

foundSmallest == false

只需⁽¹⁾写入

not foundSmallest

或

!foundSmallest

^{⁽¹⁾ 对于至少一个不完全 standard-compliant 的编译器，您必须包含 <iso646.h> header 才能使用保留字 and、or 和 not 作为运算符。但是，这可以通过命令行中的强制包含指令来完成。它不需要在代码中显示。}

Answer 2

删除smallest的记忆后，无法再阅读。简直就是垃圾数据。可能有道理，也可能没有，但不能保证任何事情。

从算法上讲，正如 Cheers 所指出的，您忘记删除 smallest 节点作为其父节点的子节点。换句话说，它的原始部分仍然指向它。您可以通过跟踪 parent 节点来解决此问题。

Answer 3

您忘记在 Cheers 回答时将指针置空。
我认为您寻找最小节点的算法不正确。要找到 BST 的最小节点，您不应该向右走，因为右子树的任何节点都不少于该节点本身。正确的做法应该是一直往左走，直到没有左子树，也就是没有节点小于那个节点。

BST删除实际上并没有删除

BST delete doesn't actually delete

c++

binary-search-tree