高度平衡的二叉树优质精选课件

高度平衡的二叉树高度平衡的二叉树1

二叉搜索树性能分析对于有n个关键码的集合，其关键码有n!种不同排列，可构成不同二叉搜索树有

(棵)

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

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

{a1,a2,a3}=

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

○表示内部结点，包含了关键码集合中的某一个关键码；□表示外部结点，代表各关键码间隔中的不在关键码集合中的关键码。在每两个外部结点间必存在一个内部结点。一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p[i]与搜索该结点时所需的关键码比较次数c[i](=l[i],即结点所在层次)乘积之和：在判定树中6设各关键码的搜索概率相等：p[i]=1/n搜索不成功的平均搜索长度ASLunsucc为树中所有外部结点上搜索概率q[j]与到达外部结点所需关键码比较次数c'[j](=l'[j])乘积之和：设外部结点搜索概率相等：q[j]=1/(n+1)：设各关键码的搜索概率相等：p[i]=1/n7设树中所有内、外部结点的搜索概率都相等：

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):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)相等搜索概率的情形设树中所有内、外部结点的搜索概率都相等：(1)相等搜索概率8

图(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)的情形所得的平均搜索长度最小。 图(e):ASLsucc=1/3*1+1/3*3+19设二叉搜索树中所有内、外部结点的搜索概率互不相等。

p[1]=0.5,p[2]=0.1,p[3]=0.05

q[0]=0.15,q[1]=0.1,q[2]=0.05,q[3]=0.05分别计算各个可能的扩充二叉搜索树的搜索性能，判断哪些扩充二叉搜索树的平均搜索长度最小。(2)不相等搜索概率的情形设二叉搜索树中所有内、外部结点的搜索概率互不相等。

10doiftodoiftoq0=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，

ASLunsucc=(0.15+0.1+0.05+0.05)*2=0.7。doiftodoiftoq0=0.15q1=0.1p1=0.11doifto

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=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.doiftoq0=q1=0.1p1=0.5q2=0.0512由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小，因此，图(c)和图(e)的情形是最优二叉搜索树。doiftoq0=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;由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小13一般把平均搜索长度达到最小的扩充的二叉搜索树称作最优二叉搜索树。等概率条件下，最优二叉搜索树的最短内部路径长度与最短外部路径长度,课本383页:高度平衡的二叉树优质精选课件14☞一、什么是平衡二叉树二、失衡二叉排序树的分析与调整

平衡二叉树☞一、什么是平衡二叉树平衡二叉树15平衡二叉树又称为AVL树。

一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

①

