作者haniwang (hani)
看板Grad-ProbAsk
标题[理工] 107 中山资结
时间Sun Jan 27 20:56:29 2019
第1小题
n-key表示degree是n-1
题目又说minimum degree是t
如果要求upper bound of tree height的话
要把tree的点数变成最多
每一个node的degree最多可以到2t-1
然後後面就不太知道怎麽继续推了
想请问大家有没有什麽想法可以证明这题
https://i.imgur.com/ivwR0uD.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.74.212.246
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548593792.A.3D3.html
1F：→ new1100726: 我会当它这题是Cormen的B-tree 11/09 21:23
2F：→ new1100726: 假设除了root node以外的node皆为degree t 11/09 21:24
3F：→ new1100726: 高度0开始，key数=1+2(t-1)(1+t+t^2+...+t^(h-1)) 11/09 21:35
4F：→ new1100726: key数=1+2(t^h-1)<=n，移项得h<=log_t ((n+1)/2) 11/09 21:37