首页 文章

BST删除实际上并不删除

提问于
浏览 次
2

我有这个删除功能，它将BST中的节点作为参数删除它 . 它在做任何事之前检查三个案例：

  • 如果节点没有子节点 - 那么只需删除节点

  • 如果节点有一个子节点 - 那么只需用子节点替换该节点

  • 如果节点有两个子节点 - 找到右侧树中的最小节点，将其替换为我们要删除的节点（实际上是删除它），然后删除我们找到的最小节点

前两个案例有效，但不是最后一个有两个孩子的案例 . 这种情况的代码如下

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; 行之前，树中的最小节点看起来像这样

Smallest node pre deletion

删除行后，它看起来像这样

Smallest node post deletion

那么这里发生了什么？我用我使用指针的方式弄乱了什么吗？

Edit: 我刚刚意识到了什么 . 在删除树上的图像中，在折叠的部分中，右节点不再是NULL并且现在具有值 . 我打开它，它是我们想要从头开始删除的节点的整个右分支（所以原始指针的右分支） . 所以我觉得我现在肯定对指针做错了 . 关于它是什么的任何线索？

c++ binary-search-tree

3 回答

  • 0

    你忘了指向最小的指针（在最小的父节点中） . 这将指针留作 dangling pointer ，指向已经释放的内存的指针 . 调试器显示这种内存的任意内容，在许多情况下就是之前的内容 .

    您需要跟踪父节点 .

    此外，当当前逻辑不能向左分支并且右分支时，当前逻辑分支正确 . 但这会导致一个 Value 更高的节点，包括其所有孩子 . 所以这个逻辑是不合适的 .

    在父项中复制数据，删除和清空指针的替代方法是重新排列树（将最小的节点移动到您确实要删除的节点的位置），然后只删除您真正要删除的节点 . 这具有通常做较少工作的两个优点，并且保持对节点的其他指针有效 .

    Niklaus Wirth的书“Algorithms Data Structures = Programs”对此非常宝贵 . 我读了基于Pascal的原版 . 我相信现在有一个基于Oberon的免费电子版 .

    一般建议：在现代C中，使用 nullptr 而不是宏 NULL 是个好主意 . 一般而言，它更安全 .

    而且，而不是

    foundSmallest == false

    只是（1）写

    not foundSmallest

    要么

    !foundSmallest

    （1）至少有一个不完全符合标准的编译器，你必须包含<iso646.h>头文件才能使用保留字，而不是作为运算符 . 但是，这可以通过命令行中的强制include指令来完成 . 它不需要在代码中显示 .

    回复于
  • 2

    在删除 smallest 所持的内存之后，它不仅仅是垃圾数据 . 它可能有意义，它可能没有，但是没有任何保证 .

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

    回复于
  • 0

    • 当Cheers回答时，你忘了将指针归零 .

    • 我不认为你找到最小节点的算法是正确的 . 要找到BST的最小节点，您不应该正确，因为右子树的任何节点都不小于节点本身 . 正确的方法应该是继续向左，直到它没有左子树，这意味着没有节点小于那个节点 .

    回复于

相关问题