左子树与右子树的高度之差的绝对值小于等于1；②左子树和右子树也是平衡二叉排序树。平衡二叉树又称为AVL树。16结论2设h是一棵红黑树的高度(不包括外部结点)，n是树中内部结点的个数，r是根结点的黑高度，则以下关系式成立：当m≥n时，所有m个操作总共需要O(mlog2n)时间，从而使每次访问操作的所花费的平均时间达到O(log2n)，从整体上保持较高的时间性能。28-7(ctd.由特性1‘可知，每条从根结点到外部结点的路径中最后一个指针为黑色；(1)h≤2r如果插入前是空树，则那么新元素将成为根结点，根据特征1，根结点必须染成黑色。设新插入的结点为u，它的父结点和祖父结点分别是pu和gu，现在来考查不平衡的类型。0.红黑树的黑高度定义为其根结点的黑高度。(2)n≥2r-1可能的二叉搜索树如下所示。一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p[i]与搜索该结点时所需的关键码比较次数c[i](=l[i],即结点所在层次)乘积之和：{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}p[i]=1/3,1≤i≤3,q[j]=1/4,0≤j≤3特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。伸展树、AVL树、并查集的用双亲表示的树，都属于自调整数据结构（self-adjustingdatastructure）。(3)由(2)可得r≤log2(n+1)，结合(1)，有根据红黑树的特性2，r一定是黑色结点。从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性3，所有从根到外部结点的路径上的黑色结点个数不等。例：平衡二叉树40247053452860引入平衡二叉树的目的是为了提高查找效率，使其平均查找长度为O(log2n)。402470532860结论2设h是一棵红黑树的高度(不包括外部结点)，17根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0，或1。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子，如2、-2。为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子。根据平衡二叉树的定义，平衡二叉树上所有结点的平1840247053452860402470532860例：下图对平衡二叉树和失去平衡的二叉排序树分别标注了平衡因子。01-1-100-110-1-20-140247053452860402470532860例：下图19一、什么是平衡二叉树

☞二、失衡二叉排序树的分析与调整

平衡二叉树一、什么是平衡二叉树平衡二叉树20如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：

LL平衡旋转

RR平衡旋转

LR平衡旋转

RL平衡旋转如果在一棵AVL树中插入一个新结点，就有可能造成21若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）1）LL平衡旋转：ABCABC若在A的左子树的左子树上插入结点，使A的平衡因子从1增22右单旋转(RotateRight)hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABD 在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到-2，造成了不平衡。 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。 以结点B为旋转轴，将结点A顺时针旋转。h000-1-1-2右单旋转(RotateRight)hhhACEBD(a)23

左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：1、LL情况：（LL：表示新插入结点在危机结点的

左子树的左子树上）AB+1h-10+2+1hh-1h-1LL改组BLBRARBA0h0h-1h-1BLBRAR危机结点改组前：高度为h+1中序序列：ABBLBRAR改组后：高度为h+1中序序列：ABBLBRAR注意：改组后平衡度为0AB左改组（新插入结点出现在危机结点的左子树上进行的调整）AB24若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-125左单旋转(RotateLeft)hhhACEBD(a)(b)(c)hhh+1BACEDhhh+1CEABD 如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。 沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。 以结点C为旋转轴，让结点A反时针旋转。+1+20+100左单旋转(RotateLeft)hhhACEBD(a)26若pu是红色结点，则出现连续两个红色结点的情形，这时还要考查pu的兄弟结点。在保持二叉搜索树特性的情况下，结点s成为新的根，原来的根p成为它的子女结点。因为在搜索二叉搜索树、AVL树和红黑树时使用了相同算法。课本397页图10.平衡二叉树又称为AVL树。针对上述两种情况，还有镜像情况，即pu是gu的右子女时，当u是pu的右子女则做左单旋转，当u是pu的左子女则做先右后左的双旋转。由于每一棵红黑树都是二叉搜索树，可以使用二叉搜索树的算法进行搜索。假设根结点的黑高度bh(root)=r。为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。28-7(ctd.28-2cdestroysitsbalance;torestorethebalance,performboth

(b)arightrotationand(c)aleftrotation.splaying(g,p,s){二、失衡二叉排序树的分析与调整在这种情况下只要做一次右单旋转，交换一下pu和gu的颜色，就可恢复红黑树的特性，并结束重新平衡过程。伸展树、AVL树、并查集的用双亲表示的树，都属于自调整数据结构（self-adjustingdatastructure）。else//s与它的前驱p,g是异构形状{2,1,3}假设根结点的黑高度bh(root)=r。由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小，因此，图(c)和图(e)的情形是最优二叉搜索树。28-5afteradditionsthatmaintainitsbalance;(b)afteranadditionthatdestroysthebalance…continued→若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：若pu是红色结点，则出现连续两个红色结点的情形，这时还要考查272、LR情况：（LR：表示新插入结点在危机结点的

左子树的右子树上）情况A：AB+1h-10+2-1h-1LR改组BLAR危机结点改组前：高度为h+1中序序列：注意：改组后平衡度为0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：高度为h+1中序序列：ABBLARCCLCRA2、LR情况：（LR：表示新插入结点在危机结点的AB+1h28DoubleRotationsFig.28-7(a)TheAVLtreeinFig.28-5afteradditionsthatmaintainitsbalance;(b)afteranadditionthatdestroysthebalance…continued→

DoubleRotationsFig.28-7(a)29DoubleRotationsFig.28-7(ctd.)(c)afteraleftrotation;

(d)afterarightrotation.DoubleRotationsFig.28-7(ctd30若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC这种调整规则可以保证二叉排序树的次序不变若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至31综上所述，在一个平衡二叉排序树上插入一个新结点S时，主要包括以下三步：

(1)查找应插位置，同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。

(2)插入新结点S，并修改从A到S路径上各结点的平衡因子。

(3)根据A、B的平衡因子，判断是否失衡以及失衡类型，并做相应处理。综上所述，在一个平衡二叉排序树上插入一个新结点S时，32DoubleRotationsFig.28-5(a)Adding70tothetreeinFig.28-2cdestroysitsbalance;torestorethebalance,performboth

(b)arightrotationand(c)aleftrotation.DoubleRotationsFig.28-5(a)33013037024例：请将下面序列构成一棵平衡二叉排序树：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053000例：请将下面序列构成一棵平衡二叉排序树：

34例如，输入关键码序列为{16,3,7,11,9,26,18,14,15}，插入和调整过程如下。160163-10左右双旋731600073110-1116右单旋37169000111163701-273161190-1-223711269160112例如，输入关键码序列为{16,3,7,11,9,35右左双旋0左单旋181600732611900031609171126183-1-17161426911127390182611-1161右左双旋0左单旋181600732611900031609136在最差情况下AVL树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下AVL树能获得最优时间复杂性。可以将结点u视为具有双重黑色的结点，这样任意包含结点u的路径上的黑高度仍保持删除前的值，就能恢复红黑树的特性。结点w是红色结点，作一次右单旋转，将w、g染成黑色，v染成红色，就可消除结点u的双重黑色，恢复红黑树的性质。交换结点gu和它的子女结点的颜色，将可能破坏红黑树特性2的红色结点上移。当m≥n时，所有m个操作总共需要O(mlog2n)时间，从而使每次访问操作的所花费的平均时间达到O(log2n)，从整体上保持较高的时间性能。伸展树与AVL树在操作上稍有不同。一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p[i]与搜索该结点时所需的关键码比较次数c[i](=l[i],即结点所在层次)乘积之和：=0.改组后：高度为h+1这样的判定树即为扩充的二叉搜索树。结点s是其父结点p的左子女，结点p又是其父结点g的左子女(／)。grLgrR对于有n个关键码的集合，其关键码有n!种不同排列，可构成不同二叉搜索树有(a)(b)(c)设u是被删结点p的唯一子女结点。☞二、失衡二叉排序树的分析与调整☞二、失衡二叉排序树的分析与调整外结点表示失败结点，内结点表示搜索树中已有的数据。1,p[3]=0.因为在搜索二叉搜索树、AVL树和红黑树时使用了相同算法。1518231816-2左右双旋73000117149-1161501112626141-29从空树开始的建树过程在最差情况下AVL树的高度最小，因此，在那些以搜索操作为主的37各种搜索结构的比较课本397页图10.14各种搜索结构的比较课本397页图10.1438作业1、设有关键码序列{55，31，11，37，46，73，63，02，07}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。作业1、设有关键码序列{55，31，11，37，46，73，39伸展树（SplayingTree）

伸展树、AVL树、并查集的用双亲表示的树，都属于自调整数据结构（self-adjustingdatastructure）。AVL树使得搜索树保持高度平衡，让叶结点只出现在最低的一层或两层上，从而提高其搜索效率。伸展树是另一种提高搜索效率的方法，其思路是：单一旋转：将经常访问的结点最终上移到靠近根的地方，使以后的访问更快。伸展树（SplayingTree）伸展树、AVL树、并查40移动到根部：假设正访问的结点将以很高的概率再次被访问，对它反复进行子女―父结点旋转，直到被访问的结点位于根部为止。伸展树提出了一组改进二叉搜索树性能的一组规则，每当执行搜索、插入、删除等操作时，就要依据这些规则调整二叉搜索树，从而保证操作的时间代价。每当访问（搜索、插入或删除）一个结点s时，伸展树就执行一次叫做“展开(splaying)”的过程，将结点s移到二叉搜索树的根部。

移动到根部：假设正访问的结点将以很高的概率再次被访问，对它反41就像AVL树，一次“展开”由一组旋转组成。旋转有三种类型：单旋转、一字形旋转和之字形旋转。一次旋转的目的是通过调整结点s

与它的父结点p

和祖父结点g

之间位置，把它上移到树的更高层。被访问结点s

的父结点p

是根结点。此时执行单旋转。在保持二叉搜索树特性的情况下，结点

s成为新的根，原来的根p

成为它的子女结点。

就像AVL树，一次“展开”由一组旋转组成。42同构形状（homogeneousconfiguration）。结点s

是其父结点p

的左子女，结点p

又是其父结点g

的左子女(／)。或者结点s

是其父结点p

的右子女，结点p

又是其父结点g的右子女(＼)。此时执行一字形旋转(zigzigrotation):

pssp右单旋转同构形状（homogeneousconfiguration43异构的形状（heterogeneousconfiguration）。结点s

是其父结点p

的左子女，结点p又是其父结点g

的右子女(＞)。或结点s

是其父结点

p

的右子女，结点p

又是其父结点g

的左子女(＜)。此时执行之字形旋转(zigzagrotation)。

pgspgspgs右单旋转右单旋转异构的形状（heterogeneousconfigurat44因为刚访问的结点s与其父结点p

和祖父结点g

形成折线，需要做与AVL树一样的双旋转，首先围绕s

旋转p，再围绕s旋转g，把结点s上升到祖父结点的位置，并保持二叉搜索树的特性。

pgspgssgp左单旋转右单旋转因为刚访问的结点s与其父结点p和祖父结点g形成折线45将刚访问的结点s上移到树根部的算法

splaying(g,p,s){//g

是p

的父结点，p是s

的父结点//算法将s移到根结点位置

while(s

不是树的根结点)if(s的父结点是根结点)

进行单旋转,将

s

调整为根结点

elseif(s与它的前驱

p,g是同构形状)

进行一字形双旋转，将

s

上移

else//s

与它的前驱

p,g是异构形状

进行之字形双旋转，将

s

上移};将刚访问的结点s上移到树根部的算法splaying(g,46交换结点gu和它的子女结点的颜色，将可能破坏红黑树特性2的红色结点上移。每当访问（搜索、插入或删除）一个结点s时，伸展树就执行一次叫做“展开(splaying)”的过程，将结点s移到二叉搜索树的根部。为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。else//s与它的前驱p,g是异构形状特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。设新插入的结点为u，它的父结点和祖父结点分别是pu和gu，现在来考查不平衡的类型。例如，输入关键码序列为{16,3,7,11,9,26,18,14,15}，插入和调整过程如下。若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。44*log2(n+2)）。在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。图(c):ASLsucc=1/3*1+1/3*2+1/3*3=6/3,设新插入的结点为u，它的父结点和祖父结点分别是pu和gu，现在来考查不平衡的类型。DoubleRotations0.图(d):ASLsucc=1/3*2+1/3*3+1/3*1=6/3,☞二、失衡二叉排序树的分析与调整如果结点u是红色结点，可以把u染成黑色，从而恢复红黑树的特性。44*log2(n+2)）。异构的形状（heterogeneousconfiguration）。课本397页图10.伸展树的性能分析之字形旋转使得树结构趋向于平衡化，结果常常使树结构的高度减少1。而一字形旋转一般不会降低树结构的高度，它只是把刚访问的结点向根结点上移。伸展树不要求每一个操作都是高效的，对于一个有n

个结点的树，执行m

次操作时可能一次插入或搜索操作需要花费O(n)时间。例如，对于一个有n

个结点的单支树，访问最底层的结点，需要时间即为O(n)。交换结点gu和它的子女结点的颜色，将可能破坏红黑树特性2的红47当m≥n时，所有m个操作总共需要O(mlog2n)时间，从而使每次访问操作的所花费的平均时间达到O(log2n)，从整体上保持较高的时间性能。下面的实例描述了伸展树如何通过“展开”实现自调整。首先在伸展树中搜索70，搜索过程与二叉搜索树完全一样，一旦搜索成功，就执行“展开”过程将该结点上移到根结点位置。伸展树的插入操作与二叉搜索树相同，但结点一经插入之后立即展开到根结点。

当m≥n时，所有m个操作总共需要O(mlog2n)时间，从而48608030201070409050608030201070409050608030201070409050608030201070409050zigzig双旋转zigzag双旋转左单旋转70调整完60803020107040905060803020107049从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删结点的父结点展开到根结点。伸展树与AVL树在操作上稍有不同。伸展树的调整与结点被访问（包括搜索、插入、删除）的频率有关，能够进行更合理的调整。而AVL树的结构调整只与插入、删除的顺序有关，与访问的频率无关。从伸展树中删除一个结点的操作也与二叉搜索树相同，但需要把被删50红黑树（Red-BlackTree）

红黑树是一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。其特性描述如下：特性1：根结点和所有外部结点的颜色是黑色。特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。特性3：所有从根到外部结点的路径上都有相同数目的黑色结点。红黑树（Red-BlackTree）红黑树是一棵二叉搜索51从红黑树中任一结点x

出发(不包括结点x)，到达一个外部结点的任一路径上的黑结点个数叫做结点x

的黑高度，称为结点的阶(rank)，记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。501030204060702050红色结点黑色结点外部结点从红黑树中任一结点x出发(不包括结点x)，到达一个外52另一种等价的定义是看结点指针的颜色。从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。50103020406070另一种等价的定义是看结点指针的颜色。50103020406053特性1'：从内部结点指向外部结点的指针是黑色的。特性2'：从根结点到外部结点的途中没有两个连续的红色指针。特性3'：所有根到外部结点的路径上都有相同数目的黑色指针。如果知道指针的颜色，就能推断结点的颜色，反之亦然。设从根到外部结点的路径长度(PathLength,PL)为该路径上指针的个数，特性1'：从内部结点指向外部结点的指针是黑色的。54结论1

如果P与Q是红黑树中的两条从根到外部结点的路径，则有：

PL(P)≤2PL(Q)

证明：考查任意一棵红黑树。假设根结点的黑高度bh(root)=r。由特性1‘可知，每条从根结点到外部结点的路径中最后一个指针为黑色；从特性2’可知，不存在有连续两个红色指针的路径。因此，每个红色指针后面都会跟随一个黑色指针，每条从根到外部结点的路径上都有r～2r个指针，综上所述有PL(P)≤2PL(Q)。结论1如果P与Q是红黑树中的两条从根到外部结点的路径55如上图，从根到40左下的外部结点的路径长度PL(40)=4，从根到70右下的外部结点的路径长度PL(70)=3，因此PL(40)≤PL(70)或者PL(70)≤PL(40)。

50103020406070PL=4,bh=2PL=3,bh=2如上图，从根到40左下的外部结点的路径长度PL(40)56(a)(b)(c)uLuR课本397页图10.1,p[3]=0.中序序列：旋转有三种类型：单旋转、一字形旋转和之字形旋转。这个数字称为结点的平衡因子。就像AVL树，一次“展开”由一组旋转组成。28-2cdestroysitsbalance;torestorethebalance,performboth

(b)arightrotationand(c)aleftrotation.如上图，从根到40左下的外部结点的路径长度PL(40)=4，从根到70右下的外部结点的路径长度PL(70)=3，因此PL(40)≤PL(70)或者PL(70)≤PL(40)。假设根结点的黑高度bh(root)=r。u是pu的右子女，pu是gu的左子女。而一字形旋转一般不会降低树结构的高度，它只是把刚访问的结点向根结点上移。若pu是黑色结点，则特性2没有破坏，结束重新平衡的过程。这样的判定树即为扩充的二叉搜索树。针对上述两种情况，还有镜像情况，即pu是gu的右子女时，当u是pu的右子女则做左单旋转，当u是pu的左子女则做先右后左的双旋转。如果插入前是空树，则那么新元素将成为根结点，根据特征1，根结点必须染成黑色。进行单旋转,将s调整为根结点课本397页图10.每当访问（搜索、插入或删除）一个结点s时，伸展树就执行一次叫做“展开(splaying)”的过程，将结点s移到二叉搜索树的根部。结论2

设h

是一棵红黑树的高度(不包括外部结点)，n

是树中内部结点的个数，r

是根结点的黑高度，则以下关系式成立：

(1)h≤2r

(2)n≥2r-1 (3)h≤2log2(n+1)

证明：

(1)从结论1的证明可知，从根到任一外部结点的路径长度不超过2r，同时从树的定义可知，树的高度即为根结点的高度，等于从根到离根最远的外部结点的路径的长度，有h≤2r。(a)(b57

(2)因为红黑树的黑高度为r，则从树的第1层到第r

层没有外部结点，在这些层中有2r-1个内部结点，即内部结点的总数至少为2r-1。

(3)由(2)可得r≤log2(n+1)，结合(1)，有

h≤2log2(n+1)。由于红黑树的高度最大为2log2(n+1)，所以搜索、插入、删除操作的时间复杂性为O(log2n)。注意，最差情况下的红黑树的高度大于最差情况下具有相同结点个数的AVL树的高度（近似于1.44*log2(n+2)）。 (2)因为红黑树的黑高度为r，则从树的第1层到第r58红黑树的搜索

由于每一棵红黑树都是二叉搜索树，可以使用二叉搜索树的算法进行搜索。在搜索过程中不需使用颜色信息。对普通二叉搜索树进行搜索的时间复杂性为O(h)，对于红黑树则为O(log2n)。因为在搜索二叉搜索树、AVL树和红黑树时使用了相同算法。在最差情况下AVL树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下AVL树能获得最优时间复杂性。

红黑树的搜索由于每一棵红黑树都是二叉搜索树，可以使用二叉搜59红黑树的插入

首先使用二叉搜索树的插入算法将一个元素插入到红黑树中，该元素将作为新的叶结点插入。在插入过程中需要为新元素染色。如果插入前是空树，则那么新元素将成为根结点，根据特征1，根结点必须染成黑色。Ф红黑树的插入首先使用二叉搜索树的插入算法将一个元素插入到红60如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性3，所有从根到外部结点的路径上的黑色结点个数不等。因此，新插入的结点将染成红色，但这又可能违反红黑树的特性2，出现连续两个红色结点，因此需要重新平衡。guuL插入╳如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性3，61设新插入的结点为u，它的父结点和祖父结点分别是pu和gu，现在来考查不平衡的类型。若pu是黑色结点，则特性2没有破坏，结束重新平衡的过程。若pu是红色结点，则出现连续两个红色结点的情形，这时还要考查pu的兄弟结点。插入╳puguugr设新插入的结点为u，它的父结点和祖父结点分别是pu和gu，现621) 如果pu的兄弟结点gr是红色结点，此时结点pu的父结点gu是黑色结点，它有两个红色子女结点。交换结点gu和它的子女结点的颜色，将可能破坏红黑树特性2的红色结点上移。puguugrpuguugruLuRpuRgrLgrRuLuRpuRgrLgrR1) 如果pu的兄弟结点gr是红色结点，此时结点pu的父结点632) 如果pu的兄弟结点gr是黑色结点，此时又有两种情况。

u是pu的左子女，pu是gu的左子女。在这种情况下只要做一次右单旋转，交换一下pu和gu的颜色，就可恢复红黑树的特性，并结束重新平衡过程。pugugrupugugruuLuRpuRgrLgrRuLuRpuRgrLgrR2) 如果pu的兄弟结点gr是黑色结点，此时又有两种情况。p64

u是pu的右子女，pu是gu的左子女。在这种情况下做一次先左后右的双旋转，再交换一下u与gu的颜色，就可恢复红黑树的特性，结束重新平衡过程。

puL

gupuugrgrLgrR

uRuLgupuugrgrLgrR

uRuLpuL

u是pu的右子女，pu是gu的左子女。在这种情况下做一次先65针对上述两种情况，还有镜像情况，即pu是gu的右子女时，当u是pu的右子女则做左单旋转，当u是pu的左子女则做先右后左的双旋转。红黑树的删除算法与二叉搜索树的删除算法类似，不同之处在于，在红黑树中执行一次二叉搜索树的删除运算，可能会破坏红黑树的特性，需要重新平衡。红黑树的删除针对上述两种情况，还有镜像情况，即pu是gu的右子女时，当u66在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。如果被删结点p是红色的，删去它树中各结点的黑高度都没有改变，也不会出现连续两个红色结点，红黑树的特性仍然保持，不需执行重新平衡过程。pvguuLuR

vRvL

vguuLuR

vRvL

直接删除在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。pv67如果被删结点p是黑色的，一旦删去它，红黑树将不满足特性3的要求，因为在这条路径上黑色结点少了一个，从根到外部结点的黑高度将会降低。可以将结点u视为具有双重黑色的结点，这样任意包含结点u的路径上的黑高度仍保持删除前的值，就能恢复红黑树的特性。问题是在红黑树的定义中没有包括双重黑色的结点，因此必须通过旋转变换和改变结点的颜色，消除双重黑色结点，恢复红黑树的特性。如果被删结点p是黑色的，一旦删去它，红黑树将不满足特性3的要68设u是被删结点p的唯一子女结点。如果结点u是红色结点，可以把u染成黑色，从而恢复红黑树的特性。

pugvugv设u是被删结点p的唯一子女结点。如果结点u是红色结点，可以把69如果被删结点p是黑色结点，它的唯一的子女结点u也是黑色结点，可先将p从链中摘下，将结点u链到其祖父g的下面。假设结点u成为结点g的右子女，v是u的左兄弟。根据v的颜色，分以下两种情况：结点v是黑色结点，若设结点v的左子女结点为w。根据w的颜色分别讨论：

如果被删结点p是黑色结点，它的唯一的子女结点u也是黑色结点，70结点w是红色结点，作一次右单旋转，将w、g染成黑色，v染成红色，就可消除结点u的双重黑色，恢复红黑树的性质。结点w是黑色结点，还要看结点w的右兄弟结点r。根据r的颜色，分两种情况：gvuvRuLuR

wRwLwgvvRuuLuR

wRwLw结点w是红色结点，作一次右单旋转，将w、g染成黑色，v染成红71结点r是红色结点，可通过一次先左后右的双旋转，并将g染成黑色，就可消除u的双重黑色，恢复红黑树的特性。结点r是黑色结点，这时还要看结点g的颜色。如果g是红色结点，只要交换结uLuR

wRwLgvuwrrRrLgvuwruLuR

rRrLwRwL结点r是红色结点，可通过一次先左后右的双旋转，并将g染成黑色72

点g和其子女结点v的颜色就能恢复红黑树的特性。

如果g是黑色结点，可做一次右单旋转，将结点v上升并染成双重黑色，从而消除结点u的双重黑色，将双重黑色结点向根gvuuLuR

wRwLwrrRrLgvuuLuR

wRwLwrrRrL 点g和其子女结点v的颜色就能恢复红黑树的特性。gvuuL73

的方向转移。结点v是红色结点。考查v的右子女结点r。根据红黑树的特性2，r一定是黑色结点。再看结点r的左子女结点s。根据s的颜色，可以分为两种情况讨论。

gvuuLuR

wRwLwrrRrLgvuuLuR

wRwLwrrRrL 的方向转移。gvuuLuRwRwLw741) 结点s是红色结点。通过一次先左后右双旋转，让r上升，使包含u的路径的黑高度增1，从而消除结点u的双重黑色，恢复红黑树的特性。

gvuuLuR

sRvLsrrRsLgvuuLuR

sRvLsrrRsL1) 结点s是红色结点。通过一次先左后右双旋转，让r上升，使752) 结点s是黑色结点，再看结点s的右兄弟结点t。根据结点t的颜色又可分为两种情况进行讨论。若结点t为红色结点，先以t为旋转轴，做左单旋转，以t替补r的位置；然后再以t为旋转轴，做一次先左后右的双旋转，可消除结点u的双重黑色，恢复红黑树特性。

2) 结点s是黑色结点，再看结点s的右兄弟结点t。根据结点t76针对上述两种情况，还有镜像情况，即pu是gu的右子女时，当u是pu的右子女则做左单旋转，当u是pu的左子女则做先右后左的双旋转。我们称调整平衡过程为平衡旋转。else//s与它的前驱p,g是异构形状ASLunsucc=1/4*1+1/4*3*2+1/4*2=9/4。(a)(b)(c)u是pu的右子女，pu是gu的左子女。在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到-2，造成了不平衡。一次旋转的目的是通过调整结点s与它的父结点p和祖父结点g之间位置，把它上移到树的更高层。(3)由(2)可得r≤log2(n+1)，结合(1)，有ASLunsucc=1/4*2*4=8/4。根据r的颜色，分两种情况：1,p[3]=0.28-5(a)Adding70tothetreeinFig.h≤2log2(n+1)。伸展树的调整与结点被访问（包括搜索、插入、删除）的频率有关，能够进行更合理的调整。特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。课本397页图10.为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。特性1'：从内部结点指向外部结点的指针是黑色的。首先在伸展树中搜索70，搜索过程与二叉搜索树完全一样，一旦搜索成功，就执行“展开”过程将该结点上移到根结点位置。gvuuLuR

