作者skyevolution (小總)
看板Grad-ProbAsk
標題Re: [理工] [資結]2-3 Tree的老問題!!!
時間Fri Jan 28 20:42:40 2011
抱歉昨晚算錯了
修正第一題錯誤
第二題我改成詳細版（刪除後插入不一定會一樣，下面幾篇有人給例子）
※ 引述《st84514 (綜合水果武士)》之銘言：
: 有一2-3 tree如下:
: 19.35
: / | \
: 11.15 25 42
: / | \ / \ / \
: 7.8 13 18 24 27.30 39 46
: 想問delete15的結果!
: 我的步驟是(1)delete15
: (2)取13往上拉
: (3)8.11作rotation
: 結果:
: 19.35
: / | \
: 8.13 25 42
: / | \ / \ / \
: 7 11 18 24 27.30 39 46
: 是否正確?
step1.刪除non-leaf是把該node的左子樹最大值(13)或右子樹最小值(18)拉去補
step2.就是leaf underflow的處理
所以會有兩個答案
ans1(用13補)
19.35
/ | \
11.13 25 42 ->(rotation) 8.13 (其它位置沒變)
/ | \ / \ / \ / | \
7.8 18 24 27.30 39 46 7 11 18
ans2(用18補)
19.35
/ | \
11.18 25 42 ->(combine) 11 （其它位置沒變）
/ | \ / \ / \ / \
7.8 13 24 27.30 39 46 7.8 13.18
: 又有一2-3 tree如下:
: 19.35
: / | \
: 8.13 27 42
: / | \ / \ / \
: 7 11 18 25 30 39 46
: 想問delete25的結果!
: 我的步驟是(1)delete25
: (2)27下拉與30 combine
: (3)這步驟我有點疑惑我是用35跟42 combine!
: 因為我覺得若將13.19作rotation左子樹會錯誤,11.18的部分
: 結果:
: 19
: / \
: 8.13 35.42
: / | \ / | \
: 7 11 18 27.30 39 46
: 想請問是否正確!有請高手解答!謝謝!
用13.19 combine沒問題
step1.(combine) step2.(rotation)
19.35 13.35
/ | \ / | \
8.13 42 8 19 42
/ | \ | / \ / \ / \ / \
7 11 18 27.30 39 46 7 11 18 27.30 39 46
和AVL TREE一樣，父點改變會使下面的LINK有些調動
所以在2.rotation後，在依據正確的去聯接子點
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.203.20
推 st84514:那第二題的第三步應該roration還是combine?我覺得不能 01/28 21:34
→ st84514:combine是因為11.18會無對應的父點,所以可以照你這樣做然 01/28 21:35
→ st84514:後把18接到19那喔? 01/28 21:35
→ st84514:說錯了,我是說我覺得不能roration 01/28 21:38
→ st84514:我發現你畫的第一題11.13好像錯了,第二題若插入25驗算也跟 01/28 22:36
→ st84514:原來不一樣 01/28 22:36
※ 編輯: skyevolution 來自: 111.254.203.20 (01/29 04:31)