具有N个结点的平衡二叉树的深度一定不小于logn对么?为什么

来源：学生作业帮助网 编辑：作业帮 时间：2024/07/12 19:14:10
具有N个结点的平衡二叉树的深度一定不小于logn对么?为什么
xTMSP;II LW%taաn8N8c J *Ta|XE`H(ʿЛvn=M(̘ԲQKA''4m#ٴ#(dI#d<m*V-=e7>&oXMk[heSאB*/}݇iվEc nv9f޼HA ۀTfzD*'vgj.YERdK^T")aE4yِu3tP ""GKCT'jr6#AfޑR# z6ԠCnV}k.H5U$7M8:e"+3 0 ,ʠ "k+ZZYfβDϮh Zi$Tૈaߤ묇K*2_O%I~6.ysy4ʌì qN&v6Y“r%K$m>߂TPt"eg;2f} _e,+;{byȳ>YB,xC/OOa>;fYYtHV&-G5۴saPݣ_ 2B߻zDF;sy9sw GY[1ufCF*yh-C/ٳȴ0 ̘i]g_,c8R Rd u:

具有N个结点的平衡二叉树的深度一定不小于logn对么?为什么
具有N个结点的平衡二叉树的深度一定不小于logn对么?为什么

具有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个结点的平衡二叉树的深度一定不小于logn对么?为什么 具有N个结点的平衡二叉树的深度一定不小于log2n.这句话对还是错 具有N个叶结点二叉树的深度具有N个结点的二叉树的深度为N-1到log2n,那么拥有N个叶结点的二叉树深度如何计算呢?百思不得其解, 求解具有n个结点的完全二叉树的深度,写出计算过程 证明具有n个结点的二叉树,其深度至少为[log2n]+1, 具有n个结点的二叉树,其深度至少为（㏒2n)+1,怎么证明? 具有n个结点的二叉树,其深度至少为（㏒2n)+1,为什么,怎么证明? 具有5层结点的平衡二叉树至少有多少个结点 具有n个结点的完全二叉树的深度为log2n+1 证明过程是怎样的? 20个结点构成的平衡二叉树的最大深度是多少? 具有256个结点的完全二叉树的深度为______. 具有66个结点的完全二叉树的深度为? 二叉树的基本性质深度为M的二叉树最多有几个结点?具有n个节点的二叉树深度至少为多少?其中?表示取?的整数部分.C语言中 一颗含有N个结点的完全二叉树,他的深度是?怎么算? 一棵具有n个结点的二叉树,若他有m个叶子结点,则该二叉树中度为1的结点个数是多少 具有65个结点的完全二叉树的高度 在有n个结点的二叉树中,最大深度可达多少?最小深度多少? 假设根结点的层数为1,具有n个结点的二叉树的最大高度是