→ new1100726: 我會當它這題是Cormen的B-tree 11/09 21:23
→ new1100726: 假設除了root node以外的node皆為degree t 11/09 21:24
→ new1100726: 高度0開始，key數=1+2(t-1)(1+t+t^2+...+t^(h-1)) 11/09 21:35
→ new1100726: key數=1+2(t^h-1)<=n，移項得h<=log_t ((n+1)/2) 11/09 21:37
第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://www.ptt.cc/bbs/Grad-ProbAsk/M.1548593792.A.3D3.html