Re: [理工] [資結]2-3 Tree的老問題!!!(修正)
抱歉昨晚算錯了
修正第一題錯誤
第二題我改成詳細版（刪除後插入不一定會一樣，下面幾篇有人給例子）
※ 引述《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
推
01/28 21:34, , 1F
01/28 21:34, 1F
→
01/28 21:35, , 2F
01/28 21:35, 2F
→
01/28 21:35, , 3F
01/28 21:35, 3F
→
01/28 21:38, , 4F
01/28 21:38, 4F
→
01/28 22:36, , 5F
01/28 22:36, 5F
→
01/28 22:36, , 6F
01/28 22:36, 6F
※ 編輯: skyevolution 來自: 111.254.203.20 (01/29 04:31)