资源描述：
《高度平衡的二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、高度平衡的二叉搜索树AVL(Addison-VelskiandLandis)树伸展树红黑树二叉搜索树性能分析对于有n个关键码的集合，其关键码有n!种不同排列，可构成不同二叉搜索树有(棵){2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}123111132223323同样3个数据{1,2,3}，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大。用树的搜索效率来评价这些二叉搜索树。为此，在二叉搜索
2、树中加入外结点，形成判定树。外结点表示失败结点，内结点表示搜索树中已有的数据。这样的判定树即为扩充的二叉搜索树。举例说明。已知关键码集合{a1,a2,a3}={do,if,to}，对应搜索概率p1,p2,p3,在各搜索不成功间隔内搜索概率分别为q0,q1,q2,q3。可能的二叉搜索树如下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)判定树doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)在判
3、定树中○表示内部结点，包含了关键码集合中的某一个关键码；□表示外部结点，代表各关键码间隔中的不在关键码集合中的关键码。在每两个外部结点间必存在一个内部结点。一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p[i]与搜索该结点时所需的关键码比较次数c[i](=l[i],即结点所在层次)乘积之和：设各关键码的搜索概率相等：p[i]=1/n搜索不成功的平均搜索长度ASLunsucc为树中所有外部结点上搜索概率q[j]与到达外部结点所需关键码比较次数c'[j](=l'[j])乘积之和：设外部结点搜
4、索概率相等：q[j]=1/(n+1)：设树中所有内、外部结点的搜索概率都相等：p[i]=1/3,1≤i≤3,q[j]=1/4,0≤j≤3图(a):ASLsucc=1/3*3+1/3*2+1/3*1=6/3,ASLunsucc=1/4*3*2+1/4*2+1/4*1=9/4。图(b):ASLsucc=1/3*2*2+1/3*1=5/3,ASLunsucc=1/4*2*4=8/4。图(c):ASLsucc=1/3*1+1/3*2+1/3*3=6/3,ASLunsucc=1/4*1+1/4*2+1/4*3*2=9/4。图(d):ASL
5、succ=1/3*2+1/3*3+1/3*1=6/3,ASLunsucc=1/4*2+1/4*3*2+1/4*1=9/4。(1)相等搜索概率的情形图(e):ASLsucc=1/3*1+1/3*3+1/3*2=6/3,ASLunsucc=1/4*1+1/4*3*2+1/4*2=9/4。图(b)的情形所得的平均搜索长度最小。设二叉搜索树中所有内、外部结点的搜索概率互不相等。p[1]=0.5,p[2]=0.1,p[3]=0.05q[0]=0.15,q[1]=0.1,q[2]=0.05,q[3]=0.05分别计算各个可能的扩充二叉搜索树
6、的搜索性能，判断哪些扩充二叉搜索树的平均搜索长度最小。(2)不相等搜索概率的情形doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15q1=0.1q2=0.05q3=0.05p1=0.5p2=0.1p3=0.05(a)(b)图(a):ASLsucc=0.5*3+0.1*2+0.05*1=1.75，ASLunsucc=0.15*3+0.1*3+0.05*2+0.05*1=0.9。图(b):ASLsucc=0.5*2+0.1*1+0.05*2=1.2，ASL
7、unsucc=(0.15+0.1+0.05+0.05)*2=0.7。doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(d)(c)图(c):ASLsucc=0.5*1+0.1*2+0.05*3=0.85,ASLunsucc=0.15*1+0.1*2+0.05*3+0.05*3=0.75.图(d):ASLsucc=0.5*2+0.1*3+0.05*1=1.35,ASLunsu
8、cc=0.15*2+0.1*3+0.05*3+0.05*1=0.8.由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小，因此，图(c)和图(e)的情形是最优二叉搜索树。doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0
