高度平衡二叉树

1、高度平衡二叉树高度平衡的二叉搜索树nAVL( Addison-Velski and Landis )树n伸展树高度平衡二叉树 二叉搜索树性能分析二叉搜索树性能分析n对于有对于有 n 个关键码的集合，其关键码有个关键码的集合，其关键码有 n! 种种不同排列，可构成不同二叉搜索树有不同排列，可构成不同二叉搜索树有 (棵棵)Cnnn2112, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1123111132223323高度平衡二叉树n同样同样 3 个数据个数据 1, 2, 3 ，输入顺序不同，建立，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响起

2、来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。到二叉搜索树的搜索性能。n如果输入序列选得不好，会建立起一棵单支树，如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大。使得二叉搜索树的高度达到最大。n用树的搜索效率来评价这些二叉搜索树。用树的搜索效率来评价这些二叉搜索树。n为此，在二叉搜索树中加入外结点，形成判定为此，在二叉搜索树中加入外结点，形成判定树。外结点表示失败结点，内结点表示搜索树树。外结点表示失败结点，内结点表示搜索树中已有的数据。中已有的数据。n这样的判定树即为扩充的二叉搜索树。这样的判定树即为扩充的二叉搜索树。高度平衡二叉树n举例说明。已知关键

3、码集合举例说明。已知关键码集合 a1, a2, a3 = do, if, to，对应搜索概率，对应搜索概率p1, p2, p3, 在各搜索不成功间在各搜索不成功间隔内搜索概率分别为隔内搜索概率分别为q0, q1, q2, q3。可能的二叉。可能的二叉搜索树如下所示。搜索树如下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)高度平衡二叉树判定树判定树doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)高度平衡二叉树.*i lipASLnisucc1n在判定树中在

4、判定树中 表示内部结点，包含了关键码集合中的表示内部结点，包含了关键码集合中的某一个关键码；某一个关键码； 表示外部结点，代表各关键码间隔中的表示外部结点，代表各关键码间隔中的不在关键码集合中的关键码。不在关键码集合中的关键码。n在每两个外部结点间必存在一个内部结点。在每两个外部结点间必存在一个内部结点。n一棵判定树上的搜索成功的平均搜索长度一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜可以定义为该树所有内部结点上的搜索概率索概率pi与搜索该结点时所需的关键码比较与搜索该结点时所需的关键码比较次数次数ci (= li, 即结点所在层次即结点所在层次) 乘积之

5、和：乘积之和：高度平衡二叉树n设各关键码的搜索概率相等：设各关键码的搜索概率相等：pi = 1/nn搜索不成功的平均搜索长度搜索不成功的平均搜索长度ASLunsucc为树中所为树中所有外部结点上搜索概率有外部结点上搜索概率qj与到达外部结点所与到达外部结点所需关键码比较次数需关键码比较次数cj(= lj)乘积之和：乘积之和：n设外部结点搜索概率相等：设外部结点搜索概率相等：qj = 1/(n+1)：. nisucci lnASL11njunsuccjljqASL0).1 (*njunsuccjlnASL0(11).1高度平衡二叉树n设树中所有内、外部结点的搜索概率都相等：设树中所有内、外部结点

6、的搜索概率都相等： 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, 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): ASLsucc = 1/3*2+1/3*3+1/3*

7、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。n图图(b)的情形所得的平均搜索长度最小。的情形所得的平均搜索长度最小。高度平衡二叉树n设二叉搜索树中所有内、外部结点的搜索概率设二叉搜索树中所有内、外部结点的搜索概率互不相等。互不相等。 p1 = 0.5, p2 = 0.1, p3 = 0.05 q0 = 0.15, q1 = 0.1

