二進制搜索樹 - 節點刪除

Question

我想了解爲什麼當刪除一個BST樹中的節點，並且必須保持孩子和堅持BST結構時，您必須採取該節點的正確的孩子（更高的價值，然後節點被刪除），如果這個正確的孩子有一個孩子離開了那個孩子。否則就是被刪除的節點右鍵。

爲什麼不把剛剛刪除的節點留給孩子，如果有的話。它仍然正確地工作？

或者我錯過了什麼。

我在閱讀this文章。

Answer 1

你簡直太簡單了。

用於替換已刪除節點的節點必須大於已刪除節點左側的所有節點，並且小於右側的所有節點。所以它必須是左子樹的最右邊的後裔或右子樹的最左邊的後裔;除非其中一個或另一個子樹完全不存在，否則我們可以完全刪除一層樹，只需將刪除的節點替換爲存在的子節點即可。

當兩棵樹都存在時，文章中列出的規則將始終爲您提供正確的子樹的最左後裔。如果你願意，你確實可以派生出一個替代規則集來代替最左邊的子樹的最右邊的後代。

它不會「正常工作」，只是始終使用左側的孩子。事實上，如果右邊有一個孩子，而左邊的孩子本身有兩個孩子，那麼在沒有重建樹的情況下甚至無法完成。

Answer 2

對於您描述的特例，您應該是正確的。但是對於更一般的情況，您可以在比被刪除的節點更深的層次上擁有更多的層次，您需要用一個節點替換該節點，該節點的權重小於一切，而且大於一切。因此，作爲一個例子：

2 
/\ 
1 6 
    /\ 
    4 7 
    \ 
    5 

比方說，你想移動節點6，現在按照你的指示，我們將與左子​​替換它，節點4.現在我們做什麼與節點5？我們可以使它成爲節點7的左邊子節點（或者節點7的最左端子節點，如果它存在的話），但是爲什麼當你知道這個時候你會做所有這些重新洗牌刪除一個葉子是微不足道的而你只是想要替換節點與另一個節點保持左側的每個節點越少，右側的每個節點越多。