《高度平衡的二叉树》由会员分享，可在线阅读，更多相关《高度平衡的二叉树（79页珍藏版）》请在金锄头文库上搜索。
1、高度平衡的二叉搜索树,AVL( Addison-Velski and Landis )树 伸展树 红黑树,二叉搜索树性能分析,对于有 n 个关键码的集合，其关键码有 n! 种不同排列，可构成不同二叉搜索树有 (棵),2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1,同样 3 个数据 1, 2, 3 ，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。 如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大。 用树的搜索效率来评价这些二叉搜索树。 为此，在二叉搜索树中加入外结点，形成判定树。外结点表示失
2、败结点，内结点表示搜索树中已有的数据。 这样的判定树即为扩充的二叉搜索树。,举例说明。已知关键码集合 a1, a2, a3 = do, if, to，对应搜索概率p1, p2, p3, 在各搜索不成功间隔内搜索概率分别为q0, q1, q2, q3。可能的二叉搜索树如下所示。,判定树,在判定树中 表示内部结点，包含了关键码集合中的某一个关键码； 表示外部结点，代表各关键码间隔中的不在关键码集合中的关键码。 在每两个外部结点间必存在一个内部结点。 一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率pi与搜索该结点时所需的关键码比较次数ci (= li, 即结
3、点所在层次) 乘积之和：,设各关键码的搜索概率相等：pi = 1/n 搜索不成功的平均搜索长度ASLunsucc为树中所有外部结点上搜索概率qj与到达外部结点所需关键码比较次数cj(= lj)乘积之和： 设外部结点搜索概率相等：qj = 1/(n+1)：,设树中所有内、外部结点的搜索概率都相等： pi = 1/3, 1i3, qj = 1/4, 0 j3 图(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, ASLu
4、nsucc = 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): ASLsucc = 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)的情形所得的平均搜索长度最小。,设二叉
5、搜索树中所有内、外部结点的搜索概率互不相等。 p1 = 0.5, p2 = 0.1, p3 = 0.05 q0 = 0.15, q1 = 0.1, q2 = 0.05, q3 = 0.05 分别计算各个可能的扩充二叉搜索树的搜索性能，判断哪些扩充二叉搜索树的平均搜索长度最小。,(2) 不相等搜索概率的情形,图(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， ASLunsucc = (0
6、.15+0.1+0.05+0.05)*2 = 0.7。,图(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, ASLunsucc = 0.15*2+0.1*3+0.05*3+0.05*1 = 0.8.,由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小，因此，图(c)和图(e)的情形是最优二叉搜索树。,图(e) : ASLsucc = 0.5*1+ 0.1*3+0.05*2
7、 = 0.9; ASLunsucc = 0.15*1+ 0.1*3+0.05*3+0.05*2 = 0.7;,一般把平均搜索长度达到最小的扩充的二叉搜索树称作最优二叉搜索树。 等概率条件下，最优二叉搜索树的最短内部路径长度与最短外部路径长度, 课本383页:, 一、什么是平衡二叉树 二、失衡二叉排序树的分析与调整,平衡二叉树,平衡二叉树又称为AVL树。 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树： 左子树与右子树的高度之差的绝对值小于等于1； 左子树和右子树也是平衡二叉排序树。,例：平衡二叉树,引入平衡二叉树的目的是为了提高查找效率， 使其平均查找长度为O(log2n)。,根据平
8、衡二叉树的定义， 平衡二叉树上所有结点的平衡因子只能是-1、 0，或1。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子，如2、-2。,为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子。,例：下图对平衡二叉树和失去平衡的二叉排序树分别标注了平衡因子。,一、什么是平衡二叉树 二、失衡二叉排序树的分析与调整,平衡二叉树,如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。,现分别介绍这四种平衡旋转。,平衡旋转可以归纳为四类： LL平衡旋转
9、 RR平衡旋转 LR平衡旋转 RL平衡旋转,若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。 (以B为旋转轴）,1）LL平衡旋转：,右单旋转 (RotateRight ),h,h,h,A,C,E,B,D,(a) (b) (c),h,h + 1,B,A,C,E,D,h,h,h + 1,C,E,A,B,D,在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到 -2，造成了不平衡。 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。 以结点B为旋转轴，将结点A顺时针旋转。,h,0,0,0,-1,-1
10、,-2,左改组（新插入结点出现在危机结点的左子树上进行的调整） 的情况分析： 1、LL 情况：（LL：表示新插入结点在危机结点的 左子树的左子树上）,A,B,+1,h-1,0,+2,+1,h,h-1,h-1,LL 改组,BL,BR,AR,B,A,0,h,0,h-1,h-1,BL,BR,AR,危机结点,改组前：高度为 h + 1 中序序列：,A,B,BL,BR,AR,改组后：高度为 h + 1 中序序列：,A,B,BL,BR,AR,注意：改组后 平衡度为 0,A,B,若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。 (以B为旋转轴）,2）RR平衡旋转：,
11、左单旋转 (RotateLeft ),h,h,h,A,C,E,B,D,(a) (b) (c),h,h,h + 1,B,A,C,E,D,h,h,h + 1,C,E,A,B,D,如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。 沿插入路径检查三个结点A、C和E。它们处于一条方向为“”的直线上，需要做左单旋转。 以结点C为旋转轴，让结点A反时针旋转。,+1,+2,0,+1,0,0,若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。 (以插入的结点C为旋转轴）,3）LR平衡旋转：,2、LR 情况：（LR：表示新插入结
12、点在危机结点的 左子树的右子树上） 情况A：,A,B,+1,h-1,0,+2,-1,h-1,LR 改组,BL,AR,危机结点,改组前： 高度为 h + 1 中序序列：,注意：改组后 平衡度为 0,0,-1,C,B,C,CL,CR,h-2,h-2,h-1,0,+1,C,B,0,h-1,h-1,BL,AR,A,CR,h-2,CL,h-1,-1,0,A,B,BL,AR,C,CL,CR,改组后： 高度为 h + 1 中序序列：,A,B,BL,AR,C,CL,CR,A,Double Rotations,Fig. 28-7 (a) The AVL tree in Fig. 28-5 after addit
13、ions that maintain its balance; (b) after an addition that destroys the balance continued ,Double Rotations,Fig. 28-7 (ctd.) (c) after a left rotation; (d) after a right rotation.,若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。 (以插入的结点C为旋转轴）,4）RL平衡旋转：,这种调整规则可以保证二叉排序树的次序不变,综上所述， 在一个平衡二叉排序树上插入一个新结
14、点S时，主要包括以下三步： (1)查找应插位置，同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。 (2)插入新结点S， 并修改从A到S路径上各结点的平衡因子。 (3)根据A、 B的平衡因子， 判断是否失衡以及失衡类型， 并做相应处理。,Double Rotations,Fig. 28-5 (a) Adding 70 to the tree in Fig. 28-2c destroys its balance; to restore the balance, perform both (b) a right rotation and (c) a left rotation.,例：
15、请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53）,0 13,-1 13,-1 24,-2 13,需要RR平衡旋转(绕B逆转,B为根）,-1 24,-1 37,1 90,-2 37,需要RL平衡旋转(绕C先顺后逆）,例如，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。,左右双旋,右单旋,15,18,2,3,18,16,-2,左右双旋,7,3,0,0,0,11,7,14,9,-1,16,15,0,1,11,26,26,14,1,-2,9,从空树开始的建树过程,各种搜索结构的比较,课本397页 图10.14,作业,1、设有关键码序列55，31，11，37，46，73，63，02，07，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。,伸展树（Splaying Tree）,伸展树、AVL树、并查集的用双亲表示的树，都属于自调整数据结构（self-adjusting data structure）。 AVL树使得搜索树保持高度平衡，让叶结点只出现在最低的一层或两层上，从而提高其搜索效率。 伸展树是另一种提高搜索效率的方法，其思路是： 单一旋转：将经常访问的结点最终上移到靠近根的地方，使以后的访问更快。,
