二叉搜索樹刪除操作

Question

我有一本書，以非常糟糕的方式解釋了整個二叉搜索樹，至今我已經能夠關閉研究我的書，並得到二叉搜索樹的想法，但我找到解釋對於二叉搜索樹的操作Delete

我明白了兩個第一最簡單的操作

• 刪除葉（無子女的節點）：刪除葉是容易的，因爲 我們可以簡單地卸離那個樹。
• 刪除一個孩子的節點：刪除節點並將其替換爲 其子節點。

但是，有兩個孩子的人真的很難理解，我已經閱讀過wiki和其他網站來嘗試找到解決方案，但我發現解釋有點加密。

我希望有人在這裏能給我更多的細節或以另一種方式向我解釋它？

Answer 1

當節點有兩個孩子，你必須：

1. 查找最小。
2. 將要刪除的節點的密鑰替換爲最小元素。

看看這張圖： 我們要刪除元素4

• 4有2個孩子。

• 找到最小右子樹。

• 找到5個。

• 所以，4被替換爲5，並且4被刪除。

希望這就是你要找的！

Answer 2

如果您瞭解前兩條規則，那麼刪除帶有兩個孩子的節點並不難理解。

想到它的一個非常簡單的方法是，轉到要刪除節點的有序後繼者（或前驅者）。然後再應用前兩條規則和之前的規則。

編程時，具有完全功能的後繼（前驅）函數使編碼刪除變得更加簡單。

對於這種樹：

刪除8：

• 轉到9（7）

• 替換9與10

• 替換8與9（7）

刪除12：

• 轉到14（10）

• （替換9與10）

• 替換12與14（10）

Answer 3

我們可以簡單說一下：

要刪除一個二叉樹中的2個子節點的節點N（如前面提到的那樣），要麼將這個N替換爲左子樹的最大節點，要麼替換爲右子樹的最小節點