8、, q2 = 0.05, q3 = 0.05n分别计算各个可能的扩充二叉搜索树的搜索性分别计算各个可能的扩充二叉搜索树的搜索性能，判断哪些扩充二叉搜索树的平均搜索长度能，判断哪些扩充二叉搜索树的平均搜索长度最小。最小。(2) 不相等搜索概率的情形不相等搜索概率的情形高度平衡二叉树doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15 q1=0.1 q2=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， ASL

9、unsucc = 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.15+0.1+0.05+0.05)*2 = 0.7。高度平衡二叉树doifto q0=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 =

10、 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高度平衡二叉树n由此可知，图由此可知，图(c)和图和图(e)的情形下树的平均搜索的情形下树的平均搜索长度达到最小，因此，图长度达到最小，因此，图(c)和图和图(e)的情形是最的情形是最优二叉搜索树。优二叉搜索树。doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e) 图图(e) : ASLsuc

11、c = 0.5*1+ 0.1*3+0.05*2 = 0.9; ASLunsucc = 0.15*1+ 0.1*3+0.05*3+0.05*2 = 0.7;高度平衡二叉树n一般把平均搜索长度达到最小的扩充的一般把平均搜索长度达到最小的扩充的二叉搜索树称作最优二叉搜索树。二叉搜索树称作最优二叉搜索树。n等概率条件下，最优二叉搜索树的最短等概率条件下，最优二叉搜索树的最短内部路径长度与最短外部路径长度内部路径长度与最短外部路径长度, 课本课本383页页:.1112log2nniiE.niiI12log高度平衡二叉树 一、什么是平衡二叉树 二、失衡二叉排序树的分析与调整 高度平衡二叉树平衡二叉树又称为

12、平衡二叉树又称为AVL树。树。 左子树与右子树的高度之差的绝对值小于等于左子树与右子树的高度之差的绝对值小于等于1； 左子树和右子树也是平衡二叉排序树。左子树和右子树也是平衡二叉排序树。高度平衡二叉树例：平衡二叉树40247053452860 引入平衡二叉树的目的是为了提高查找效率，引入平衡二叉树的目的是为了提高查找效率， 使使其平均查找长度为其平均查找长度为O(log2n)。402470532860高度平衡二叉树 根据平衡二叉树的定义，根据平衡二叉树的定义， 平衡二叉树上所有结点平衡二叉树上所有结点的平衡因子只能是的平衡因子只能是-1、 0，或，或1。当我们在一个平衡二。当我们在一个平衡二叉

13、排序树上插入一个结点时，有可能导致失衡，即出叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于现绝对值大于1的平衡因子，如的平衡因子，如2、-2。 为了方便起见，给每个结点附加一个为了方便起见，给每个结点附加一个，给出，给出。这个数字称为结点的。这个数字称为结点的高度平衡二叉树40247053452860402470532860例：下图对平衡二叉树和失去平衡的二叉排序树分别下图对平衡二叉树和失去平衡的二叉排序树分别标注了平衡因子。标注了平衡因子。高度平衡二叉树 一、什么是平衡二叉树 二、失衡二叉排序树的分析与调整 高度平衡二叉树 如果在一棵如果在一棵AVL树中插入一个新结点，就有可能造

14、树中插入一个新结点，就有可能造成失衡，此时必须成失衡，此时必须，使之恢复平衡。，使之恢复平衡。我们称调整平衡过程为我们称调整平衡过程为。现分别介绍这四种平衡旋转。现分别介绍这四种平衡旋转。v LL平衡旋转平衡旋转v RR平衡旋转平衡旋转v LR平衡旋转平衡旋转v RL平衡旋转平衡旋转高度平衡二叉树 若在若在A A的的结点，使结点，使A A的平的平衡因子从衡因子从1 1增加至增加至2 2，需要进行一次，需要进行一次。1）LL平衡旋转：平衡旋转：高度平衡二叉树hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABDh高度平衡二叉树 左改组（新插入结点出现在危机结点的左子树上进行

