节点的满二叉树深度为log2(n+1),同节点数的平衡二插树绝对大雨等于这个数，所以是正确的吧，呵呵
温馨提示：内容为网友见解，仅供参考
第1个回答 2013-10-07
证：设N[h]表示高度为h的AVL树最少含有的节点数，则显而易见地，N[1]=1，N[2]=2，并且N[h]=N[h-1]+N[h-2]+1（N>2）,因为高为h的话，必然有一颗子树高为h-1，由于平衡性质，另一颗至少高度为h-2。
对于最后的二阶差分方程，通过代换来齐次化(N[h]+1)=(N[h-1]+1)+(N[h-2]+1)，即得到Fibonacci数列，特征方程x^2-x-1=0，利用初值F[0]=0;F[1]=1求出系数，得到F[n]=(alpha^n-beta^n)/sqrt(5)，其中alpha=(1+sqrt(5))/2,beta=(1-sqrt(5))/2。
则对应地N[h]=F[h+2]-1。
F[n]与alpha^n/sqrt(5)是同阶无穷大。因为
lim(F[n]/(alpha^n/sqrt(5)))=lim(1+((1-sqrt(5))/(1+sqrt(5)))^n)
=lim(1+(-1)^n*((sqrt(5)-1)/(sqrt(5)+1))^n)=lim(1+(-1)^n*0)=1
所以N[h]约等于alpha^(h+2)/sqrt(5)-1。
对应得，h可表示为sqrt(5)*log(N+1)-2。
即，N个点的AVL树，最大深度可表示为O(logN)。
严格的数学证明如上，无奈输入的符号看着较乱，望见谅。追问
对于最后的二阶差分方程，通过代换来齐次化(N[h]+1)=(N[h-1]+1)+(N[h-2]+1)，即得到Fibonacci数列，特征方程x^2-x-1=0，利用初值F[0]=0;F[1]=1求出系数，得到F[n]=(alpha^n-beta^n)/sqrt(5)，其中alpha=(1+sqrt(5))/2,beta=(1-sqrt(5))/2。
则对应地N[h]=F[h+2]-1。
F[n]与alpha^n/sqrt(5)是同阶无穷大。因为
lim(F[n]/(alpha^n/sqrt(5)))=lim(1+((1-sqrt(5))/(1+sqrt(5)))^n)
=lim(1+(-1)^n*((sqrt(5)-1)/(sqrt(5)+1))^n)=lim(1+(-1)^n*0)=1
所以N[h]约等于alpha^(h+2)/sqrt(5)-1。
对应得，h可表示为sqrt(5)*log(N+1)-2。
即，N个点的AVL树，最大深度可表示为O(logN)。
严格的数学证明如上，无奈输入的符号看着较乱，望见谅。追问
证明我提的问题是对的？
追答最后一句“N个点的AVL树，最大深度可表示为O(logN)”
因此，是不大于……，你的结论写反了吧。
平衡树的优点就在于，树不会很高，不会退化。
如果是不小于的话，这个有点就完全没有了。
喔喔 知道啦 谢谢你
还想问你题
本回答被提问者和网友采纳
相似回答
