二進制搜索樹刪除

Question

我目前正在C++中使用二叉搜索樹，我已經到了必須編寫刪除/刪除功能（使用遞歸方法，x = change(x)）的階段。我有兩種選擇：

• 停止在要刪除的節點的父節點處;

• 去的節點刪除，然後調用，將
  返回父

方法1功能：更便宜，更多的代碼

方法2：更少的代碼，更貴

哪種方法比較好，爲什麼？

Answer 1

最好的方法是遍歷到要刪除的節點的父節點，然後刪除該節點。最終使用這種方法你總是訪問子節點，因爲你總是必須確認子節點是你想要刪除的節點。

Answer 2

我發現寫數據結構的最有效的形式通常是以下psuedocode格式。

function someActionOnTree() { 
     return someActionOnTree(root) 
    } 

    function someActionOnTree (Node current) { 
     if (current is null) { 
       return null 
     } 
     if (current is not the node I seek) { 
       //logic for picking the next node to move to 
       next node = ... 

       next node = someActionOnTree(next node) 
     } 
     else { 
       // do whatever you need to do with current 
       // i.e. give it a child, delete its memory, etc 
       current = ... 
     } 
     return current; 
    } 

這個遞歸函數遞歸遍歷數據結構的頂點集。對於算法的每一次迭代，它要麼尋找一個節點來重新開啓函數，而是用算法在該節點上迭代的值覆蓋數據結構對該節點的引用。否則，它會覆蓋節點的值（並可能執行一組不同的邏輯）。最後，該函數返回對參數節點的引用，這對覆蓋步驟是必不可少的。

這通常是我在C++中爲樹形數據結構找到的最有效的代碼形式。這些概念也適用於其他結構 - 您可以使用此表單的遞歸，其中返回值始終是對數據結構的平面表示中的固定點的引用（基本上，總是返回任何應該在您的位置正在看）。

下面是這種風格的應用程序的二叉搜索樹刪除功能，以美化我的觀點。

function deleteNodeFromTreeWithValue(value) { 
    return deleteNodeFromTree(root, value) 
} 

function deleteNodeFromTree(Node current, value) { 
    if (current is null) return null 
    if (current does not represent value) { 
      if (current is greater than my value) { 
       leftNode = deleteNodeFromTree(leftNode, value) 
      } else { 
       rightNode = deleteNodeFromTree(rightNode, value) 
      } 
     } 
     else { 
      free current's memory 
      current = null 
     } 
     return current 
} 

顯然，還有很多其他的方式來寫這樣的代碼，但是從我的經驗，這已經被證明是最有效的方法。請注意，由於硬件已經緩存了節點，因此性能不會被覆蓋指針所擊中。如果你正在尋求提高搜索樹的性能，我建議尋找專業樹，如自平衡（AVL樹），B樹，紅黑樹等。

Answer 3

我不同意那些是你唯一的兩個選擇。

我認爲一個更簡單的解決方案是問每個節點天氣它應該被刪除。如果它決定是，那麼它被刪除並返回應該替換它的新節點。如果它決定不，那麼它會自行返回。

// pseudo code. 
deleteNode(Node* node, int value) 
{ 
    if (node == NULL) return node; 

    if (node->value == value) 
    { 
     // This is the node I want to delete. 
     // So delete it and return the value of the node I want to replace it with. 
     // Which may involve some shifting of things around. 
     return doDelete(node); 
    } 
    else if (value < node->value) 
    { 
     // Not node. But try deleting the node on the left. 
     // whatever happens a value will be returned that 
     // is assigned to left and the tree will be correct. 
     node->left = deleteNode(node->left, value); 
    } 
    else 
    { 
     // Not node. But try deleting the node on the right. 
     // whatever happens a value will be returned that 
     // is assigned to right and the tree will be correct. 
     node->right = deleteNode(node->right, value); 
    } 
    // since this node is not being deleted return it. 
    // so it can be assigned back into the correct place. 
    return node; 
}