sRvLsrsLtRttLgvuuLuR

sRvLsrsLtRttLgvuuLuR

sRvLsrsLtRttL针对上述两种情况，还有镜像情况，即pu是gu的右子女时，当u77若结点t为黑色结点，以v为旋转轴，做一次右单旋转，并改变v和r的颜色，即可消除结点u的双重黑色，恢复红黑树的特色。gvuuLuR

sRvLsrsLtRttLgvuuLuR

sRvLsrsLtRttL若结点t为黑色结点，以v为旋转轴，做一次右单旋转，并改变v和78当删除结点p之后结点u成为结点g的左子女，这种情况与上面讨论的情况是镜像的，只要左、右指针互换就可以了。

当删除结点p之后结点u成为结点g的左子女，这种情况与上面讨论79高度平衡的二叉树高度平衡的二叉树80

二叉搜索树性能分析对于有n个关键码的集合，其关键码有n!种不同排列，可构成不同二叉搜索树有

(棵)

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

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

{a1,a2,a3}=

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

○表示内部结点，包含了关键码集合中的某一个关键码；□表示外部结点，代表各关键码间隔中的不在关键码集合中的关键码。在每两个外部结点间必存在一个内部结点。一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p[i]与搜索该结点时所需的关键码比较次数c[i](=l[i],即结点所在层次)乘积之和：在判定树中85设各关键码的搜索概率相等：p[i]=1/n搜索不成功的平均搜索长度ASLunsucc为树中所有外部结点上搜索概率q[j]与到达外部结点所需关键码比较次数c'[j](=l'[j])乘积之和：设外部结点搜索概率相等：q[j]=1/(n+1)：设各关键码的搜索概率相等：p[i]=1/n86设树中所有内、外部结点的搜索概率都相等：

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):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)相等搜索概率的情形设树中所有内、外部结点的搜索概率都相等：(1)相等搜索概率87

