作者chenbojyh (阿志)
看板Grad-ProbAsk
標題Re: [理工] [資結]2-3 tree的刪除問題
時間Sun Jan 3 22:26:33 2010
※ 引述《chenbojyh (阿志)》之銘言：
※ 引述《GraffitiK (GraffitiK)》之銘言：
: 75
: / \
: 35 85
: / \ / \
: 15 50 80 96
: 請問像是以上這種2-3 tree，要刪掉的node位置分別為75和35時，該怎麼操作呢？
: 謝謝！
刪75
80 35,80
/ \ / │ \
35 85 -> 15 50 85,96
/ \ \
15 50 96
刪35
35,80 80
/ │ \ -> / \
15 50 85,96 15,50 85,96
應該是這個樣子.....
1F：推 polomoss:找左子最大~~或右子最小~~其他調整一樣 01/03 13:46
2F：→ kkman0120:這樣對嘛？看起來怪怪的 01/03 19:34
刪35應該是這樣才對
35,80 50,85
/ │ \ -> / │ \
15 50 85,96 15 80 96
sorry 之前寫錯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.129.123
3F：推 GraffitiK:? 可是刪35的部分我寫的和之前的一樣欸, 欲刪的點若在非 01/03 23:47
4F：→ GraffitiK:葉節點的話, 先和左子樹最大或右子樹最小作交換, 再用刪 01/03 23:47
5F：→ GraffitiK:leaf的方式刪. 假設35和50交換之後, 15再和50 combine, 01/03 23:47
6F：→ GraffitiK:結果就變成像之前的那個答案.. 還是因為一定要先用 01/03 23:47
7F：→ GraffitiK:rotation的方式?? 01/03 23:48
8F：推 ck1115:可是如果再新增回去怎麼怪怪的 我錯了嗎? 01/04 00:02
9F：→ chenbojyh:我也在想 刪35好像怪怪的 01/04 09:43
10F：推 kkman0120:我覺得一開始刪75好像也怪怪的@@ 01/04 21:39