Research Space for Linear Algebra & Discrete Mathematics
你可以把圖畫出來想, 欲使得一個高度為 4 的 full m-ary tree 具有最少(或最多)的 node 數, 那樹應該要長成甚麼樣子呢?欲使一個 full m-ary tree 的高度為 4, 至少需含有 4 個 internal node, 所以 i≧4=> 80/(m-1)≧4=> m≦21另外, 具有最多internal node的情形則是發生在樹長滿的時候, 此時 i 具最大值 m^0+m^1+m^2+m^3 = (m^4-1)/(m-1)i.e., 80/(m-1)≦(m^4-1)/(m-1)=> 81≦m^4=> m≧3上面是用 internal node 的 bound 來推, 解答觀察的是 leaf 的個數, 意思是一樣的
張貼留言
1 則留言:
你可以把圖畫出來想, 欲使得一個高度為 4 的 full m-ary tree 具有最少(或最多)的 node 數, 那樹應該要長成甚麼樣子呢?
欲使一個 full m-ary tree 的高度為 4,
至少需含有 4 個 internal node, 所以 i≧4
=> 80/(m-1)≧4
=> m≦21
另外, 具有最多internal node的情形則是發生在樹長滿的時候, 此時 i 具最大值 m^0+m^1+m^2+m^3 = (m^4-1)/(m-1)
i.e., 80/(m-1)≦(m^4-1)/(m-1)
=> 81≦m^4
=> m≧3
上面是用 internal node 的 bound 來推,
解答觀察的是 leaf 的個數, 意思是一樣的
張貼留言