Re: [課業] 資料結構 紅黑樹

作者: malowda (malowda)   2015-04-12 19:42:12
※ 引述《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
我以234樹來說
15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7,10 13 16 18 23
刪10
15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7 13 16 18 23
刪18
15
: / \
: 6,12 17
: / | \ / |
: 3 7 13 16 20,23
刪3
15
: / \
: 12 17
: / \ / \
: 6,7 13 16 20,23
刪16
15
: / \
: 12 20
: / \ / \
: 6,7 13 17 23
刪13
15
: / \
: 7 20
: / \ / \
: 6 12 17 23
刪12
: 15 20
: / | \
: 6,7 17 23
刪17
7,20
: / | \
: 6 15 23
再來就以小的值做為父親節點轉紅黑樹
7
: / \
: 6 20
: / \
: 15 23
就得到大大你PO的解答
以上個人的想法如有錯請其他大大指教
作者: malowda (malowda)   2015-04-12 19:44:00
不太會用顏色所以沒表現出7和20之間是紅色的
作者: lei70200 (Lei)   2015-04-12 19:56:00
謝謝!!! 這樣看起來清楚多了@@!!!
作者: kafka0829 (卡夫卡)   2015-04-12 20:04:00
我234樹刪16那邊和你不太一樣耶.我root會變(12,15,20)
作者: malowda (malowda)   2015-04-12 20:06:00
刪16後原本16的右兄弟還有2個值也就要把17向下移,20向上移,還達不到要降階的條件
作者: kafka0829 (卡夫卡)   2015-04-12 20:09:00
可我看書上步驟~除root外,遇到2node要先轉成3或4node
作者: malowda (malowda)   2015-04-12 20:11:00
沒錯阿你要先把20移上去和17成為17,20這樣就是書上說的再向17,20借17向下移
作者: kafka0829 (卡夫卡)   2015-04-12 20:28:00
疑?所以他不是指搜尋的路上有遇到2node要先處理?而是找到要刪除的元素再判斷?
作者: lei70200 (Lei)   2015-04-12 20:32:00
搜尋的路上有遇到就要先處理沒錯兩位大大都沒錯,只是刪16跟刪13的圖錯了
作者: APE36 (PT鄉民)   2015-04-12 20:46:00
k大的比較沒問題,那是王老師的版本...
作者: malowda (malowda)   2015-04-12 21:14:00
B樹是要刪除的節點到樹根沒有辦法借(都只有1個KEY)才會向下降一階,這題還有一個節點有2個KEY怎麼會就降階
作者: kafka0829 (卡夫卡)   2015-04-12 21:25:00
不知道是否為top-down 2-3-4樹和n-way樹差別嗎?topdown作法可避免backward restructuring path
作者: malowda (malowda)   2015-04-13 11:08:00
k大你有看王老師的資料結構11-57(2014)delete有分三種情況,(1)sibling為2個node(分支為2)才和兄弟合併,(2)(3)都是兄弟有3或以上的node會先借1個來,所以我的刪16和13沒錯,你的2node是指節點內的2個值吧
作者: kafka0829 (卡夫卡)   2015-04-13 12:14:00
是使用第(1)個情況沒錯呀~同你的圖要刪16的2-3-4樹17為2node他的兄弟12也為2node所以合併變成(12,15,17)之後作刪除16動作,root就會變成(12,15,20)過程是這樣:http://i.imgur.com/VA60fs8.jpg不知道步驟是否有錯~ 但參考步驟紅黑樹轉回的2-3-4樹應該是會長這樣~ 有錯再請高手補充...
作者: malowda (malowda)   2015-04-13 14:55:00
錯了,你刪16要先看他的兄弟,不是先看父節點(17)(1)的情況是p為樹葉,這題帶(1)的話p指的是17那個它不是樹葉
作者: kafka0829 (卡夫卡)   2015-04-13 15:08:00
這邊的(1)是你回文的情況(1)=書上的(3)-①然後是依序往下處理q=17 p=parent=15所以使用3-1的casedownward pass,p與q是會移動的,當遇到2node先處理因為書上有些模糊,我有特地google找一些教材參考這張圖說明的滿清楚的:http://i.imgur.com/AYsjXfP
作者: malowda (malowda)   2015-04-13 15:21:00
又不是要刪17你q指向17對嗎?第1個條件p有2個node則p為
作者: kafka0829 (卡夫卡)   2015-04-13 15:21:00
圖中的第三點剛好就是此種情況q先指17確認不是2node才往下啊
作者: malowda (malowda)   2015-04-13 15:22:00
root你覺得用你做的方式這個條件合嗎?
作者: kafka0829 (卡夫卡)   2015-04-13 15:24:00
他不是root一開始q為15為2node->root情況排除 往下17為2node處理看那張投影片,我的理解是這樣啦~
作者: malowda (malowda)   2015-04-13 15:30:00
這個是剛好3層,如果是4層你不就要從第2層開始向下合併?
作者: kafka0829 (卡夫卡)   2015-04-13 15:30:00
投影片2的意思就表示遇到2node要先處理,而不是直接就是指到欲刪除的元素應該不會有你說的情況應該沒有第二層2node第三層也2node的case吧所以會到第三層,然後處理情況又和本題一樣了
作者: lei70200 (Lei)   2015-04-13 15:58:00
k大講得很對呀~先遇到2node先處理,全部處理完後再刪除之後就停止做動作這樣才符合Forward deletion,層層往下處理的意義
作者: kafka0829 (卡夫卡)   2015-04-13 16:04:00
我上面講得有點跳:我的意思是指第二層和第三層若同為2node則因為第二層已和root合併,所以原來第三層會變成就會變成4個兄弟所以不會出現bug問題

Links booklink

Contact Us: admin [ a t ] ucptt.com