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