資料結構 紅黑樹 - 考試

各位好，由於上完王老師函授的資結，對於上課所提及到的紅黑樹著墨甚少，

所以心中還是有不少疑問，首先附上範例圖：

一顆紅黑樹如下
15
/ \
6 17
/ \ / \
3 12 16 20
/ \ / \
10 13 18 23
/
7


補上其最初2-3-4樹如下

15
/ \
6,12 17,20
/ | \ / | \
3 7,10 13 16 18 23


其中節點7、12、20 為紅色節點，請一步步刪除圖中節點，

依序為10、18、3、16、13、12、17

最後的解答為

7
/ \
6 20
/ \
15 23

以下提出我的疑問：

(1)老師有說過可以利用2-3-4樹推出紅黑樹(但是只做了插入就下課了...)

那麼，刪除紅黑樹的步驟是先將2-3-4樹刪除完後再轉換成紅黑樹嗎?

(2)承(1)如果是，由於2-3-4樹的特性在刪除之前可能會有值的位置變動，

這樣的變動是不是會讓紅黑樹為不唯一？如果不是，那麼每個步驟該怎麼做？(

比如說旋轉的時機等等...)資質駑鈍，看不出來兩棵樹在刪除的時候
有甚麼關聯OTL

(3)我有另外去用紅黑樹的正式規則做一次，但是做出來的結果與解答相去甚遠，

再這樣的差異下，考試的時候應該要以哪個為主？(感覺很吃運氣....)



後面的紅黑樹整個就大爆炸阿...出了感覺就很不妙....

希望有精通此樹的大大們可以為小的開釋...




--