方法來刪除一個二叉樹節點

Question

我下面的一本書，介紹瞭如何從一個二叉搜索樹刪除節點，基本上如果我們有這樣的樹：

 10 
    /\ 
    4 100 
    /\ 
    1 8 
    /\ 
    6 9 
     \ 
     7 

，我們要刪除節點4，書上說我應該：

1. 查找其右子樹4的繼任者（這是6）
2. 交易所4和6
3. 從右子樹刪除6
4. 附上4左子樹（這僅僅是1在這種情況下）到新節點6

因此我們得到

 10 
    /\ 
    6 100 
    /\ 
    1 8 
    /\ 
    7 9 

不過，我想到了另一種方式來做到這一點：

1. 找到4右子樹的最小元素（這是6）
2. 附上4的左子樹，以6（它不會有一個左子）
3. 將父母（10）附加到4的右側元素（8）。如果算法是遞歸的，我們可以只返回8

因此我們得到

 10 
    /\ 
    8 100 
    /\ 
    6 9 
/\ 
1 7 

現在，我想問：我看到我的解決方案產生（至少在這種情況下）稍微不平衡的樹。

爲什麼我應該用我的書而不是我自己的書？看來我的解決方案更容易實現（至少從我的角度來看），但我更希望別人指出我是否錯了。

Answer 1

當你的樹不平衡時，遍歷樹的時間增加，因此你失去了使用BST的一些好處。

Answer 2

這兩種方法的代碼都特別複雜。你正在採取一個子樹（1的子樹）並將它移動（可能）在樹的下方很遠，所以你的方法通常會產生一個不太平衡的樹。

通過他們的方法，7的子樹向上移動1個節點，並且沒有其他子樹移動。

可能只是因爲他們沒有考慮你的方法，或者如果他們有，他們可能會選擇他們的方法，因爲樹越平衡，查詢的性能就越差。

雖然這個討論並不是特別重要，但由於實際上很少使用基本的二叉搜索樹，所以使用了self-balancing ones（爲了保持某些特性以保持樹平衡，可以使用self-balancing ones ）。