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

看板Grad-ProbAsk作者 (kk)時間16年前 (2009/11/11 16:11), 編輯推噓1(106)
留言7則, 3人參與, 最新討論串1/1
請問一下 一個2-3tree假如如下: 40 / \ 27,29 45 / | \ / \ 10 28 35 44 50 如果要刪除29這個資料的話 該如何操作阿? 找了範例找好久都找不到有討論這種刪除2node的範例... 幾乎都是討論刪除root or leaf的資料... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.166.242.233 ※ 編輯: kkman0120 來自: 118.166.242.233 (11/11 16:16)

11/11 17:24, , 1F
將29的左子樹最大(28) 或 29的右子樹最小(35)交換
11/11 17:24, 1F

11/11 17:24, , 2F
此時29即為leaf 用刪除leaf的規則去做就好
11/11 17:24, 2F

11/11 17:25, , 3F
如果還不是leaf 則重複第一行的步驟
11/11 17:25, 3F

11/11 17:27, , 4F
阿 忽略我上一行 他一定是leaf
11/11 17:27, 4F

11/11 18:42, , 5F
所以不管幾個資料的node依然是去找他的子樹中最小or最大
11/11 18:42, 5F

11/11 18:42, , 6F
的ley去替代他囉...
11/11 18:42, 6F

11/12 18:42, , 7F
不能rotation就combination
11/12 18:42, 7F
文章代碼(AID): #1A-d6YIq (Grad-ProbAsk)