[課業] 資料結構 紅黑樹

[lei70200 (客家一哥)]

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

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

一顆紅黑樹如下
                         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)我有另外去用紅黑樹的正式規則做一次，但是做出來的結果與解答相去甚遠，

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



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

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




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.237.205
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1428832246.A.372.html
→ emstarbucks: 我都記這些= = 紅兄 黑兄二黑姪 黑兄紅姪雙黑處理
→ malowda: 可以先把這棵的234樹畫出來嗎
→ lei70200: 我也是用這推的，可是推出來的樹長的完全不一樣 囧
→ lei70200: 馬上來新增一下2-3-4樹
※ 編輯: lei70200 (114.27.237.205), 04/12/2015 18:49:52
→ lei70200: 已補上
→ malowda: 你的7和10是不是畫錯了你不是以小的值當父親NODE嗎
推 kafka0829: 你可以將書上每步的紅黑樹轉回2-3-4樹再比對自己作刪除
→ kafka0829: 時的2-3-4樹是否一樣
→ kafka0829: 我當時是卡在刪除16，因為17是2node要先對他處理才能刪
m大請問是哪一個圖呢@@? 我剛重新檢查了下紅黑樹確定是對的
k大我是卡在刪除3後的6跟7...因為刪除3完後的2-3-4樹長這樣

                         15
                     /       \
                    12       17
                  /    \   /    \
                6,7    13 16   20,23

6跟7沒有前循可以知道誰先誰後，所以紅黑樹有  7    6     兩種情況
                                           /      \
                                          6        7
這邊要全寫出來?
※ 編輯: lei70200 (114.27.237.205), 04/12/2015 19:49:19
→ malowda: 我是習慣用234樹來做直接用紅黑樹來做紅黑要變來變去會搞
→ malowda: 亂
我好像搞懂了...以這題來說多種情況就先不理他，刪到後面只會剩下一種情況，

所以題目特別設計過的話，樹的結果會是唯一

然後紅黑樹的刪除就是以先刪2-3-4樹再轉成紅黑樹，所以可以拋棄那難背的規則了QAQ

謝謝以上留言的大大幫助，小的感激不盡!!!

※ 編輯: lei70200 (114.27.237.205), 04/12/2015 20:11:20
推 kafka0829: 3node(6,7)本來就兩種畫法，看你要哪邊先寫都可以
→ malowda: 要畫那一種全部要統一不是一個節點以小的另一個以大的
→ malowda: 否則會有很多種
→ kafka0829: 推樓上要統一~看是哪邊要先畫~
→ lei70200: 嗯嗯 了解!