Re: [理工] [資結]2-3 tree的刪除問題

[chenbojyh (阿志)]

※ 引述《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

應該是這個樣子.....
推 polomoss:找左子最大~~或右子最小~~其他調整一樣
→ kkman0120:這樣對嘛？看起來怪怪的
刪35應該是這樣才對

    35,80                     50,85
  /  │   \        ->       /   │  \
15   50  85,96             15   80  96

sorry 之前寫錯

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.227.129.123
推 GraffitiK:? 可是刪35的部分我寫的和之前的一樣欸, 欲刪的點若在非
→ GraffitiK:葉節點的話, 先和左子樹最大或右子樹最小作交換, 再用刪
→ GraffitiK:leaf的方式刪. 假設35和50交換之後, 15再和50 combine,
→ GraffitiK:結果就變成像之前的那個答案.. 還是因為一定要先用
→ GraffitiK:rotation的方式??
推 ck1115:可是如果再新增回去怎麼怪怪的 我錯了嗎?
→ chenbojyh:我也在想  刪35好像怪怪的
推 kkman0120:我覺得一開始刪75好像也怪怪的@@