作者jojoboy0115 (その血の运命~Jo~Jo~)
看板Grad-ProbAsk
标题[理工] 2-3 Tree以及2-3-4 Tree的Insertion
时间Sun Jan 27 14:20:03 2019
先提出疑问
1.请问2-3或者2-3-4 Overflow 是怎麽判断?
(A)在插入後，检查是否Overflow，才Split
(B)在插入前，就把所经过的 Node 都先Split(後面有例子)
有点像是红黑树若经过有两个红子点，要先 Color change
2.要往父点拉的值是怎麽选择?
(C)在插入对应的顺序後，才开始找
假设2-3-4 Tree现在有{13,14,15}，Insert(12)後，{12,13,14,15}overflow，
选择{13}上去父点，{12}、{14,15}当子点
(D)在插入前，先Split，选{14}上去当父点，{12,13}、{15} 当子点
3.2-3 Tree 跟 2-3-4 Tree 的Insertion 本来就不一样吗?
直接来看题目，这题2-3 Tree是用(A)+(C)
看前三个数字 10 9 8就好
当8插入後，发现Overflow，选择第二个值 9 往上拉
https://i.imgur.com/RJYDiuW.jpg
https://i.imgur.com/Pw0JUJH.jpg
再来是这题2-3-4 Tree
106台大电机丙的资料结构
要采用(B)+(D)才有答案...
https://i.imgur.com/CHseQQu.jpg
http://i.imgur.com/70KGZUq.jpg
转自yorunohoshi大大的图片
在插入12之前，就先Split了，就是我上面的例子
可以看这篇文章下面的讨论
https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1486893104.A.3B6.html
还是...这些问题都不存在? 我哪边又想错惹@@
请各位大大开导一下...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.233.83.128
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548570005.A.531.html
1F：推 aeiou335: 3. 看维基百科 两个做法不一样吧 01/27 16:52
2F：推 Voicer: 1.2-3 A/2-3-4 B 01/27 17:38
3F：推 Voicer: 2.D 01/27 17:40
4F：→ Voicer: 234属於最後再做插入，23属於先插入 01/27 17:41
5F：→ alen0303: 采(A)+(C)法可以选出BD为答案 01/27 19:11
6F：→ alen0303: 答案有确定是AB还是BD吗? 01/27 19:11
7F：推 alen0303: 啊 题目要求用top-down insert 那应该是AB没错了 01/27 19:22
答案是AB没错
8F：推 ming173899: 2-3-4tree 01/27 20:28
9F：→ ming173899: Bottom-up是先插入後在split 01/27 20:28
10F：→ ming173899: Top-down好像是搜索路径上等於四就会先split 01/27 20:28
11F：→ ming173899: 不过我也不知道2-3 tree Bottom-up和Top-down的差别 01/27 20:30
几乎都是Top-down
总结来说就是2-3 跟 2-3-4 做法不一样...
这样我知道了~感谢各位~
※ 编辑: jojoboy0115 (36.233.83.128), 01/27/2019 22:37:29
12F：推 ekids1234: 真的有先插在split作法吗QQ 这样会不懂四个谁该上去.. 01/27 22:47
13F：→ jojoboy0115: 因为2-3 是用先插入再Split，所以我一开始做2-3-4也 01/27 23:06
14F：→ jojoboy0115: 是用同样的方法，却没有答案，爬文後才知道有其他做 01/27 23:06
15F：→ jojoboy0115: 法@@ 01/27 23:06
16F：推 eatagary: 台大 2-3树 那题 题目有问题，用top-down会画不出来， 01/28 00:17
17F：→ eatagary: 市面解答都是用 bottom up解法，解这题。 01/28 00:17
18F：推 ko330: 2 3 tree是不是没有top-down阿都找不到资料.. 01/28 17:38