c++ - 二叉搜索树节点移除

Question

我一直在尝试为二叉搜索树实现删除功能，但无法让它在所有情况下都能正常工作。

这是我最近的尝试:

Node* RBT::BST_remove(int c)
{
    Node* t = get_node(c);
    Node* temp = t;

    if(t->get_left() == empty)
        *t = *t->get_left();
    else if(t->get_right() == empty)
        *t = *t->get_right();
    else if((t->get_left() != empty) && (t->get_right() != empty))
    {
        Node* node = new Node(t->get_data(), t->get_parent(), t->get_colour(), t->get_left(), t->get_right());
        *t = *node;
    }

    return temp;
}

Node* RBT::get_node(int c)
{
    Node* pos = root;

    while(pos != empty)
    {
        if(c < pos->get_data())
            pos = pos->get_left();
        else if(c == pos->get_data())
            return pos;
        else
            pos = pos->get_right();
    }

    return NULL;
}

t 是一个节点，empty 只是一个没有任何内容的节点。

我只是想交换值，但出现运行时错误。有什么想法吗？

编辑:我将返回 temp 以便之后将其删除。

谢谢

Answer 1

首先，您的最后一个 else if 条件子句是多余的。用 else 子句替换它。

其次，如果您将指向要删除的节点的指针作为参数，我认为这会让事情变得更容易。您可以编写一个 find() 函数来查找给定键的节点。我当然假设您可以更改函数签名。如果可以将要删除的节点作为参数，则可以专注于删除节点，而不是添加用于查找节点的逻辑。否则，仍然编写 find() 函数并使用它来获取指向相关节点的指针。

当您删除二叉搜索树中的节点时，您必须保持顺序，这样树才不会失去完整性。回想一下，树中有一个特定的顺序支持元素的快速检索。所以，列举可能的情况:

1. 要删除的节点没有子节点。这很简单:只需释放其资源即可。
2. 该节点有一个子节点。这也相当简单。释放节点并用其子节点替换它，因此子节点保留已删除节点在树中的位置。
3. 该节点有两个 child 。我们称节点为 D。找到 D 的左子树的最右边的 child 。我们称此节点为 R。将 R 的值赋给 D，并删除 R(如本算法中所述)。请注意，R 可以有零个或一个 child 。

第三种情况，如图所示:

         .
        .
       .
      /
     D
    / \
   /\  .
  /  \
 /    \
+------+
        \
         R
        /
       ?