15、的调整）左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：的情况分析：1、LL 情况：（情况：（LL：表示新插入结点在危机结点的表示新插入结点在危机结点的 左子树左子树的的左子树上左子树上）AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：高度为 h + 1 中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为 h + 1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平衡度为平衡度为 0AB高度平衡二叉树 若在若在A A的的结点，使结点，使A A的平衡的平衡因子从

16、因子从-1-1增加至增加至-2-2，需要进行一次，需要进行一次。高度平衡二叉树hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABD高度平衡二叉树 若在若在A A的的结点，使结点，使A A的平的平衡因子从衡因子从1 1增加至增加至2 2，需要，需要，。 3）LR平衡旋转：平衡旋转：高度平衡二叉树2、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的 左子树的右子树上）左子树的右子树上） 情况情况A：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前： 高度为高度为 h + 1 中序序列：中序序列：注意：改组后

17、注意：改组后 平衡度为平衡度为 0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：改组后： 高度为高度为 h + 1 中序序列：中序序列：ABBLARCCLCRA高度平衡二叉树Double RotationsFig. 28-7 (a) The AVL tree in Fig. 28-5 after additions that maintain its balance; (b) after an addition that destroys the balance continued 高度平衡二叉树Double

18、 RotationsFig. 28-7 (ctd.) (c) after a left rotation; (d) after a right rotation.高度平衡二叉树若在若在A A的的结点，使结点，使A A的平衡因子的平衡因子从从-1-1增加至增加至-2-2，需要，需要，。 高度平衡二叉树 综上所述，综上所述， 在一个平衡二叉排序树上插入一个新在一个平衡二叉排序树上插入一个新结点结点S S时，主要包括以下三步：时，主要包括以下三步： (1)(1)查找应插位置，同时记录离插入位置最近的可能查找应插位置，同时记录离插入位置最近的可能失衡结点失衡结点A A（A A的平衡因子不等于的平衡因子

19、不等于0 0）。）。 (2)(2)插入新结点插入新结点S S， 并修改从并修改从A A到到S S路径上各结点的平路径上各结点的平衡因子。衡因子。 (3)(3)根据根据A A、 B B的平衡因子，的平衡因子， 判断是否失衡以及失衡判断是否失衡以及失衡类型，类型， 并做相应处理。并做相应处理。 高度平衡二叉树Double RotationsFig. 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 a

