Re: [理工] [資結]2-3 Tree的 delete

[boy5548 (小YO)]

※ 引述《tomcallme (今天早上)》之銘言：
:          14
:         /  \
:       12    16,18
:      /\      /  | \
:    11  13   15 17 19
:    刪除 14
:         /      \           因為是刪除non-leaf
:       12        16,18      選擇取左子樹最大去遞補
:      /  \      /  |  \
:    11    13  15  17   19
:            13
:         /      \
:       12        16,18      子點keys數小於1 又不能做rotation
:      /  \      /  |  \     故做combination 並斷連結
:    11    空  15  17   19

-----
以上沒問題
下面應該是
            13              在此做rotation轉換，13下來，16上去
         /      \
        空       16,18
                /  |  \
    11,12     15  17   19


            16
         /      \
       13        18         完成圖
      /  \      /  \
  11,12   15  17    19


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.128.91
※ 編輯: boy5548         來自: 125.224.128.91       (01/18 21:46)
推 aoqq12:子節點 underflow由父節點 提供data
→ aoqq12:先判斷可不可以rotation 可以的話就做
→ aoqq12:父節點破產的話就合併 ..找爺爺
→ aoqq12:然後重點就來了 爺爺如果可以ratation
→ aoqq12:左子樹 跟右子樹的孫子要重新  依照旋轉後排列
→ privatewind:我認為你是對的... 0.0