C++ - 删除 AVL 树中的节点

Question

我目前正在尝试用 C++ 实现 AVL 树，到目前为止，除了删除节点之外，我几乎已经完成了所有工作。

1) 有人可以确认我删除节点的算法是正确的吗？

• 在树中找到要删除的节点
• 如果该节点有 0 个子节点:删除该节点
• 否则，如果该节点有1个 child :删除该节点，并重新链接他的 child
• else (2 children): 找到它的后继者，并与它的后继者交换要删除的节点。然后重复删除节点的步骤(现在是它的后继者所在的位置)。
• 插入后重新平衡树(它将递归地重新平衡树...)

我已经这样做了，但我不确定的部分是我删除节点的步骤。我是否还必须删除对该节点的引用，或者它会被管理？ (因为我传入的参数是一个Node*&，但是后继者只是函数中的一个Node*。。。)

我不确定我说得很清楚，如果您需要更多详细信息，请告诉我。

(我会发布一些代码，但不幸的是我说法语，所以我想你不会从中理解太多)

Answer 1

如果节点是使用“new”创建的，则绝对需要明确删除。他们的问题将是哪里。如果您要删除节点(假设没有其他人需要该节点的内容)，那么您还应该在完成从树中删除节点后删除节点本身。

现在，对节点的引用是另一回事。如果引用是方法参数定义的产物，则您不必对它做任何事情。在堆栈上创建引用以帮助方法调用。如果我还记得我的 C++，引用永远不会为 null，这意味着永远不必说对不起(糟糕的笑话)，呃永远不必删除它们。

[编辑] OP 说，“因为我传入了一个 Node*& 参数，但是函数中的后继者只是一个 Node*...)”所以我假设你的意思是这样的:

void removeNode(Node*& node) 

然后调用

void foo()
{
    Node* n = new Node();
    // for example
    removeNode(n);
}

我的 C++ 有点生疏，但这里的想法是 'n' 是一个指针，但 removeNode() 的参数类型是对指针的引用。调用者不知道涉及引用，它只是传递 'n' 期望 arg 类型是指向节点的指针 (Node*)。编译器将引用创建为参数的包装器，因此只有被调用者知道该引用。由于引用是在堆栈上创建的，因此当 removeNode() 返回时它将被正确地“管理”。 'n' 指向的节点仍然需要删除，问题是应该由哪个代码来处理它。

首先想到的是“removeNode()”来执行此操作。一个问题是它只有对它的引用，如果删除指针(引用的目标)，引用将为空，这是一个坏主意/不允许。一想到尝试它的语法就让我感到畏缩。

因此，让客户端代码来执行此操作，如下所示:

void foo()
{
    Node* n = new Node();
    // for example
    removeNode(n);
    delete n;
}

基本上，您需要对节点指针的范围有一个计划。只要它是一致的，你就可以用几种不同的方式来做到这一点。如果您希望 removeNode() 处理删除，则将参数类型更改为指针而不是引用并记录调用，以便预期它既会从树中删除节点，也会删除内存。