20、nd (c) a left rotation.高度平衡二叉树0 00 00 0例：例：请将下面序列构成一棵平衡二叉排序树：请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53）0 00 0-1-10 0 -1-1需要需要RR平衡旋平衡旋转转(绕绕B逆转逆转,B为为根）根）0 0-1-1-1-10 01 1需要需要RL平衡平衡旋转旋转(绕绕C先顺先顺后逆）后逆）0 00 00 00 00 00 0高度平衡二叉树n例如，输入关键码序列为例如，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。，插入和调整过程如下。160163-

21、 -10731600073110- -111637169000111163701273161190- -1- -223711269160112高度平衡二叉树右左双旋右左双旋0左单旋左单旋181600732611900031609171126183- -1- -17161426911173918261116高度平衡二叉树151831816731171491615112626149从空树开始的建树过程从空树开始的建树过程高度平衡二叉树各种搜索结构的比较n课本397页 图10.14高度平衡二叉树作业n1、设有关键码序列55，31，11，37，46，73，63，02，07，从空树开始构造平衡二叉搜索树

22、，画出每加入一个新结点时二叉树的形态。高度平衡二叉树伸展树（伸展树（Splaying TreeSplaying Tree） n伸展树、伸展树、AVL树、并查集的用双亲表示的树，树、并查集的用双亲表示的树，都属于自调整数据结构（都属于自调整数据结构（self-adjusting data structure）。）。nAVL树使得搜索树保持高度平衡，让叶结点树使得搜索树保持高度平衡，让叶结点只出现在最低的一层或两层上，从而提高其只出现在最低的一层或两层上，从而提高其搜索效率。搜索效率。n伸展树是另一种提高搜索效率的方法，其思伸展树是另一种提高搜索效率的方法，其思路是：路是：1.单一旋转：将经常访问

23、的结点最终上移到单一旋转：将经常访问的结点最终上移到靠近根的地方，使以后的访问更快。靠近根的地方，使以后的访问更快。高度平衡二叉树移动到根部：假设正访问的结点将以很高移动到根部：假设正访问的结点将以很高的概率再次被访问，对它反复进行子女的概率再次被访问，对它反复进行子女父结点旋转，直到被访问的结点位于根部父结点旋转，直到被访问的结点位于根部为止。为止。n伸展树提出了一组改进二叉搜索树性能的一伸展树提出了一组改进二叉搜索树性能的一组规则，每当执行搜索、插入、删除等操作组规则，每当执行搜索、插入、删除等操作时，就要依据这些规则调整二叉搜索树，从时，就要依据这些规则调整二叉搜索树，从而保证操作的时间

24、代价。而保证操作的时间代价。n每当访问（搜索、插入或删除）一个结点每当访问（搜索、插入或删除）一个结点 s 时，时，伸展树就执行一次叫做伸展树就执行一次叫做“展开展开(splaying)”的过的过程，将结点程，将结点 s 移到二叉搜索树的根部。移到二叉搜索树的根部。 高度平衡二叉树n就像就像AVL树，一次树，一次“展开展开”由一组旋转组成。由一组旋转组成。n旋转有三种类型：单旋转、一字形旋转和之旋转有三种类型：单旋转、一字形旋转和之字形旋转。字形旋转。n一次旋转的目的是通过调整结点一次旋转的目的是通过调整结点 s 与它的父与它的父结点结点 p 和祖父结点和祖父结点 g 之间位置，把它上移到之间

25、位置，把它上移到树的更高层。树的更高层。1.被访问结点被访问结点 s 的父结点的父结点 p 是根结点。此时执是根结点。此时执行单旋转。在保持二叉搜索树特性的情况下，行单旋转。在保持二叉搜索树特性的情况下，结点结点 s 成为新的根，原来的根成为新的根，原来的根 p 成为它的子成为它的子女结点。女结点。 高度平衡二叉树n同构形状（同构形状（homogeneous configuration）。）。结点结点 s 是其父结点是其父结点 p 的左子女，结点的左子女，结点 p 又是又是其父结点其父结点 g 的左子女的左子女()。或者结点。或者结点 s 是其是其父结点父结点 p 的右子女，结点的右子女，结点

26、 p 又是其父结点又是其父结点g 的右子女的右子女()。此时执行一字形旋转。此时执行一字形旋转 (zigzig rotation): p s s p右单旋转高度平衡二叉树n异构的形状（异构的形状（heterogeneous configuration）。）。结点结点 s 是其父结点是其父结点 p 的左子女，结点的左子女，结点 p 又是其又是其父结点父结点 g 的右子女的右子女()。或结点。或结点 s 是其父结点是其父结点 p 的右子女，结点的右子女，结点 p 又是其父结点又是其父结点 g 的左子女的左子女()。此时执行之字形旋转。此时执行之字形旋转(zigzag rotation)。 pg s

27、 pg s pg s 右单旋转右单旋转高度平衡二叉树n因为刚访问的结点因为刚访问的结点 s 与其父结点与其父结点 p 和祖父结点和祖父结点g 形成折线，需要做与形成折线，需要做与AVL树一样的双旋转，树一样的双旋转，首先围绕首先围绕 s 旋转旋转 p，再围绕，再围绕 s 旋转旋转 g，把结点，把结点 s上升到祖父结点的位置，并保持二叉搜索树的上升到祖父结点的位置，并保持二叉搜索树的特性。特性。 pg s pg s sg p 左单旋转右单旋转高度平衡二叉树将刚访问的结点将刚访问的结点s s上移到树根部的算法上移到树根部的算法 splaying (g, p, s) /g 是 p 的父结点，p 是

28、s 的父结点/算法将s移到根结点位置 while (s 不是树的根结点不是树的根结点) if (s 的父结点是根结点的父结点是根结点) 进行单旋转进行单旋转, , 将将 s 调整为根结点调整为根结点 else if (s 与它的前驱与它的前驱 p, g 是同构形状是同构形状) 进行一字形双旋转，将进行一字形双旋转，将 s 上移上移 else /s 与它的前驱与它的前驱 p, g 是异构形状是异构形状 进行之字形双旋转，将进行之字形双旋转，将 s 上移上移; 高度平衡二叉树伸展树的性能分析伸展树的性能分析n之字形旋转使得树结构趋向于平衡化，结果常之字形旋转使得树结构趋向于平衡化，结果常常使树结构

29、的高度减少常使树结构的高度减少1。而一字形旋转一般。而一字形旋转一般不会降低树结构的高度，它只是把刚访问的结不会降低树结构的高度，它只是把刚访问的结点向根结点上移。点向根结点上移。n伸展树不要求每一个操作都是高效的，对于一伸展树不要求每一个操作都是高效的，对于一个有个有 n 个结点的树，执行个结点的树，执行 m 次操作时可能一次操作时可能一次插入或搜索操作需要花费次插入或搜索操作需要花费O(n)时间。时间。n例如，对于一个有例如，对于一个有 n 个结点的单支树，访问最个结点的单支树，访问最底层的结点，需要时间即为底层的结点，需要时间即为O(n)。高度平衡二叉树n当当mn时，所有时，所有m个操作

30、总共需要个操作总共需要O(mlog2n)时时间，从而使每次访问操作的所花费的平均时间间，从而使每次访问操作的所花费的平均时间达到达到O(log2n)，从整体上保持较高的时间性能。，从整体上保持较高的时间性能。n下面的实例描述了伸展树如何通过下面的实例描述了伸展树如何通过“展开展开”实实现自调整。首先在伸展树中搜索现自调整。首先在伸展树中搜索70，搜索过程，搜索过程与二叉搜索树完全一样，一旦搜索成功，就执与二叉搜索树完全一样，一旦搜索成功，就执行行“展开展开”过程将该结点上移到根结点位置。过程将该结点上移到根结点位置。n伸展树的插入操作与二叉搜索树相同，但结点伸展树的插入操作与二叉搜索树相同，但

31、结点一经插入之后立即展开到根结点。一经插入之后立即展开到根结点。 高度平衡二叉树608030201070409050608030201070409050608030201070409050608030201070409050zigzig双旋转双旋转zigzag双旋转双旋转左单旋转左单旋转70调整完调整完高度平衡二叉树n从伸展树中删除一个结点的操作也与二叉搜从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删结点的父结点展开索树相同，但需要把被删结点的父结点展开到根结点。到根结点。n伸展树与伸展树与AVL树在操作上稍有不同。伸展树树在操作上稍有不同。伸展树的调整与结点被访问（包括搜索、插

32、入、删的调整与结点被访问（包括搜索、插入、删除）的频率有关，能够进行更合理的调整。除）的频率有关，能够进行更合理的调整。而而AVL树的结构调整只与插入、删除的顺序树的结构调整只与插入、删除的顺序有关，与访问的频率无关。有关，与访问的频率无关。 高度平衡二叉树红黑树（红黑树（Red-Black TreeRed-Black Tree） n红黑树是一棵二叉搜索树：树中的每一个结红黑树是一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示黑树视为一棵扩充二叉树，用外部结点表示空指针。其特性描述如下：空指针。其特

33、性描述如下：特性特性1：根结点和所有外部结点的颜色是黑：根结点和所有外部结点的颜色是黑色。色。特性特性2：从根结点到外部结点的途中没有连：从根结点到外部结点的途中没有连续两个结点的颜色是红色。续两个结点的颜色是红色。特性特性3：所有从根到外部结点的路径上都有：所有从根到外部结点的路径上都有相同数目的黑色结点。相同数目的黑色结点。 高度平衡二叉树n从红黑树中任一结点从红黑树中任一结点 x 出发出发(不包括结点不包括结点 x )，到达一个外部结点的任一路径上的黑结点个数到达一个外部结点的任一路径上的黑结点个数叫做结点叫做结点 x 的黑高度，称为结点的阶的黑高度，称为结点的阶(rank)，记作记作

34、bh(x)。红黑树的黑高度定义为其根结点。红黑树的黑高度定义为其根结点的黑高度。的黑高度。501030204060702050红色结点红色结点黑色结点黑色结点外部结点外部结点高度平衡二叉树n另一种等价的定义是看结点指针的颜色。另一种等价的定义是看结点指针的颜色。n从父结点到黑色子女结点的指针为黑色的，从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。从父结点到红色子女结点的指针为红色的。50103020406070高度平衡二叉树特性特性1：从内部结点指向外部结点的指针：从内部结点指向外部结点的指针是黑色的。是黑色的。特性特性2：从根结点到外部结点的途中没有：从根结点到

35、外部结点的途中没有两个连续的红色指针。两个连续的红色指针。特性特性3：所有根到外部结点的路径上都有：所有根到外部结点的路径上都有相同数目的黑色指针。相同数目的黑色指针。n如果知道指针的颜色，就能推断结点的颜色，如果知道指针的颜色，就能推断结点的颜色，反之亦然。反之亦然。n设从根到外部结点的路径长度设从根到外部结点的路径长度 (Path Length, PL) 为该路径上指针的个数，为该路径上指针的个数， 高度平衡二叉树n结论结论1 如果如果P与与Q是红黑树中的两条从根到外是红黑树中的两条从根到外部结点的路径，则有：部结点的路径，则有：PL(P)2PL(Q)证明：考查任意一棵红黑树。假设根结点的

36、黑证明：考查任意一棵红黑树。假设根结点的黑高度高度bh(root) = r。由特性。由特性1可知，每条从根结可知，每条从根结点到外部结点的路径中最后一个指针为黑色；点到外部结点的路径中最后一个指针为黑色；从特性从特性2可知，不存在有连续两个红色指针的可知，不存在有连续两个红色指针的路径。因此，每个红色指针后面都会跟随一个路径。因此，每个红色指针后面都会跟随一个黑色指针，每条从根到外部结点的路径上都有黑色指针，每条从根到外部结点的路径上都有r2r个指针，综上所述有个指针，综上所述有 PL(P)2PL(Q)。高度平衡二叉树n如上图，从根到如上图，从根到 40 左下的外部结点的路径长左下的外部结点的

37、路径长度度PL(40) = 4，从根到，从根到70右下的外部结点的路右下的外部结点的路径长度径长度PL(70) = 3，因此，因此PL(40)PL(70)或者或者PL(70)PL(40)。 50103020406070PL=4, bh=2 PL=3, bh=2高度平衡二叉树n结论结论2 设设 h 是一棵红黑树的高度是一棵红黑树的高度( 不包括外部不包括外部结点结点)，n 是树中内部结点的个数，是树中内部结点的个数，r 是根结点是根结点的黑高度，则以下关系式成立：的黑高度，则以下关系式成立：(1) h2r (2) n2r-1(3) h2log2(n+1)证明：证明：(1) 从结论从结论1的证明可

38、知，从根到任一外部结点的证明可知，从根到任一外部结点的路径长度不超过的路径长度不超过2r，同时从树的定义可知，同时从树的定义可知，树的高度即为根结点的高度，等于从根到离根树的高度即为根结点的高度，等于从根到离根最远的外部结点的路径的长度，有最远的外部结点的路径的长度，有h2r。高度平衡二叉树(2) 因为红黑树的黑高度为因为红黑树的黑高度为r，则从树的第，则从树的第 1 层层到第到第 r 层没有外部结点，在这些层中有层没有外部结点，在这些层中有2r-1个个内部结点，即内部结点的总数至少为内部结点，即内部结点的总数至少为2r-1。(3) 由由(2)可得可得rlog2(n+1)，结合，结合(1)，有

39、，有h2log2(n+1)。n由于红黑树的高度最大为由于红黑树的高度最大为2log2(n+1)，所以搜，所以搜索、插入、删除操作的时间复杂性为索、插入、删除操作的时间复杂性为O(log2n)。注意，最差情况下的红黑树的高度大于最差情注意，最差情况下的红黑树的高度大于最差情况下具有相同结点个数的况下具有相同结点个数的AVL树的高度（近似树的高度（近似于于1.44*log2(n+2)）。）。高度平衡二叉树红黑树的搜索红黑树的搜索 n由于每一棵红黑树都是二叉搜索树，可以使由于每一棵红黑树都是二叉搜索树，可以使用二叉搜索树的算法进行搜索。在搜索过程用二叉搜索树的算法进行搜索。在搜索过程中不需使用颜色信

40、息。中不需使用颜色信息。n对普通二叉搜索树进行搜索的时间复杂性为对普通二叉搜索树进行搜索的时间复杂性为O(h)，对于红黑树则为，对于红黑树则为O(log2n)。因为在搜索。因为在搜索二叉搜索树、二叉搜索树、AVL树和红黑树时使用了相同树和红黑树时使用了相同算法。在最差情况下算法。在最差情况下AVL树的高度最小，因树的高度最小，因此，在那些以搜索操作为主的应用程序中，此，在那些以搜索操作为主的应用程序中，最差情况下最差情况下AVL树能获得最优时间复杂性。树能获得最优时间复杂性。 高度平衡二叉树红黑树的插入红黑树的插入 n首先使用二叉搜索树的插入算法将一个元素首先使用二叉搜索树的插入算法将一个元素

41、插入到红黑树中，该元素将作为新的叶结点插入到红黑树中，该元素将作为新的叶结点插入。在插入过程中需要为新元素染色。插入。在插入过程中需要为新元素染色。1.如果插入前是空树，则那么新元素将成为根如果插入前是空树，则那么新元素将成为根结点，根据特征结点，根据特征1，根结点必须染成黑色。，根结点必须染成黑色。 高度平衡二叉树n如果插入前树非空，若新结点被染成黑色，如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性将违反红黑树的特性3，所有从根到外部结所有从根到外部结点的路径上的黑色结点个数不等点的路径上的黑色结点个数不等。因此，新。因此，新插入的结点将染成红色，但这又可能违反红插入的结点将染成红

42、色，但这又可能违反红黑树的特性黑树的特性2，出现连续两个红色结点，因，出现连续两个红色结点，因此需要重新平衡。此需要重新平衡。guuL插入高度平衡二叉树n设新插入的结点为设新插入的结点为u，它的父结点和祖父结点，它的父结点和祖父结点分别是分别是pu和和gu，现在来考查不平衡的类型。，现在来考查不平衡的类型。若若pu是黑色结点，则特性是黑色结点，则特性2没有破坏，结束重没有破坏，结束重新平衡的过程。若新平衡的过程。若pu是红色结点，则出现连是红色结点，则出现连续两个红色结点的情形，这时还要考查续两个红色结点的情形，这时还要考查pu的的兄弟结点。兄弟结点。插入puguugr高度平衡二叉树1) 如果

43、如果pu的兄弟结点的兄弟结点gr是红色结点，此时结是红色结点，此时结点点pu的父结点的父结点gu是黑色结点，它有两个是黑色结点，它有两个红色子女结点。交换结点红色子女结点。交换结点gu和它的子女结和它的子女结点的颜色，将可能破坏红黑树特性点的颜色，将可能破坏红黑树特性2的红的红色结点上移。色结点上移。puguugrpuguugruLuRpuRgrLgrRuLuRpuRgrLgrR高度平衡二叉树2) 如果如果pu的兄弟结点的兄弟结点gr是黑色结点，此时又是黑色结点，此时又有两种情况。有两种情况。a) u是是pu的左子女，的左子女，pu是是gu的左子女。在的左子女。在这种情况下只要做一次右单旋转，

