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

Question

我目前正在尝试在C++中实现AVL树，到目前为止，除了节点删除之外，我已经做了几乎所有的事情。

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

• 查找树删除
• 如果节点有0子节点：删除节点
• 否则，如果节点有1个小孩：删除节点，并重新链接了他的孩子
• else（2 children）：找到它的后继者，并交换节点以删除其后继者。然后重复这些步骤以删除节点（现在是其后继者所在的节点）。
• 重新平衡插入后树（它会递归重新平衡树...）

我已经这样做了，但如果我不知道的部分，是一步，我删除节点。我是否也必须删除对节点的引用，否则它将被管理？ （因为我已经通过参数Node * &，但继任者只是该功能中的一个Node *）

我不确定我是否超级清晰，请告诉我，如果您需要更多细节。

（我会发布一些代码，但不幸的是我讲法语，所以你不会明白从中多，我猜）

Answer 1

如果节点用“新”比它需要显式删除创建，绝对。他们的问题将在其中。如果您要删除节点（假定其他人不需要该节点的内容），那么在完成从树中删除节点后，您还应该删除节点本身。

现在，对节点的引用是另一回事。如果引用是方法参数定义的工件，则不必对它做任何处理。该引用是在堆栈上创建的，以帮助进行方法调用。如果我记得我的C++，引用永远不会为null，这意味着永远不必说你对不起（坏玩笑），呃永远不必删除它们。

[编辑] 的OP说，“因为我在参数传递的节点* &，但继任者仅仅是在功能的节点* ...）”，所以我假定你的意思是这样的：

void removeNode(Node*& node) 

，然后使用

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

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

首先想到的是'removeNode（）'来做到这一点。一个问题是它只有一个引用，如果你删除了指针（引用的目标），引用将是空的，这是一个坏主意/不允许。只是想着尝试它的语法让我感到害怕。

因此，在客户端代码来做到这一点，就像这样：

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

基本上，您需要为您的节点指针范围的计划。只要它是一致的，你可以用几种不同的方式来做到这一点。如果你想让removeNode（）处理删除操作，那么将参数类型改为指针而不是引用，并记录调用，所以期望它既从树中删除节点，也删除内存。

Answer 2

问题中棘手的部分是“删除对节点的引用”其实很含糊：根据你认为的“删除引用”，答案可以是“是”或“否”。

正如我所看到的，作为重新链接树的一部分，您将“删除对节点的引用”。关键部分是事实上，你的方法接收节点指针为Node *&：有了这个，你的方法不只是获得指向节点的指针，它接收到一个引用，指向这个指针的存储位置在父节点 。您必须修改此引用以保持树链接完好无损。

所以，如果你的方法做这样的事情：

void deleteNode (Node*& node) { 
    if (node is the right one to delete) { 
     Node * tmp = node; 
     node = node->successor; 
     delete node; 
    } 
    else 
     deleteNode(node->successor); 
} 

分配node = node->successor实际修改之前的节点的后继场。没有这个分配，你的树结构就会被破坏，因为前面的节点的后继字段会指向一个现在解除分配的节点。

Answer 3

我是你在标准C++编码，那么没有什么会为你“管理”。如果你使用智能指针，那么他们会照顾到你的释放。

至于你的接口，我建议remove()函数带一个指向要删除的节点的指针。然后，您不必费心寻找节点，因为它是给定的。尽管如此，请编写find()函数，以便客户端可以自己找到节点。

最后，我不确定我是否按照你的第三种情况，删除的节点有两个孩子。在AVL树中，当一个节点要删除为两个子节点时，可以将其与要删除节点的左子树的最右侧子节点交换。一旦交换，要删除的节点恰好有一个或零个孩子，所以你基本上将问题简化为这两种情况。

例如：

  20 
    40   15 
    60 35  18  10 
80 38 30 19 17 13 8 

在上面的树，如果你想删除节点20然后你用节点30（节点35的孩子），将其交换：

  30 
    40   15 
    60 35  18  10 
80 38 20 19 17 13 8 

，然后取下节点20作为无子节点。如果没有节点30，那么左子树的最右边的子节点将是节点35，并且您将交换节点20。然后，你必须删除一个单一的孩子，你知道该怎么做。

请注意，除非删除完成，否则树状态不一致。如果你同时工作，这很重要。