作者GlassesKJ (睡觉宰予)
看板Grad-ProbAsk
标题[理工] 105 中央 资演 B tree问题
时间Sun Jan 5 11:20:25 2020
这年的中央题目提到5,4,3,2,1放入一个空的B tree里面(degree 3)
版上查到的答案是
[2,4]
/ | \
[1] [3] [5]
不过我去网路上看,看到的都是一个节点最多放两倍degree-1的key
照这样算起来光是root就可以把所有东西装满了啊?(变成[1,2,3,4,5])
不知道各位朋友能否赐教,提醒我到底哪边出问题了,如果直接告诉我步骤更感谢。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.74.226.57 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578194431.A.6A2.html
1F:推 ponwar87123: degree 3不是代表一个节点可以伸出去3个线ㄇ 01/05 11:28
2F:→ ponwar87123: 也就是key最多2个 不太可能塞到5个吧 01/05 11:28
3F:推 bochengchen: 应该是你的定义看错吧! 不如把网址放上来给大家看看 01/05 11:40
https://i.imgur.com/l4cJX8Q.png
先上一张图片,网址等等(好像有点长我看看是否缩一下)
刚刚才发现人家是minimum degree不是单纯degree,是差在这边吗
(更)一开始是看这个(我喂狗第一条):
https://bit.ly/2ZPtkOa
後来是看这个:
https://bit.ly/39DqkJi
※ 编辑: GlassesKJ (42.74.226.57 台湾), 01/05/2020 12:45:23
4F:推 bochengchen: 你的第一张图讲的是minimum degree=3,不是max=3 01/05 14:47
5F:推 bochengchen: 题目的degree=3是指max degree=3 01/05 14:51
6F:→ bochengchen: 用你查到的算法是2t-1=3,t=2 至少要1个data 01/05 14:53
7F:→ GlassesKJ: 原来是这样,所以结果才会变成一般2,3树那样啊 01/05 14:58
8F:→ GlassesKJ: 好吧我没搞懂这个degree怎麽分的,中央105也没有特别明 01/05 14:59
9F:→ GlassesKJ: 讲:3 01/05 14:59
10F:→ bochengchen: 算是习惯用法,Btree of degree k代表最多k个子树 01/05 15:25
11F:→ GlassesKJ: 了解,感谢指导 01/05 16:35