44、交换这种情况下只要做一次右单旋转，交换一下一下pu和和gu的颜色，就可恢复红黑树的的颜色，就可恢复红黑树的特性，并结束重新平衡过程。特性，并结束重新平衡过程。pugugrupugugruuLuRpuRgrLgrRuLuRpuRgrLgrR高度平衡二叉树n u是是pu的右子女，的右子女，pu是是gu的左子女。在的左子女。在这种情况下做一次先左后右的双旋转，这种情况下做一次先左后右的双旋转，再交换一下再交换一下u与与gu的颜色，就可恢复红的颜色，就可恢复红黑树的特性，结束重新平衡过程。黑树的特性，结束重新平衡过程。 puL gupuugrgrL grR uRuLgupuugrgrL grR uRu

45、LpuL 高度平衡二叉树n针对上述两种情况，还有镜像情况，即针对上述两种情况，还有镜像情况，即pu是是gu的右子女时，当的右子女时，当u是是pu的右子女则做左单旋的右子女则做左单旋转，当转，当u是是pu的左子女则做先右后左的双旋转。的左子女则做先右后左的双旋转。n红黑树的删除算法与二叉搜索树的删除算法红黑树的删除算法与二叉搜索树的删除算法类似，不同之处在于，在红黑树中执行一次类似，不同之处在于，在红黑树中执行一次二叉搜索树的删除运算，可能会破坏红黑树二叉搜索树的删除运算，可能会破坏红黑树的特性，需要重新平衡。的特性，需要重新平衡。红黑树的删除红黑树的删除高度平衡二叉树n在红黑树中真正删除的结点

