作者wagaru (wagaru)
看板Grad-ProbAsk
標題[問題] 2-3 tree
時間Thu Mar 19 00:34:27 2009
考試都考到現在了，還問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 應該不符定義才對…
請問上面的步驟是哪裡錯了呢？
謝謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.91.160
推 SPYKER:同學你確定你是113的嗎? 03/19 00:40
推 elfkiller:上面沒錯 20會跟著21接到另外一邊 03/19 00:41
推 ixjnpns:怎麼會有人不回答還反嗆呢 = =? 03/19 00:45
推 SPYKER:定義沒錯阿 2-3樹 2<=degree<=3 03/19 00:46
推 SPYKER:sorry! 應該說是父節點破產 要先去鍵結 所以20應該接在 03/19 00:57
推 erictku:樓上 1父點怎麼接3子點..要2父點才能接3子點好嗎 = = 03/19 00:57
→ SPYKER:(20,21) 03/19 00:57
→ erictku:給原po:你用BST的概念去想 20比19大 所以也會被移到右邊 03/19 00:58
→ SPYKER:誤 (21,22) 下接20 22 30 03/19 00:59