作者SPYKER (成功客)
站內Grad-ProbAsk
標題Re: [問題] 2-3 tree
時間Thu Mar 19 01:14:05 2009
※ 引述《wagaru (wagaru)》之銘言：
: 考試都考到現在了，還問2-3tree似乎有點蠢…
: 31
: / \
: / \
: / \
: 21 47
: / \ / \
: / \ / \
: / \ / \
: (15 , 19) 24 43 50
: / | \ / \ / \ / \
: / | \ / \ / \ / \
: (10,12) 18 20 22 30 33 45 48 52
: 現在要刪除30…
: 我的算法是，因為無法rotation，所以要combination，把24拿下來
: 所以24現在是空的，進行rotation，19上去，21下來
: 那現在15這個node，會有三個child node 應該不符定義才對…
: 請問上面的步驟是哪裡錯了呢？
: 謝謝~
step 1 combination 父破產 去鍵結
31
/ \
/ \
/ \
21 47
/ \ / \
/ \ / \
/ \ / \
(15 , 19) 空 43 50
/ \ / \
/ \ / \
(10,12) 18 20 (22,24) 33 45 48 52
step 2 rotation
31
/ \
/ \
/ \
19 47
/ \ / \
/ \ / \
/ \ / \
15 21 43 50
/ \ / \
/ \ / \
(10,12) 18 20 (22,24) 33 45 48 52
step 3 連回
31
/ \
/ \
/ \
19 47
/ \ / \
/ \ / \
/ \ / \
15 21 43 50
/ \ / \ / \ / \
/ \ / \ / \ / \
(10,12) 18 20 (22,24) 33 45 48 52
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.218.131.186