46、应是叶结点或只在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。有一个子女的结点。n如果被删结点如果被删结点p是红色的，删去它树中各结点是红色的，删去它树中各结点的黑高度都没有改变，也不会出现连续两个的黑高度都没有改变，也不会出现连续两个红色结点，红黑树的特性仍然保持，不需执红色结点，红黑树的特性仍然保持，不需执行重新平衡过程。行重新平衡过程。pvguuL uR vRvL vguuL uR vRvL 直接删除高度平衡二叉树n如果被删结点如果被删结点p是黑色的，一旦删去它，红黑是黑色的，一旦删去它，红黑树将不满足特性树将不满足特性3的要求，因为在这条路径上的要求，因为在这条路径上黑色结点少

47、了一个，从根到外部结点的黑高度黑色结点少了一个，从根到外部结点的黑高度将会降低。将会降低。n可以将结点可以将结点u视为具有双重黑色的结点，这样视为具有双重黑色的结点，这样任意包含结点任意包含结点u的路径上的黑高度仍保持删除的路径上的黑高度仍保持删除前的值，就能恢复红黑树的特性。前的值，就能恢复红黑树的特性。n问题是在红黑树的定义中没有包括双重黑色的问题是在红黑树的定义中没有包括双重黑色的结点，因此必须通过旋转变换和改变结点的颜结点，因此必须通过旋转变换和改变结点的颜色，消除双重黑色结点，恢复红黑树的特性。色，消除双重黑色结点，恢复红黑树的特性。高度平衡二叉树n设设u是被删结点是被删结点p的唯一子女结点。如果结的唯一子女结点。如果结点点u是红色结点，可以把是红色结点，可以把u染成黑