具有N个结点的平衡二叉树的深度一定不小于logn对么？为什么
2个回答
展开全部
证：设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)”
因此，是不大于……，你的结论写反了吧。
平衡树的优点就在于，树不会很高，不会退化。
如果是不小于的话，这个有点就完全没有了。
本回答被提问者和网友采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
