推 polomoss:交大某年好像要導公式 02/26 16:52
→ polomoss:不過我都是用F(h+2)-1去推 02/26 16:52
推 rockmanray:就(2n,n)/n+1就好了 01/27 22:10
※ 引述《zkdzvy22 (逍遙山水)》之銘言：
※ 引述《gpu (GraphicProcessUnit)》之銘言：
: http://www.lib.ntu.edu.tw/exam/graduate/94/452.pdf
: 第11題
: Suppose a tree with only one node is defind to be with height 1.
: Let x be the maxium height of an AVL tree with 400 nodes.
: Then, x mod 5 = ?
: (A) 0 (B) 1 (C) 2 (D) 3 (E) 4
: Ans : C
AVL tree有個遞迴式
f(n)=f(n-1)+f(n-2)+1
表示高度為n的話至少要幾個點
所以
f(n) 1 2 4 7 12 20 33 54 88 143 232 376
n 1 2 3 4 5 6 7 8 9 10 11 12
高度13就至少要超過600個點了
所以高度是12
遞迴式自己畫畫看就導得出來了優
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.204.115