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

看板Grad-ProbAsk作者ubuntu123 (ubuntu123)時間13年前 (2011/01/18 21:25)推噓3(3推 0噓 12→)

留言15則, 4人參與討論串2/4 (看更多)

※ 引述《tomcallme (今天早上)》之銘言：這題是依序：11，12，...，19 in ascending order 建2-3tree 然後 delete node14 吧？剛剛參考了一下手邊的資料 ~ 洪逸的筆記 2-3tree的delete的確可以有兩種方法 1.從左子樹的MAX來補 2.從右子樹的MIN來補 : 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 : / \ : 空 16,18 父點keys小於1 還是不能做rotation : / | \ 故combine 並斷建結 : 11,12 15 17 19 ************************************************************** 修改過後的想法： 13 / \ 12 16,18 / \ / \ \ 11 空 15 17 19 將左子樹MAX(13)移至root 此時原先(13)的節點 key = 0 不符合2-3tree定義所以將其左兄弟(11)與其父親(12)combination 此時： 13 / \ 空 16,18 / / \ \ 11，12 15 17 19 這時候原先(12)的節點 key = 0 因為右兄弟有兩個鍵值(16，18) 所以向右兄弟借一個鍵值(rotation)就是13下、16上並且調整右子樹的子鏈結~這又是另一個故事了XD 如有錯誤請高手指證^^ : 13,16,18 root keys數目大於2 -> split : 11,12 15 17 19 : 16 : / \ : 13 18 將斷掉的接回 : / \ / \ : 11,12 15 17 19 : 應該是這樣吧剛剛講錯了 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 112.105.207.212 ※ 編輯: ubuntu123 來自: 112.105.207.212 (01/18 21:27)

推

tomcallme

01/18 21:43, , 1^F

01/18 21:43, 1^F

→

tomcallme

01/18 21:43, , 2^F

01/18 21:43, 2^F

→

ubuntu123

01/18 21:56, , 3^F

01/18 21:56, 3^F