這段代碼爲什麼需要從BST中刪除？

我想了解更多關於二叉樹的知識，並且我遇到了關於如何找到後繼節點（當試圖刪除節點時）的方法，但我很難理解它的一部分。這是代碼。這段代碼爲什麼需要從BST中刪除？

private Node getSuccessor(Node delNode){ 
    Node successorParent = delNode; 
    Node successor = delNode; 
    Node current = delNode.rightChild; 

    while(current != null){ 
     successorParent = successor; 
     successor = current; 
     current = current.leftChild; 
    } // end of if 

    if(successor != delNode.rightChild){ 
     successorParent.leftChild = successor.rightChild; 
     successor.rightChild = delNode.rightChild; 
    } 
    return successor; 


}

我完全理解了while循環以及那裏的內容。我不明白的是if語句，特別是...

successor.rightChild = delNode.rightChild;

我爲什麼要將delNode的右側子項分配給後繼節點的右側子項？爲什麼if語句是必要的？

來源

2017-08-12 Rocky Singh

你自己想出這個最簡單的方法就是運行代碼並觀察兩者之間的區別。 – Carcigenicate

說實話，沒有仔細閱讀核心*，這看起來不像任何普通的「在二叉樹中找到任何東西」的實現，因爲它**修改了樹。然而，一個splay樹通過將查詢的節點移動到樹頂部來修改樹，但是問題中的代碼還不足以實現這一點。 –

@Carcigenicate這是真的！我會盡力做到這一點。 –

getSuccessor（）所做的是找到delNode的後繼者，該節點的最小值大於delNode，即delNode下右側子樹中最左側的節點。然後它將它從正確的子樹中移除，並將右側子樹連接到後繼的右側。

有條件的原因是，如果後繼者是delNode的正確子節點，它已經在右側子樹的頂部，並且不需要從子樹中移出並移動到頂部的。

在接下來的步驟中，delNode將被刪除，後繼將附加到delNode的父節點，並且delNode下的左側子樹將被附加到繼承者的左側。所有這些的影響是將delNote替換爲其後繼者。（這種方法不是從二叉樹中刪除一個節點的最直接的方法，你可以簡單地將右子樹連接到delNode的父節點，左子樹連在後繼節點上，但是這個更復雜的方法有不增加樹的高度的優點，因爲每個節點保持在相同的深度，或者移動靠近根。）

這裏是一個我們要刪除節點3的例子：我們發現它的後繼者是4，我們從右邊的子樹中移除4並將它放在子樹的頂部，然後我們用後繼者4替換節點3，並將左邊的子樹連接到它：

 9            9 
    /\           /\ 
    3 ...      4     4 ... 
/\        \    /\ 
    2 6    6    6    2 6 
//\   /\   /\   //\ 
1 4 7   4 7   5 7   1 5 7 
    \ \   \ \    \     \ 
     5 8   5 8    8     8

（你會去除該節點後發現，每一個節點是在同一深度它之前，或已移近根，所以樹的高度並沒有增加。）

現在考慮一個例子，我們再次刪除節點3，但我們發現它的後繼節點4已經在右側子樹的頂部;這意味着我們可以通過後繼4立即更換節點3和左子樹附加到它，而不必首先移動節點4到右子樹的頂部：

 8         8 
    /\        /\ 
    3 ...       4 ... 
/\        /\ 
    2 4    4    2 6 
/ \    \   //\ 
1  6    6   1 5 7 
    /\   /\   
     5 7   5 7

來源

2017-08-12 22:47:15 m69

有兩種情況，此代碼試圖解釋。第一種情況是你刪除一個節點X，其繼任者Y是其直接右孩子：

在這種情況下，我們最終要爲Y來代替X，因此該方法可以只返回Y和說「這裏是現在取代X的節點。「

在另一方面，假設X的繼任者Y是在其右子樹的子樹：

X 
\ 
    A 
/\ 
Y C 
\ 
    B

在這種情況下，我們不能盲目地，其中Y代替X，因爲這樣做會失去節點A和其中所有的樹C.所以才說：「哎樹 - 去與節點Y代替節點X，」我們重新排列樹中的節點，使它們看起來就像這樣：

X 
\ 
    Y 
    \ 
    A 
/\ 
    B C

現在，當我們用Y替換X時，我們並沒有丟失樹中的任何其他節點。

順便提一句，這裏的形狀是通過交換X和Y，然後通過使Y的前父母將Y的前右子樹作爲其左子元素來刪除X（它在Y中的位置）來形成的。通過這些線追蹤，看看你是否能看到這是如何工作的。

來源

2017-08-12 23:02:19 templatetypedef

這段代碼爲什麼需要從BST中刪除？

回答

相關問題