一道证明题

证明：

有n个内部结点的AVL树满足 ：

h<1.4404lg(n+2)-0.328

AVL树性质：

AVL树是一种二叉搜索树，每一个节点的左右子树高度之差最多为1（空树定义为0）。

假设高度为h的AVL树内部节点的最小数量为f(h),则

<1> 当高度为1时f(1)=1;

<2> 当高度为2时f(2)=2;

<3>当高度为3时f(3)=4;

则高度为h的的数,由AVL树的性质,至少由一个高度为h-1,以及一个高度为h-2的子树构成.则当两个子树

的内部节点最少时,h树的内部节点最少,由此推得:

f(h)=f(h-1)+f(h-2)+1;

则内部节点的最小数量为一个斐波那契额数列.

对比斐波那契数列F(n)与上面公式的数值:

f(h)斐波那契n=1 11n=221n=342n=473n=5125n=6208

猜测 f(n) = F(n+2)-1; n>1;

使用数学归纳法进行证明:

f(1)=1=F(3)-1

f(2)=2=F(4)-1

f(3)=4=F(5)-1

则假设存在 f(n-1)=F(n+1)-1,f(n-2)=F(n)-1 [n>2]

则 f(n)=f(n-1)+f(n-2)+1=F(n+1)-1+F(n)-1+1=F(n+2)-1

得证.

斐波那契数列的求值方法可以通过百度百科中所讲的待定系数法等方法进行计算.

则 ,内部节点的个数n,高度h符合以下关系:

n>F(h+2)-1

然后经过推理[数学符合太难输入了,还是给链接吧...],得:

h<1.4404lg(n+2)-0.328