卸下從BST左和右子樹與重複

Question

的DSA book一個節點描述了這種情況下，從二分搜索樹中的節點的刪除：

「4.以除去值既有在左和右子樹這種情況下，我們 提升左子樹中的最大值。「

比方說，我們有以下幾點（我想使它看起來像一棵樹）：

 7 
    6  8 
5 6  8 

如果我們去掉根（7），它說我們應該把6到它的位置。現在，它看起來像（它只是不正確的感覺）：

 6 
    6  8 
5   8 

現在是6 6.左節點，但它不應該，右（左值應該更小）？所以，我想我的問題是：可以有這種情況嗎？如果這種情況是可以接受的，那有沒有一個名字？或者我們應該選擇其他節點來替代已刪除的節點？

Answer 1

您是否假設所有「相等」的值都在正確的子樹中？如果是這樣，您可以隨時替換其右側子樹中具有最小值的節點。如果他們可以在任何一方，那麼你就沒有問題。