作者ubuntu123 (ubuntu123)
看板Grad-ProbAsk
標題Re: [理工] [資結]2-3 Tree的 delete
時間Tue Jan 18 21:25:38 2011
※ 引述《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
→ tomcallme:是第一次做combination的時候嗎? 01/18 21:43
→ ubuntu123:我想法幾乎跟你一樣 唯獨在*號框起來那邊有點出入 01/18 21:56
→ ubuntu123:至於斷鍵時機點 我的想法就是因為出現underflow 01/18 21:58
推 tomcallme:我的想法:因為出現underflow 所以不能rotate 01/18 21:59
→ tomcallme:所以只能combine combine完斷建 等一切整好再接 01/18 21:59
→ ubuntu123:所以必須作rotation處理 下一個step若不斷鍵重組 01/18 22:00
→ tomcallme:我手邊沒資料XD 不過斷建應該是combine的配套吧~? 01/18 22:00
→ ubuntu123:就會違背search tree的定義 01/18 22:00
→ tomcallme:更改一下 因為rotate會出現underflow 所以不能rotate 01/18 22:01
→ tomcallme:阿~~明天去查書 = = 01/18 22:01
→ MiiQ:我想的跟T大一樣 01/18 22:04
推 tomcallme:我一直打錯 是overflow 不是 underflow 01/18 22:05
※ 編輯: ubuntu123 來自: 112.105.207.212 (01/18 22:29)
→ ubuntu123:修改過了 不知道有沒有比較合理一點@@? 01/18 22:30
※ 編輯: ubuntu123 來自: 112.105.207.212 (01/18 22:32)