图(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)的情形所得的平均搜索长度最小。 图(e):ASLsucc=1/3*1+1/3*3+188设二叉搜索树中所有内、外部结点的搜索概率互不相等。

p[1]=0.5,p[2]=0.1,p[3]=0.05

q[0]=0.15,q[1]=0.1,q[2]=0.05,q[3]=0.05分别计算各个可能的扩充二叉搜索树的搜索性能，判断哪些扩充二叉搜索树的平均搜索长度最小。(2)不相等搜索概率的情形设二叉搜索树中所有内、外部结点的搜索概率互不相等。

89doiftodoiftoq0=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，

ASLunsucc=(0.15+0.1+0.05+0.05)*2=0.7。doiftodoiftoq0=0.15q1=0.1p1=0.90doifto

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=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.doiftoq0=q1=0.1p1=0.5q2=0.0591由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小，因此，图(c)和图(e)的情形是最优二叉搜索树。doiftoq0=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;由此可知，图(c)和图(e)的情形下树的平均搜索长度达到最小92一般把平均搜索长度达到最小的扩充的二叉搜索树称作最优二叉搜索树。等概率条件下，最优二叉搜索树的最短内部路径长度与最短外部路径长度,课本383页:高度平衡的二叉树优质精选课件93☞一、什么是平衡二叉树二、失衡二叉排序树的分析与调整

