[理工] 資結 B-tree of order m 之 Delete

看板Grad-ProbAsk作者 (jojo)時間7年前 (2018/10/29 15:03), 7年前編輯推噓1(1推 0噓 7→)
留言8則, 2人參與, 7年前最新討論串1/1
https://i.imgur.com/NjEGlfV.jpg
如圖所示，當key數變多的時候，要去刪除某值，請問左右子樹要怎麼判斷？ 若刪除20，採左子樹最大是用這個區間去取代20嗎？ 若刪除10，採右子樹最小是找1去取代嗎？如果說，也就是說最左邊分支變成了右子樹@@？ PS.兩個問題獨立，沒有關連 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.215.130.217 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1540796610.A.AA8.html
推
10/29 15:16, 7年前 , 1F
刪除20，採左子樹最大：用14補
10/29 15:16, 1F
→
10/29 15:16, 7年前 , 2F
刪除10，採右子樹最小：用12補
10/29 15:16, 2F
→
10/29 15:19, 7年前 , 3F
如果兩題是獨立的題目就這樣補
10/29 15:19, 3F
→
10/29 15:19, 7年前 , 4F
不過如果是先刪20，再刪10的話，因為原(12,14)那格變成空
10/29 15:19, 4F
→
10/29 15:19, 7年前 , 5F
，就得再調整
10/29 15:19, 5F
→
10/29 15:29, 7年前 , 6F
不好意思我修改一下，兩題是獨立的@@
10/29 15:29, 6F
※ 編輯: jojoboy0115 (49.215.130.217), 10/29/2018 15:30:06
→
10/29 15:32, 7年前 , 7F
所以他其實是有區間的，10要從右子樹找最小，要大於1
10/29 15:32, 7F
→
10/29 15:32, 7年前 , 8F
0的最小
10/29 15:32, 8F
‣ 更多 jojoboy0115 的文章
文章代碼(AID): #1Rrh32ge (Grad-ProbAsk)