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。然後，你必須刪除一個單一的孩子，你知道該怎麼做。

請注意，除非刪除完成，否則樹狀態不一致。如果你同時工作，這很重要。