平衡二叉树☞一、什么是平衡二叉树平衡二叉树94平衡二叉树又称为AVL树。

一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

①

左子树与右子树的高度之差的绝对值小于等于1；②左子树和右子树也是平衡二叉排序树。平衡二叉树又称为AVL树。95结论2设h是一棵红黑树的高度(不包括外部结点)，n是树中内部结点的个数，r是根结点的黑高度，则以下关系式成立：当m≥n时，所有m个操作总共需要O(mlog2n)时间，从而使每次访问操作的所花费的平均时间达到O(log2n)，从整体上保持较高的时间性能。28-7(ctd.由特性1‘可知，每条从根结点到外部结点的路径中最后一个指针为黑色；(1)h≤2r如果插入前是空树，则那么新元素将成为根结点，根据特征1，根结点必须染成黑色。设新插入的结点为u，它的父结点和祖父结点分别是pu和gu，现在来考查不平衡的类型。0.红黑树的黑高度定义为其根结点的黑高度。(2)n≥2r-1可能的二叉搜索树如下所示。一棵判定树上的搜索成功的平均搜索长度ASLsucc可以定义为该树所有内部结点上的搜索概率p[i]与搜索该结点时所需的关键码比较次数c[i](=l[i],即结点所在层次)乘积之和：{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}p[i]=1/3,1≤i≤3,q[j]=1/4,0≤j≤3特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。伸展树、AVL树、并查集的用双亲表示的树，都属于自调整数据结构（self-adjustingdatastructure）。(3)由(2)可得r≤log2(n+1)，结合(1)，有根据红黑树的特性2，r一定是黑色结点。从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性3，所有从根到外部结点的路径上的黑色结点个数不等。例：平衡二叉树40247053452860引入平衡二叉树的目的是为了提高查找效率，使其平均查找长度为O(log2n)。402470532860结论2设h是一棵红黑树的高度(不包括外部结点)，96根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0，或1。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子，如2、-2。为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子。根据平衡二叉树的定义，平衡二叉树上所有结点的平9740247053452860402470532860例：下图对平衡二叉树和失去平衡的二叉排序树分别标注了平衡因子。01-1-100-110-1-20-140247053452860402470532860例：下图98一、什么是平衡二叉树

☞二、失衡二叉排序树的分析与调整

平衡二叉树一、什么是平衡二叉树平衡二叉树99如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：

LL平衡旋转

RR平衡旋转

LR平衡旋转

RL平衡旋转如果在一棵AVL树中插入一个新结点，就有可能造成100若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）1）LL平衡旋转：ABCABC若在A的左子树的左子树上插入结点，使A的平衡因子从1增101右单旋转(RotateRight)hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABD 在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到-2，造成了不平衡。 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。 以结点B为旋转轴，将结点A顺时针旋转。h000-1-1-2右单旋转(RotateRight)hhhACEBD(a)102

左改组（新插入结点出现在危机结点的左子树上进行的调整）