《高度平衡的二叉树精选文档.ppt》由会员分享，可在线阅读，更多相关《高度平衡的二叉树精选文档.ppt（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、高度平衡的二叉树本讲稿第一页，共七十九页 二叉搜索树性能分析二叉搜索树性能分析n对于有对于有 n 个关键码的集合，其关键码有个关键码的集合，其关键码有 n!种不同排种不同排列，可构成不同二叉搜索树有列，可构成不同二叉搜索树有 (棵棵)2,1,3 1,2,3 1,3,2 2,3,1 3,1,2 3,2,1 123111132223323本讲稿第二页，共七十九页n同样同样 3 个数据个数据 1,2,3，输入顺序不同，建立起来，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。索树的搜索性能。n如果输入序列选得不好，会建立起
2、一棵单支树，如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大。使得二叉搜索树的高度达到最大。n用树的搜索效率来评价这些二叉搜索树。用树的搜索效率来评价这些二叉搜索树。n为此，在二叉搜索树中加入外结点，形成判定树。外为此，在二叉搜索树中加入外结点，形成判定树。外结点表示失败结点，内结点表示搜索树中已有的数据。结点表示失败结点，内结点表示搜索树中已有的数据。n这样的判定树即为这样的判定树即为扩充的二叉搜索树扩充的二叉搜索树。本讲稿第三页，共七十九页n举例说明。已知关键码集合举例说明。已知关键码集合 a1,a2,a3=do,if,to，对应搜索概率对应搜索概率p1,p2,p3,
3、在各搜索不成功间隔内搜在各搜索不成功间隔内搜索概率分别为索概率分别为q0,q1,q2,q3。可能的二叉搜索树如。可能的二叉搜索树如下所示。下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)本讲稿第四页，共七十九页判定树判定树doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)本讲稿第五页，共七十九页n在判定树中在判定树中 表表示示内内部部结结点点，包包含含了了关关键键码码集集合合中中的的某某一个关键码；一个关键码；表表示示外外部部结结点点，代代表表各各关关键键
4、码码间间隔隔中中的的不不在关键码集合中的关键码。在关键码集合中的关键码。n在每两个外部结点间必存在一个内部结点在每两个外部结点间必存在一个内部结点。n一一棵棵判判定定树树上上的的搜搜索索成成功功的的平平均均搜搜索索长长度度ASLsucc可可以以定定义义为为该该树树所所有有内内部部结结点点上上的的搜搜索索概概率率pi与与搜搜索索该该结结点点时时所所需需的的关关键键码码比比较较次次数数ci(=li,即结点所在层次即结点所在层次)乘积之和：乘积之和：本讲稿第六页，共七十九页n设各关键码的搜索概率相等：设各关键码的搜索概率相等：pi=1/nn搜索不成功的平均搜索长度搜索不成功的平均搜索长度ASLuns
5、ucc为树中所有外为树中所有外部结点上搜索概率部结点上搜索概率qj与到达外部结点所需关键与到达外部结点所需关键码比较次数码比较次数cj(=lj)乘积之和：乘积之和：n设外部结点搜索概率相等：设外部结点搜索概率相等：qj=1/(n+1)：本讲稿第七页，共七十九页n设树中所有内、外部结点的搜索概率都相等：设树中所有内、外部结点的搜索概率都相等：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
6、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。n图图(b)的情形所得的平均搜索长度最小。的情形所得的平均搜索长度最小。本讲稿
7、第九页，共七十九页n设二叉搜索树中所有内、外部结点的搜索概率互不设二叉搜索树中所有内、外部结点的搜索概率互不相等。相等。p1=0.5,p2=0.1,p3=0.05 q0=0.15,q1=0.1,q2=0.05,q3=0.05n分别计算各个可能的扩充二叉搜索树的搜索性能，判分别计算各个可能的扩充二叉搜索树的搜索性能，判断哪些扩充二叉搜索树的平均搜索长度最小。断哪些扩充二叉搜索树的平均搜索长度最小。(2)不相等搜索概率的情形不相等搜索概率的情形本讲稿第十页，共七十九页doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15
8、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，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.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=
9、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,ASLunsucc=0.15*2+0.1*3+0.05*3+0.05*1=0.8.本讲稿第十二页，共七十九页n由此可知，图由此可知，图(c)和图和图(e)的情形下树的平均搜索长度的情形下树的平均搜索长度达到最小，因此，图达到最小，因此，图(c)和图和图(e)的情形是最优二叉搜的情形是最优二叉搜索树。索树。doift
10、oq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e)图图(e):ASLsucc=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页页:本讲稿第十四页，共七十九页 一、什么
11、是平衡二叉树 二、失衡二叉排序树的分析与调整 平衡二叉树本讲稿第十五页，共七十九页平衡二叉树又称为平衡二叉树又称为AVL树。树。一棵平衡二叉树或者是空树，或者是具有下列性质一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：的二叉排序树：左子树与右子树的高度之差的绝对值小于等于左子树与右子树的高度之差的绝对值小于等于1；左子树和右子树也是平衡二叉排序树。左子树和右子树也是平衡二叉排序树。本讲稿第十六页，共七十九页例：平衡二叉树40247053452860 引入平衡二叉树的目的是为了提高查找效率，引入平衡二叉树的目的是为了提高查找效率，使其平均使其平均查找长度为查找长度为O(log2n)。
12、402470532860本讲稿第十七页，共七十九页 根据平衡二叉树的定义，根据平衡二叉树的定义，平衡二叉树上所有结点平衡二叉树上所有结点的平衡因子只能是的平衡因子只能是-1、0，或，或1。当我们在一个平衡二。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于现绝对值大于1的平衡因子，如的平衡因子，如2、-2。为了方便起见，给每个结点附加一个为了方便起见，给每个结点附加一个数字数字数字数字，给出，给出该结点左该结点左该结点左该结点左子树与右子树的高度差子树与右子树的高度差子树与右子树的高度差子树与右子树的高度差。这个数字称为
13、结点的。这个数字称为结点的平衡因子。平衡因子。平衡因子。平衡因子。本讲稿第十八页，共七十九页40247053452860402470532860例：下图对平衡二叉树和失去平衡的二叉排序树分别下图对平衡二叉树和失去平衡的二叉排序树分别标注了平衡因子。标注了平衡因子。0 01 1-1-1-1-10 00 0-1-11 10 0-1-1-2-20 0-1-1本讲稿第十九页，共七十九页 一、什么是平衡二叉树 二、失衡二叉排序树的分析与调整 平衡二叉树本讲稿第二十页，共七十九页 如果在一棵如果在一棵AVL树中插入一个新结点，就有可能造成失衡，树中插入一个新结点，就有可能造成失衡，此时必须此时必须重新调整
14、树的结构重新调整树的结构重新调整树的结构重新调整树的结构，使之恢复平衡。我们称调整平衡过，使之恢复平衡。我们称调整平衡过程为程为平衡旋转平衡旋转平衡旋转平衡旋转。现分别介绍这四种平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：v LL平衡旋转平衡旋转v RR平衡旋转平衡旋转v LR平衡旋转平衡旋转v RL平衡旋转平衡旋转本讲稿第二十一页，共七十九页若在若在A的的左子树的左子树上插入左子树的左子树上插入左子树的左子树上插入左子树的左子树上插入结点，使结点，使A的平衡因子的平衡因子从从1增加至增加至2，需要进行一次
15、，需要进行一次顺时针旋转顺时针旋转顺时针旋转顺时针旋转。(以以以以B B为旋转轴）为旋转轴）为旋转轴）为旋转轴）1）LL平衡旋转：平衡旋转：A AB BC CA AB BC C本讲稿第二十二页，共七十九页右单旋转右单旋转 (RotateRight)(RotateRight)hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABD在左子树在左子树D上插入新结点使其高度增上插入新结点使其高度增1，导致结点，导致结点A的的平衡因子增到平衡因子增到-2，造成了不平衡。，造成了不平衡。为使树恢复平衡，从为使树恢复平衡，从A沿插入路径连续取沿插入路径连续取3个结点个结点A、B和和D，它们处
16、于一条方向为，它们处于一条方向为“/”的直线上，需要做的直线上，需要做右单旋转。右单旋转。以结点以结点B为旋转轴，将结点为旋转轴，将结点A顺时针旋转顺时针旋转。h0 00 00 0-1 1-1 1-2 2本讲稿第二十三页，共七十九页 左改组（新插入结点出现在危机结点的左子树上进行的调整）左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：的情况分析：1、LL 情况：（情况：（LL：表示新插入结点在危机结点的：表示新插入结点在危机结点的 左子树左子树的的左子树上左子树上）AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结
17、点改组前：高度为改组前：高度为 h+1 中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为 h+1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平衡度为平衡度为 0AB本讲稿第二十四页，共七十九页若在若在A的的右子树的右子树上插入右子树的右子树上插入右子树的右子树上插入右子树的右子树上插入结点，使结点，使A的平衡因子的平衡因子从从-1增加至增加至-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转逆时针旋转逆时针旋转。(以以以以B B为旋转轴）为旋转轴）为旋转轴）为旋转轴）2 2）RRRR平衡旋转：平衡旋转：A AB BC CA AB BC C本讲稿第二十五页，
18、共七十九页左单旋转(RotateLeft)hhhACEBD(a)(b)(c)hhh+1BACEDhhh+1CEABD如如果果在在子子树树E中中插插入入一一个个新新结结点点，该该子子树树高高度度增增1导导致致结点结点A的平衡因子变成的平衡因子变成+2，出现不平衡。，出现不平衡。沿沿插插入入路路径径检检查查三三个个结结点点A、C和和E。它它们们处处于于一一条条方方向为向为“”的直线上，需要做左单旋转。的直线上，需要做左单旋转。以结点以结点C为旋转轴，让结点为旋转轴，让结点A反时针旋转。反时针旋转。+1+1+2+20 0+1+10 00 0本讲稿第二十六页，共七十九页若在若在A的的左左左左子树的子树
19、的子树的子树的右右右右子树上插入子树上插入子树上插入子树上插入结点，使结点，使A的平衡因的平衡因子从子从1增加至增加至2，需要，需要先进行先进行先进行先进行逆逆逆逆时针旋转时针旋转时针旋转时针旋转，再再再再顺顺顺顺时针旋转时针旋转时针旋转时针旋转。(以插入的结点以插入的结点以插入的结点以插入的结点C C为旋转轴）为旋转轴）为旋转轴）为旋转轴）A AB BC CA AB BC CA AB BC C3）LR平衡旋转：平衡旋转：本讲稿第二十七页，共七十九页2、LR 情况：（情况：（LR：表示新插入结点在危机结点的：表示新插入结点在危机结点的 左子树左子树的的右子树上右子树上）情况情况A：AB+1h-
20、10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前：高度为高度为 h+1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 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
21、an addition that destroys the balance continued 本讲稿第二十九页，共七十九页Double RotationsFig.28-7(ctd.)(c)after a left rotation;(d)after a right rotation.本讲稿第三十页，共七十九页若在若在A的的右右右右子树的子树的子树的子树的左左左左子树上插入子树上插入子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从-1增加至增加至-2，需要，需要先进行先进行先进行先进行顺顺顺顺时针旋转时针旋转时针旋转时针旋转，再再再再逆逆逆逆时针旋转时针旋转时针旋转时针旋转。(以
22、插入的结点以插入的结点以插入的结点以插入的结点C C为旋转轴）为旋转轴）为旋转轴）为旋转轴）4 4 4 4）RLRLRLRL平衡旋转：平衡旋转：平衡旋转：平衡旋转：A AB BC CA AB BC CA AB BC C这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变本讲稿第三十一页，共七十九页 综综上上所所述述，在在一一个个平平衡衡二二叉叉排排序序树树上上插插入入一一个个新新结点结点S时，主要包括以下三步：时，主要包括以下三步：(1)查查找找应应插插位位置置，同同时时记记录录离离插插
23、入入位位置置最最近近的的可可能能失衡结点失衡结点A（A的平衡因子不等于的平衡因子不等于0）。）。(2)插插入入新新结结点点S，并并修修改改从从A到到S路路径径上上各各结结点点的的平平衡因子。衡因子。(3)根据根据A、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 ri
24、ght rotation and(c)a left rotation.本讲稿第三十三页，共七十九页0 0131313130 0373737370 024242424例：例：请将下面序列构成一棵平衡二叉排序树：请将下面序列构成一棵平衡二叉排序树：（13，24，37，90，53）0 0131313130 037373737-1-1131313130 024242424-1-124242424-2-2-2-213131313需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）0 090909090-1-124242424-1-1373737370 0535353531 190909090-2
25、-2-2-237373737需要需要RL平衡旋平衡旋转转(绕绕C先顺后先顺后逆）逆）0 0373737370 0909090900 0535353530 0373737370 0909090900 053535353本讲稿第三十四页，共七十九页n例如，输入关键码序列为例如，输入关键码序列为 16,3,7,11,9,26,18,14,15，插入和调整过程如下。插入和调整过程如下。160163-10左右双旋左右双旋左右双旋左右双旋731600073110-1116右单旋右单旋右单旋右单旋37169000111163701-273161190-1-223711269160112本讲稿第三十五页，共七
26、十九页右左双旋右左双旋0左单旋左单旋181600732611900031609171126183-1-1716142691112 27390 0182611-1 1161 1本讲稿第三十六页，共七十九页15182 231816-2 2左右双旋左右双旋左右双旋左右双旋730 00 00 0117149-1 116150 01 1112626141 1-2 29从空树开始的建树过程从空树开始的建树过程本讲稿第三十七页，共七十九页各种搜索结构的比较n课本397页 图10.14本讲稿第三十八页，共七十九页作业n1、设有关键码序列55，31，11，37，46，73，63，02，07，从空树开始构造平衡二
27、叉搜索树，画出每加入一个新结点时二叉树的形态。本讲稿第三十九页，共七十九页伸展树（伸展树（Splaying TreeSplaying Tree）n伸展树、伸展树、AVL树、并查集的用双亲表示的树，都树、并查集的用双亲表示的树，都属于自调整数据结构（属于自调整数据结构（self-adjusting data structure）。）。nAVL树使得搜索树保持高度平衡，让叶结点只出树使得搜索树保持高度平衡，让叶结点只出现在最低的一层或两层上，从而提高其搜索效率。现在最低的一层或两层上，从而提高其搜索效率。n伸展树是另一种提高搜索效率的方法，其思路是：伸展树是另一种提高搜索效率的方法，其思路是：1.
28、单一旋转：单一旋转：将经常访问的结点最终上移到靠将经常访问的结点最终上移到靠近根的地方，使以后的访问更快。近根的地方，使以后的访问更快。本讲稿第四十页，共七十九页2.移动到根部：移动到根部：假设正访问的结点将以很高的概率假设正访问的结点将以很高的概率再次被访问，对它反复进行子女再次被访问，对它反复进行子女父结点旋转，父结点旋转，直到被访问的结点位于根部为止。直到被访问的结点位于根部为止。n伸展树提出了一组改进二叉搜索树性能的一组规则，伸展树提出了一组改进二叉搜索树性能的一组规则，每当执行搜索、插入、删除等操作时，就要依据这每当执行搜索、插入、删除等操作时，就要依据这些规则调整二叉搜索树，从而保
29、证操作的时间代价。些规则调整二叉搜索树，从而保证操作的时间代价。n每当访问（搜索、插入或删除）一个结点每当访问（搜索、插入或删除）一个结点 s 时，时，伸展树就执行一次叫做伸展树就执行一次叫做“展开展开(splaying)”的过程，的过程，将将结点结点 s 移到二叉搜索树的根部移到二叉搜索树的根部。本讲稿第四十一页，共七十九页n就像就像AVL树，一次树，一次“展开展开”由一组旋转组成。由一组旋转组成。n旋转有三种类型：旋转有三种类型：单旋转单旋转、一字形旋转一字形旋转和和之字之字形旋转形旋转。n一次旋转的目的是通过调整一次旋转的目的是通过调整结点结点 s 与它的与它的父结点父结点 p 和和祖父
30、结点祖父结点 g 之间位置，把它上移到树的更高之间位置，把它上移到树的更高层。层。1.被访问结点被访问结点 s 的父结点的父结点 p 是是根结点根结点。此时执行。此时执行单旋转单旋转。在保持二叉搜索树特性的情况下，结点。在保持二叉搜索树特性的情况下，结点 s 成为新的根，原来的根成为新的根，原来的根 p 成为它的子女结点。成为它的子女结点。本讲稿第四十二页，共七十九页2.同构形状（同构形状（homogeneous configuration）。结。结点点 s 是其父结点是其父结点 p 的左子女，结点的左子女，结点 p 又是其父结点又是其父结点 g 的左子女的左子女()。或者结点。或者结点 s
31、是其父结点是其父结点 p 的右子的右子女，结点女，结点 p 又是其父结点又是其父结点g 的右子女的右子女()。此时。此时执行执行一字形旋转一字形旋转(zigzig rotation):p s s p右单旋转本讲稿第四十三页，共七十九页n异构的形状（异构的形状（heterogeneous configuration）。结点。结点 s 是其父结点是其父结点 p 的左子女，结点的左子女，结点 p 又是其父结点又是其父结点 g 的右子女的右子女()。或结点。或结点 s 是其父结点是其父结点 p 的右子女，结的右子女，结点点 p 又是其父结点又是其父结点 g 的左子女的左子女()。此时执行。此时执行之字
32、形之字形旋转旋转(zigzag rotation)。pg s pg s pg s 右单旋转右单旋转本讲稿第四十四页，共七十九页n因为刚访问的因为刚访问的结点结点 s 与其父结点与其父结点 p 和祖父结点和祖父结点g 形形成折线成折线，需要做与，需要做与AVL树一样的树一样的双旋转双旋转，首先围绕，首先围绕 s 旋转旋转 p，再围绕，再围绕 s 旋转旋转 g，把结点，把结点 s上升到祖父结上升到祖父结点的位置，并保持二叉搜索树的特性。点的位置，并保持二叉搜索树的特性。pg s pg s sg p 左单旋转右单旋转本讲稿第四十五页，共七十九页将刚访问的结点将刚访问的结点s s上移到树根部的算法上移
33、到树根部的算法 splaying(g,p,s)/g 是 p 的父结点，p 是 s 的父结点/算法将s移到根结点位置 while(s 不是树的根结点不是树的根结点)if(s 的父结点是根结点的父结点是根结点)进行单旋转进行单旋转,将将 s 调整为根结点调整为根结点 else if(s 与它的前驱与它的前驱 p,g 是同构形状是同构形状)进行一字形双旋转，将进行一字形双旋转，将 s 上移上移 else/s 与它的前驱与它的前驱 p,g 是异构形状是异构形状 进行之字形双旋转，将进行之字形双旋转，将 s 上移上移;本讲稿第四十六页，共七十九页伸展树的性能分析伸展树的性能分析n之字形旋转之字形旋转使得
34、树结构趋向于平衡化，结果常常使使得树结构趋向于平衡化，结果常常使树结构的高度减少树结构的高度减少1。而。而一字形旋转一字形旋转一般不会降低一般不会降低树结构的高度，它只是把刚访问的结点向根结树结构的高度，它只是把刚访问的结点向根结点上移。点上移。n伸展树不要求每一个操作都是高效的，对于一个伸展树不要求每一个操作都是高效的，对于一个有有 n 个结点的树，执行个结点的树，执行 m 次操作时可能一次插入次操作时可能一次插入或搜索操作需要花费或搜索操作需要花费O(n)时间。时间。n例如，对于一个有例如，对于一个有 n 个结点的单支树，访问最底个结点的单支树，访问最底层的结点，需要时间即为层的结点，需要
35、时间即为O(n)。本讲稿第四十七页，共七十九页n当当mn时，所有时，所有m个操作总共需要个操作总共需要O(mlog2n)时间，时间，从而使每次访问操作的所花费的平均时间达到从而使每次访问操作的所花费的平均时间达到O(log2n)，从整体上保持较高的时间性能。，从整体上保持较高的时间性能。n下面的实例描述了伸展树如何通过下面的实例描述了伸展树如何通过“展开展开”实现实现自调整。首先在伸展树中搜索自调整。首先在伸展树中搜索70，搜索过程与二，搜索过程与二叉搜索树完全一样，一旦搜索成功，就执行叉搜索树完全一样，一旦搜索成功，就执行“展开展开”过程将该结点上移到根结点位置。过程将该结点上移到根结点位置
36、。n伸展树的插入操作与二叉搜索树相同，但结点一经插伸展树的插入操作与二叉搜索树相同，但结点一经插入之后立即展开到根结点。入之后立即展开到根结点。本讲稿第四十八页，共七十九页608030201070409050608030201070409050608030201070409050608030201070409050zigzig双旋转双旋转zigzag双旋转双旋转左单旋转左单旋转70调整完调整完本讲稿第四十九页，共七十九页n从伸展树中删除一个结点的操作也与二叉搜索树相从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删结点的父结点展开到根结点。同，但需要把被删结点的父结点展开到根结点。n
37、伸展树与伸展树与AVL树在操作上稍有不同。伸展树的调整树在操作上稍有不同。伸展树的调整与结点被访问（包括搜索、插入、删除）的频率有与结点被访问（包括搜索、插入、删除）的频率有关，能够进行更合理的调整。而关，能够进行更合理的调整。而AVL树的结构调整树的结构调整只与插入、删除的顺序有关，与访问的频率无关。只与插入、删除的顺序有关，与访问的频率无关。本讲稿第五十页，共七十九页红黑树（红黑树（Red-Black TreeRed-Black Tree）n红黑树是一棵二叉搜索树：树中的每一个结点的红黑树是一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为颜色不是黑色就是红色。可
38、以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。其特一棵扩充二叉树，用外部结点表示空指针。其特性描述如下：性描述如下：特性特性1：根结点和所有外部结点的颜色是根结点和所有外部结点的颜色是黑色黑色。特性特性2：从根结点到外部结点的途中没有连续两从根结点到外部结点的途中没有连续两个结点的颜色是个结点的颜色是红色红色。特性特性3：所有从根到外部结点的路径上都有相所有从根到外部结点的路径上都有相同数目的同数目的黑色结点黑色结点。本讲稿第五十一页，共七十九页n从红黑树中任一结点从红黑树中任一结点 x 出发出发(不包括结点不包括结点 x)，到达，到达一个外部结点的任一路径上的黑结点个数叫做结点一个
39、外部结点的任一路径上的黑结点个数叫做结点 x 的黑高度，称为结点的阶的黑高度，称为结点的阶(rank)，记作，记作 bh(x)。红。红黑树的黑高度定义为其根结点的黑高度。黑树的黑高度定义为其根结点的黑高度。501030204060702050红色结点红色结点黑色结点黑色结点外部结点外部结点本讲稿第五十二页，共七十九页n另一种等价的定义是看结点指针的颜色。另一种等价的定义是看结点指针的颜色。n从父结点到黑色子女结点的指针为黑色的，从从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。父结点到红色子女结点的指针为红色的。50103020406070本讲稿第五十三页，共七十九
40、页特性特性1：从内部结点指向外部结点的指针是黑色从内部结点指向外部结点的指针是黑色的。的。特性特性2：从根结点到外部结点的途中没有两从根结点到外部结点的途中没有两个连续的红色指针。个连续的红色指针。特性特性3：所有根到外部结点的路径上都有相同数所有根到外部结点的路径上都有相同数目的黑色指针。目的黑色指针。n如果知道指针的颜色，就能推断结点的颜色，反如果知道指针的颜色，就能推断结点的颜色，反之亦然。之亦然。n设从根到外部结点的路径长度设从根到外部结点的路径长度(Path Length,PL)为该路径上指针的个数，为该路径上指针的个数，本讲稿第五十四页，共七十九页n结论结论1 如果如果P与与Q是红
41、黑树中的两条从根到外部结是红黑树中的两条从根到外部结点的路径，则有：点的路径，则有：PL(P)2PL(Q)证明：证明：考查任意一棵红黑树。假设根结点的黑高考查任意一棵红黑树。假设根结点的黑高度度bh(root)=r。由特性。由特性1可知，每条从根结点到外可知，每条从根结点到外部结点的路径中最后一个指针为黑色；从特性部结点的路径中最后一个指针为黑色；从特性2可知，可知，不存在有连续两个红色指针的路径。因此，每不存在有连续两个红色指针的路径。因此，每个红色指针后面都会跟随一个黑色指针，每条个红色指针后面都会跟随一个黑色指针，每条从根到外部结点的路径上都有从根到外部结点的路径上都有r2r个指针，综上
42、个指针，综上所述有所述有 PL(P)2PL(Q)。本讲稿第五十五页，共七十九页n如上图，从根到如上图，从根到 40 左下的外部结点的路径长度左下的外部结点的路径长度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 是根结点的黑高度，是根结点
43、的黑高度，则以下关系式成立：则以下关系式成立：(1)h2r(2)n2r-1(3)h2log2(n+1)证明：证明：(1)从结论从结论1的证明可知，从根到任一外部结点的的证明可知，从根到任一外部结点的路径长度不超过路径长度不超过2r，同时从树的定义可知，树的高，同时从树的定义可知，树的高度即为根结点的高度，等于从根到离根最远的外部结度即为根结点的高度，等于从根到离根最远的外部结点的路径的长度，有点的路径的长度，有h2r。本讲稿第五十七页，共七十九页(2)因为红黑树的黑高度为因为红黑树的黑高度为r，则从树的第，则从树的第 1 层到第层到第 r 层没有外部结点，在这些层中有层没有外部结点，在这些层中
44、有2r-1个内部结点，即个内部结点，即内部结点的总数至少为内部结点的总数至少为2r-1。(3)由由(2)可得可得rlog2(n+1)，结合，结合(1)，有，有h2log2(n+1)。n由于红黑树的高度最大为由于红黑树的高度最大为2log2(n+1)，所以搜索、，所以搜索、插入、删除操作的时间复杂性为插入、删除操作的时间复杂性为O(log2n)。注意，。注意，最差情况下的红黑树的高度大于最差情况下具有相同最差情况下的红黑树的高度大于最差情况下具有相同结点个数的结点个数的AVL树的高度（近似于树的高度（近似于1.44*log2(n+2)）。）。本讲稿第五十八页，共七十九页红黑树的搜索红黑树的搜索
45、n由于每一棵红黑树都是二叉搜索树，可以使用由于每一棵红黑树都是二叉搜索树，可以使用二叉搜索树的算法进行搜索。在搜索过程中不二叉搜索树的算法进行搜索。在搜索过程中不需使用颜色信息。需使用颜色信息。n对普通二叉搜索树进行搜索的时间复杂性为对普通二叉搜索树进行搜索的时间复杂性为O(h)，对于红黑树则为，对于红黑树则为O(log2n)。因为在搜索二叉。因为在搜索二叉搜索树、搜索树、AVL树和红黑树时使用了相同算法。树和红黑树时使用了相同算法。在最差情况下在最差情况下AVL树的高度最小，因此，在那些树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下以搜索操作为主的应用程序中，最差情况下AV
46、L树树能获得最优时间复杂性。能获得最优时间复杂性。本讲稿第五十九页，共七十九页红黑树的插入红黑树的插入 n首先使用二叉搜索树的插入算法将一个元素首先使用二叉搜索树的插入算法将一个元素插入到红黑树中，该元素将作为新的叶结点插入到红黑树中，该元素将作为新的叶结点插入。在插入过程中需要为新元素染色。插入。在插入过程中需要为新元素染色。1.如果插入前是空树，则那么新元素将成为根结如果插入前是空树，则那么新元素将成为根结点，根据特征点，根据特征1，根结点必须染成黑色。，根结点必须染成黑色。本讲稿第六十页，共七十九页2.如果插入前树非空，若新结点被染成黑色，如果插入前树非空，若新结点被染成黑色，将违反红黑
47、树的特性将违反红黑树的特性3，所有从根到外部结点所有从根到外部结点的路径上的黑色结点个数不等的路径上的黑色结点个数不等。因此，新插入。因此，新插入的结点将染成红色，但这又可能违反红黑树的的结点将染成红色，但这又可能违反红黑树的特性特性2，出现连续两个红色结点，因此需要重新，出现连续两个红色结点，因此需要重新平衡。平衡。guuL插入本讲稿第六十一页，共七十九页n设新插入的结点为设新插入的结点为u，它的父结点和祖父结点分别，它的父结点和祖父结点分别是是pu和和gu，现在来考查不平衡的类型。若，现在来考查不平衡的类型。若pu是是黑色结点，则特性黑色结点，则特性2没有破坏，结束重新平衡的没有破坏，结束
48、重新平衡的过程。若过程。若pu是红色结点，则出现连续两个红色结是红色结点，则出现连续两个红色结点的情形，这时还要考查点的情形，这时还要考查pu的兄弟结点。的兄弟结点。插入puguugr本讲稿第六十二页，共七十九页1)如果如果pu的兄弟结点的兄弟结点gr是红色结点，此时结点是红色结点，此时结点pu的父结点的父结点gu是黑色结点，它有两个红色子女是黑色结点，它有两个红色子女结点。交换结点结点。交换结点gu和它的子女结点的颜色，将和它的子女结点的颜色，将可能破坏红黑树特性可能破坏红黑树特性2的红色结点上移。的红色结点上移。puguugrpuguugruLuRpuRgrLgrRuLuRpuRgrLgr
49、R本讲稿第六十三页，共七十九页2)如果如果pu的兄弟结点的兄弟结点gr是黑色结点，此时又有两是黑色结点，此时又有两种情况。种情况。a)u是是pu的左子女，的左子女，pu是是gu的左子女。在这的左子女。在这种情况下只要做一次右单旋转，交换一下种情况下只要做一次右单旋转，交换一下pu和和gu的颜色，就可恢复红黑树的特性，的颜色，就可恢复红黑树的特性，并结束重新平衡过程。并结束重新平衡过程。pugugrupugugruuLuRpuRgrLgrRuLuRpuRgrLgrR本讲稿第六十四页，共七十九页b)u是是pu的右子女，的右子女，pu是是gu的左子女。在这的左子女。在这种情况下做一次先左后右的双旋转
50、，再交种情况下做一次先左后右的双旋转，再交换一下换一下u与与gu的颜色，就可恢复红黑树的特性，的颜色，就可恢复红黑树的特性，结束重新平衡过程。结束重新平衡过程。puL gupuugrgrL grR uRuLgupuugrgrL grR uRuLpuL 本讲稿第六十五页，共七十九页n针对上述两种情况，还有镜像情况，即针对上述两种情况，还有镜像情况，即pu是是gu的右的右子女时，当子女时，当u是是pu的右子女则做左单旋转，当的右子女则做左单旋转，当u是是pu的左子女则做先右后左的双旋转。的左子女则做先右后左的双旋转。n红黑树的删除算法与二叉搜索树的删除算法类红黑树的删除算法与二叉搜索树的删除算法类