Re: [理工] [資結]2-3 Tree的老問題!!!已刪文
※ 引述《wolfswolfs (wolf)》之銘言:
: 應該是說,delete 15的話,只有13.15.18這顆子樹會變動,不能動用到7.8.11這邊的資料
: 所以,
: : 有一2-3 tree如下:
: : 19.35
: : / | \
: : 11.15 25 42
: : / | \ / \ / \
: : 7.8 13 18 24 27.30 39 46
non-leaf
找左子樹最右邊上去
或右子樹最左邊上去
如果是拿左子樹的13上去
那underflow的就是leaf
接下來先考慮rotation
8,13
/ | \
7 11 18
如果拿右子樹的18上去
那underflow的也是leaf
接下來先考慮rotation
旁邊13只有自己一人不夠
才能作combination
11
/ \
7,8 13,18
借文章來討論一下
推文中說到insert回去會一樣的想法
insert 1,3,4,2
3
/ \
1,2 4
delete 4,insert 4 ?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.124.176
推
01/29 12:58, , 1F
01/29 12:58, 1F
推
01/29 21:30, , 2F
01/29 21:30, 2F
推
01/29 21:35, , 3F
01/29 21:35, 3F
→
01/30 10:44, , 4F
01/30 10:44, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 3 之 4 篇):