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

[malowda (malowda)]

※ 引述《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的解答
       以上個人的想法如有錯請其他大大指教

















--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.141.73.131
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1428838934.A.241.html
→ malowda: 不太會用顏色所以沒表現出7和20之間是紅色的
推 lei70200: 謝謝!!! 這樣看起來清楚多了@@!!!
→ kafka0829: 我234樹刪16那邊和你不太一樣耶.我root會變(12,15,20)
→ malowda: 刪16後原本16的右兄弟還有2個值也就要把17向下移，20向上
→ malowda: 移，還達不到要降階的條件
推 kafka0829: 可我看書上步驟~除root外，遇到2node要先轉成3或4node
→ malowda: 沒錯阿你要先把20移上去和17成為17,20這樣就是書上說的再
→ malowda: 向17,20借17向下移
推 kafka0829: 疑？所以他不是指搜尋的路上有遇到2node要先處理？
→ kafka0829: 而是找到要刪除的元素再判斷？
推 lei70200: 搜尋的路上有遇到就要先處理沒錯
推 lei70200: 兩位大大都沒錯，只是刪16跟刪13的圖錯了
推 APE36: k大的比較沒問題，那是王老師的版本...
→ malowda: B樹是要刪除的節點到樹根沒有辦法借(都只有1個KEY)才會向
→ malowda: 下降一階，這題還有一個節點有2個KEY怎麼會就降階
→ kafka0829: 不知道是否為top-down 2-3-4樹和n-way樹差別嗎？
推 kafka0829: topdown作法可避免backward restructuring path
→ malowda: k大你有看王老師的資料結構11-57(2014)delete有分三種情
→ malowda: 況，(1)sibling為2個node(分支為2)才和兄弟合併，(2)(3)
→ malowda: 都是兄弟有3或以上的node會先借1個來，所以我的刪16和13
→ malowda: 沒錯，你的2node是指節點內的2個值吧
→ kafka0829: 是使用第(1)個情況沒錯呀~同你的圖要刪16的2-3-4樹
→ kafka0829: 17為2node他的兄弟12也為2node所以合併變成(12,15,17)
→ kafka0829: 之後作刪除16動作，root就會變成(12,15,20)
→ kafka0829: 過程是這樣：http://i.imgur.com/VA60fs8.jpg
→ kafka0829: 不知道步驟是否有錯~ 但參考步驟紅黑樹轉回的2-3-4樹
→ kafka0829: 應該是會長這樣~ 有錯再請高手補充...
→ malowda: 錯了，你刪16要先看他的兄弟，不是先看父節點(17)
→ malowda: (1)的情況是p為樹葉，這題帶(1)的話p指的是17那個它不是
→ malowda: 樹葉
推 kafka0829: 這邊的(1)是你回文的情況(1)=書上的(3)-①
推 kafka0829: 然後是依序往下處理q=17 p=parent=15所以使用3-1的case
→ kafka0829: downward pass，p與q是會移動的，當遇到2node先處理
→ kafka0829: 因為書上有些模糊，我有特地google找一些教材參考
→ kafka0829: 這張圖說明的滿清楚的：http://i.imgur.com/AYsjXfP
→ malowda: 又不是要刪17你q指向17對嗎？第1個條件p有2個node則p為
→ kafka0829: 圖中的第三點剛好就是此種情況
→ kafka0829: q先指17確認不是2node才往下啊
→ malowda: root你覺得用你做的方式這個條件合嗎？
→ kafka0829: 他不是root
→ kafka0829: 一開始q為15為2node->root情況排除 往下17為2node處理
→ kafka0829: 看那張投影片，我的理解是這樣啦~
→ malowda: 這個是剛好3層，如果是4層你不就要從第2層開始向下合併？
→ kafka0829: 投影片2的意思就表示遇到2node要先處理，而不是直接就
→ kafka0829: 是指到欲刪除的元素
→ kafka0829: 應該不會有你說的情況
→ kafka0829: 應該沒有第二層2node第三層也2node的case吧
→ kafka0829: 所以會到第三層，然後處理情況又和本題一樣了
推 lei70200: k大講得很對呀~先遇到2node先處理，全部處理完後再刪除
→ lei70200: 之後就停止做動作
推 lei70200: 這樣才符合Forward deletion,層層往下處理的意義
→ kafka0829: 我上面講得有點跳：我的意思是指第二層和第三層若同為
→ kafka0829: 2node則因為第二層已和root合併，所以原來第三層會變成
→ kafka0829: 就會變成4個兄弟所以不會出現bug問題