使用不同的方法刪除具有2個節點的二叉搜索樹中的節點？

我已經找遍了這一點，但只有一個方法：使用不同的方法刪除具有2個節點的二叉搜索樹中的節點？

找到節點的前任（或繼承人）刪除

取代前任（或繼承人）節點

刪除前身（或繼承人）

，但我覺得我們也可以做到這樣：

將要刪除的節點的右（或左）元素拉下來，即只是用右（或左）元素替換要刪除的元素，並繼續這樣做直到我們遇到葉，然後刪除葉。簡而言之，繼續使用它的右（或左）元素替換要刪除的元素，並繼續這樣做直到我們到達葉，然後刪除葉。

那麼這種方法是正確的嗎？

來源

2017-03-31 coderAJ

如果我正確理解您的方法，聽起來不像是可行的。你爲什麼不用一棵簡單的樹畫出我們的照片（三個級別應該這樣做），並向我們展示步驟？ –

不幸的是，CoderAj，Vikhram提供的解決方案是刪除BST中節點的正確方法。你的方法聽起來不錯，但在第一次取代本身時失敗。

讓我們在樹上研究你的方法。

      8 
        5    25 
      3   7  23  30 
        6   24 27 35

讓我們刪除根即8
第1步：

     25    //replaced 8 by 25 
       5    25 
     3   7  23  30 
       6   24 27 35

23和24是小於25，但他們還是在於它的右子樹。

因此，你最終的樹看起來像這樣

     25 
       5    30 
     3   7  23  35 
       6   24 27

它看起來並不像一個二叉搜索樹。

來源

2017-03-31 19:45:48 daBigBug

我不真正按照你的算法（他們倆）。但下面是如何從二叉樹中刪除一個節點（非平衡）。

找到要刪除的節點。此節點只能由現有樹中的2個節點中的一個節點替換。
1.右側子節點的最左側（即最小）元素或
2.左側子節點的最右側（即最大）元素。

替換它取可用的和你做

沒有其他節點需要從
1. RightMostChildOfLeftChild（）< CurrentNode（）< LeftMostChildOfRightChild（）RightMostChildOfLeftChild之間存在
2.無節點移動（）和LeftMostChildOfRightChild（）除了CurrentNode（）

現在，如果您不介意移動一堆節點，那麼還有很多其他方法可以刪除節點。

希望能夠爲您澄清它。

來源

2017-03-31 17:38:51 Vikhram

這是我們到處得到的一般解決方案，但我覺得我們也可以這樣做：繼續用正確的元素替換要刪除的元素，並繼續這樣做直到我們到達葉，然後刪除葉。 – coderAJ

對於您的主題問題，答案是肯定的;另一種方法是可能的。

我在Sedgewick的書中發現了一種方法，在我看來，這種方法更簡單一般。

首先，考慮兩個BST的專有連接ts和tg'. Exclusive means that all the keys in ts are smaller than any key in tg`。因此，考慮以下情況：

現在，如果你選擇ts或tg之間的任何根的獨家根加入，你可以遞歸定義最終結果如下：

在這種情況下，連接的根是ts的根。

請注意，當您刪除BST中的完整節點時，其子節點是前面定義的兩個專用樹。

Node * remove_from_bst(Node *& root, int key) noexcept 
{ 
    if (root == nullptr) 
    return nullptr; // In this case key was not found 

    // recursive searching of the key to be removed 
    if (key < root->key) 
    return remove_from_bst(root->left, key); 
    else if (root->key < key) 
    return remove_from_bst(root->right, key); 

    // here root contains a node with key 
    Node * ret_val = root; // backup of root that we will remove from tree 
    root = join_exclusive(root->left, root->right); // new subtree 

    return ret_val; // we return the removed node 
}

現在，整理，我們定義了join_exclusive()操作：所以，你可以如下定義刪除

Node * join_exclusive(Node *& ts, Node *& tg) noexcept 
{ 
    if (ts == nullptr) 
    return tg; 

    if (tg == nullptr) 
    return ts; 

    tg->left = join_exclusive(ts->right, tg->left); 

    ts->right = tg; 
    Node * ret_val = ts; 
    ts = tg = nullptr; // empty the trees 

    return ret_val; 
}

這種方法對我來說更容易，因爲它管理的三種情況：葉子，不完整的節點和完整的節點。另外，密鑰永遠不會在節點之間移動。

由於獨佔連接的根是任意選擇的，所以這種方法以及您的方法引入了一種傾向於使隨機樹不平衡的偏差（根選擇不是隨機完成的）。然而，正如Roura爲他們的隨機樹所建議的那樣，您可以將每個子樹的基數存儲在節點中。然後，你可以執行一個抽象的過程來提高每個子樹的基數。通過這種方法，您可以保證該樹總是等於隨機構建的BST

來源

2017-04-01 14:21:07 lrleon

使用不同的方法刪除具有2個節點的二叉搜索樹中的節點？

回答

相關問題