具有N个结点的平衡二叉树的深度一定不小于logn对么?为什么
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/10/06 00:16:01
具有N个结点的平衡二叉树的深度一定不小于logn对么?为什么
证:设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个点的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)” 因此,是不大于……,你的结论写反了吧。 平衡树的优点就在于,树不会很高,不会退化。 如果是不小于的话,这个有点就完全没有了。
再问: 喔喔 知道啦 谢谢你
再问: 还想问你题
具有N个叶结点二叉树的深度
求解具有n个结点的完全二叉树的深度,写出计算过程
证明具有n个结点的二叉树,其深度至少为[log2n]+1,
具有n个结点的完全二叉树的深度为log2n+1 证明过程是怎样的?
具有256个结点的完全二叉树的深度为______.
具有66个结点的完全二叉树的深度为?
二叉树的基本性质深度为M的二叉树最多有几个结点?具有n个节点的二叉树深度至少为多少?其中?表示取?的整数部分.C语言中
一颗含有N个结点的完全二叉树,他的深度是?怎么算?
在有n个结点的二叉树中,最大深度可达多少?最小深度多少?
假设根结点的层数为1,具有n个结点的二叉树的最大高度是
在一棵具有n个结点的二叉树中,所有结点的空子树等于()
深度为k的完全二叉树至少有 ( ) 个结点,至多有 ( ) 个结点