[課業] 資料結構 紅黑樹

作者: lei70200 (Lei)   2015-04-12 17:50:43
各位好,由於上完王老師函授的資結,對於上課所提及到的紅黑樹著墨甚少,
所以心中還是有不少疑問,首先附上範例圖:
一顆紅黑樹如下
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)我有另外去用紅黑樹的正式規則做一次,但是做出來的結果與解答相去甚遠,
再這樣的差異下,考試的時候應該要以哪個為主?(感覺很吃運氣....)
後面的紅黑樹整個就大爆炸阿...出了感覺就很不妙....
希望有精通此樹的大大們可以為小的開釋...
作者: emstarbucks (花榭清風)   2015-04-12 18:42:00
我都記這些= = 紅兄 黑兄二黑姪 黑兄紅姪雙黑處理
作者: malowda (malowda)   2015-04-12 18:44:00
可以先把這棵的234樹畫出來嗎
作者: lei70200 (Lei)   2015-04-12 18:44:00
我也是用這推的,可是推出來的樹長的完全不一樣 囧馬上來新增一下2-3-4樹已補上
作者: malowda (malowda)   2015-04-12 19:17:00
你的7和10是不是畫錯了你不是以小的值當父親NODE嗎
作者: kafka0829 (卡夫卡)   2015-04-12 19:21:00
你可以將書上每步的紅黑樹轉回2-3-4樹再比對自己作刪除時的2-3-4樹是否一樣我當時是卡在刪除16,因為17是2node要先對他處理才能刪
作者: malowda (malowda)   2015-04-12 19:47:00
我是習慣用234樹來做直接用紅黑樹來做紅黑要變來變去會搞亂
作者: kafka0829 (卡夫卡)   2015-04-12 20:00:00
3node(6,7)本來就兩種畫法,看你要哪邊先寫都可以
作者: malowda (malowda)   2015-04-12 20:04:00
要畫那一種全部要統一不是一個節點以小的另一個以大的否則會有很多種
作者: kafka0829 (卡夫卡)   2015-04-12 20:05:00
推樓上要統一~看是哪邊要先畫~
作者: lei70200 (Lei)   2015-04-12 20:13:00
嗯嗯 了解!

Links booklink

Contact Us: admin [ a t ] ucptt.com