刪除BST中的多個節點會更改生成的樹？

Question

如果我需要刪除BST中的多個節點，生成的樹會不同地改變刪除順序？正常的左右順序將被保留，但我不確定樹結構。

這是一個「phisolophical」問題，我需要一個dimostration或反例。

Answer 1

爲了證明刪除的順序對最終樹沒有影響，證明任何兩個刪除操作都是通行的（也就是說，如果它們的順序相反，它們具有相同的效果）是必要且足夠的。

刪除節點的效果僅限於該節點及其所在的子樹。所以如果兩個節點是分開的（即兩個節點都不在另一個之下），那麼它們的刪除就會通過。因此，唯一感興趣的案例在另一個子樹中有一個節點。

不失一般性，假設我們使用的規則是，當我們刪除一個有兩個孩子的節點時，我們用它的後繼替換它。如果B在A的左子樹中，那麼刪除就會通過，因爲A的刪除對A的左子樹沒有影響，並且B的刪除沒有效果 A的左子樹。所以唯一的情況是B在A的右子樹中。

當A被刪除時，對A的右子樹的效果與A的後繼者已被刪除的效果相同。假設B是而不是 A的繼任者;我們將調用A的繼承者C.刪除A包括從右子樹中刪除C和用C（通勤）替換A，所以如果B和C的刪除通過，那麼刪除A和B通勤。通過歸納，如果任何一對刪除不通勤，那麼刪除A和B（其中B是A的後繼者）不通勤。

但是刪除A及其繼承人通過檢查通勤。證明完畢

Answer 2

Deleting 1 and 2 in different order results in two different trees反例： 刪除1和2的順序導致不同的BST。 因爲當你首先要刪除2時，你必須在它的 右子樹中找到下一個元素，即3，並用2替換，但是當你首先刪除1然後你想刪除2時，現在它已經有了只有一個孩子，只是它的孩子取代它，即4。 因此導致兩棵不同的樹。