各位好，由於上完王老師函授的資結，對於上課所提及到的紅黑樹著墨甚少，
所以心中還是有不少疑問，首先附上範例圖：
一顆紅黑樹如下
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)我有另外去用紅黑樹的正式規則做一次，但是做出來的結果與解答相去甚遠，
再這樣的差異下，考試的時候應該要以哪個為主？(感覺很吃運氣....)
後面的紅黑樹整個就大爆炸阿...出了感覺就很不妙....
希望有精通此樹的大大們可以為小的開釋...
--
All Comments