数据基础及教程 4

9.3树表的查找几种特殊树形结构—统称为树表。这里的树表采用链式存储结构，由于链式存储结构既适合查找，也适合数据修改，属于动态查找表。对于动态查找表，不仅要讨论查找方法，还讨论修改方法。1/1139.3.1二叉排序树1.二叉排序树的定义若它的左子树非空，则左子树上所有结点值（默认为结点关键字）均小于根结点值。若它的右子树非空，则右子树上所有结点值均大于根结点值。左、右子树本身又各是一棵二叉排序树。

二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：2/113一棵二叉排序树示例：42135768根结点最左下结点，即为关键字最小的结点根结点最右下结点，即为关键字最大的结点特点：中序序列：1，2，3，4，5，6，7，8中序序列是一个递增有序序列！3/113定义二叉排序树的结点类型如下：template<typenameT1,typenameT2>structBSTNode { //二叉排序树结点类

T1key;

//存放关键字,假设关键字为T1类型T2data;

//存放数据项,假设数据项为T2类型

BSTNode*lchild;

//存放左孩子指针BSTNode*rchild;

//存放右孩子指针BSTNode(T1k,T2d){ //构造函数key=k;data=d;lchild=rchild=NULL; //新建结点默认为叶子结点}};二叉排序树的每个结点含key和datakey,data4/113设计二叉排序树类模板BSTClass<T1,T2>：template<typenameT1,typenameT2>classBSTClass { //二叉排序树类模板public:

BSTNode<T1,T2>*r;

//二叉排序树根结点

BSTNode<T1,T2>*f;

//用于临时存放待删除结点的双亲

BSTClass(){

//构造函数r=NULL;f=NULL;}

~BSTClass() { //析构函数DestroyBTree(r); //调用DestroyBTree()函数r=NULL;}voidDestroyBTree(BSTNode<T1,T2>*b){ //释放所有的结点空间

…}

//二叉排序树的基本运算算法};5/1132.二叉排序树的插入和生成在根结点p的二叉排序树中插入关键字为k的结点的过程如下：若p为空，创建一个key为k的结点，返回将它作为根结点。若k<p->key，将k插入p结点的左子树中并且修改p的左指针。若k>p->key，将k插入p结点的右子树中并且修改p的右指针。其他情况是k=p->key，说明树中已有关键字k，修改data值并返回p。6/113voidInsertBST(T1k,T2d){ //插入一个(k,d)结点r=_InsertBST(r,k,d);}BSTNode<T1,T2>*_InsertBST(BSTNode<T1,T2>*p,T1k,T2d){//在以p为根的BST中插入关键字为k的结点if(p==NULL) //原树为空,为根结点p=newBSTNode<T1,T2>(k,d);elseif(k<p->key)p->lchild=_InsertBST(p->lchild,k,d); //插入到p的左子树中elseif(k>p->key)p->rchild=_InsertBST(p->rchild,k,d); //插入到p的右子树中else //相同关键字,修改data域p->data=d;returnp;}7/113

创建二叉排序树r是从一个空树开始，先创建根结点，以后每插入一个关键字k，就调用一次InsertBST(k,d)算法将(k,d)插入到当前的二叉排序树中。voidCreateBST(vector<T1>&a,vector<T2>&b){//由a和b向量创建一棵二叉排序树r=newBSTNode<T1,T2>(a[0],b[0]); //创建根结点for(inti=1;i<a.size();i++) //创建其他结点

InsertBST(a[i],b[i]); //插入(a[i],b[i])}8/1133.二叉排序树的查找BSTNode<T1,T2>*SearchBST(T1k){//在二叉排序树中查找关键字为k的结点return_SearchBST(r,k); //r为二叉排序树的根结点}BSTNode<T1,T2>*_SearchBST(BSTNode<T1,T2>*p,T1k){//被SearchBST方法调用if(p==NULL)returnNULL; //空树返回NULLif(p->key==k)returnp; //找到后返回pif(k<p->key)return_SearchBST(p->lchild,k);//在左子树中递归查找elsereturn_SearchBST(p->rchild,k);//在右子树中递归查找}查找算法：9/113与折半查找的判定树类似，在二叉排序树中每个空指针处添加一个外部结点。在二叉排序树中查找时，若查找成功，则是从根结点出发走了一条从根结点到查找到结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个外部结点的路径。因此与折半查找类似，查找中关键字比较的次数不超过树的高度。查找说明：10/113

【例9.7】已知一组关键字为

（25,18,46,2,53,39,32,4,74,67,60,11）按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树，并求在等概率的情况下查找成功的平均查找长度和查找不成功的平均查找长度。11/113生成的二叉排序树如下。25182464113953327467602518462533932474676011生成的二叉排序树12/1131825241146393253746760在等概率的情况下，查找成功的平均查找长度为：13/1131825241146393253746760在等概率的情况下，查找不成功的平均查找长度为：14/113一个关键字集合可以有多个不同顺序的关键字序列，对于不同的关键字序列，CreateBST()算法创建的二叉排序树可能不同。例如，关键字序列为（5，2，1，6，7，4，3），创建的二叉排序树如图(a)所示。若关键字序列为（1，2，3，4，5，6，7），创建的二叉排序树如图(b)所示。1234567（b）高度为75261437（a）高度为4提示15/1131234567（b）高度为75261437（a）高度为416/113那么如何分析二叉排序树的查找性能呢？有如下两种分析方法。给定含n个关键字的集合，假设所有关键字不相同，对应有n!个关键字序列，每个关键字序列构造一棵二叉排序树，所有这些二叉排序树中查找每个关键字的平均时间为O(log2n)。给定含n个关键字的特定关键字序列构造一棵二叉排序树。其中查找性能最好的是高度最小的二叉排序树，最好查找性能为O(log2n)。查找性能最坏的是高度为n的二叉排序树（单支树），最坏查找性能为O(n)。平均情况由具体的关键字序列来确定。所以常说二叉排序树的时间复杂度在O(log2n)和O(n)之间，就是指这种分析方法。17/113

【例9.8】在含有27个结点的二叉排序树上，查找关键字为35的结点，以下4个选项中哪些是可能的关键字比较序列？A.28，36，18，46，35 B.18，36，28，46，35C.46，28，18，36，35 D.46，36，18，28，35查找序列（k1，k2，…，kn）的查找树画法是，每一层只有一个结点，首先k1为根结点，再依次画出其他结点，若ki+1<ki，则ki+1的结点作为ki结点的左孩子，否则作为右孩子。查找树是原来二叉排序树的一部分，也一定构成一棵二叉排序树。18/113A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3528361818362846462818364636182635是一棵二叉排序√

ⅩⅩⅩ19/1134.二叉排序树的删除删除关键字与删除结点是一回事（每个结点一个关键字）。删除一个结点时不能简单地把以该结点为根的子树都删去，只能删除该结点本身，并且还要保证删除后的二叉树仍然满足BST性质。也就是说，在二叉排序树中删除一个结点就相当于删除有序序列（即该树的中序序列）中的一个结点。20/113删除结点p分为以下几种情况

（1）若结点p是叶子结点（结点p的度为0），删除该结点等同于删除该结点的子树，所以可以直接删除该结点。526143789（a）结点p为叶子结点：直接删除删除结点9p2614378521/113（b）结点p仅有左孩子：用左孩子q结点替代结点p删除结点4qp52643789526137891

（2）若结点p只有左孩子没有右孩子（结点p的度为1），根据二叉排序树的特点，可以用结点p的左子树替代结点p的子树，也就是直接用其左孩子替代它（结点替代）。22/113（c）结点p仅有右孩子：用右孩子q结点替代结点p删除结点7pq52614378952614389

（3）若结点p只有右孩子没有左孩子（结点p的度为1），根据二叉排序树的特点，可以用结点p的右子树替代结点p的子树，也就是直接用其右孩子替代它（结点替代）。23/113（d）结点p有左右孩子：找到其左孩子的最右下结点q，置p结点值为q结点值（值替代），再删除q结点（q结点没有右孩子，最多只有左孩子，采用(b)删除）删除结点5p52614378942613789q

（4）若结点p既有左孩子又有右孩子（结点p的度为2）

间接删除。24/113从二叉排序树中删除结点p是通过修改其双亲的相关指针实现的。为此需要标识结点p的双亲结点f，并且用flag标识结点p是结点f的何种孩子，flag=-1表示结点p是根结点没有双亲，flag=0表示结点p是结点f的左孩子，flag=1表示结点p是结点f的右孩子。所以，删除中的查找不能简单地采用前面的查找算法，而需要在查找中确定结点p对应的双亲结点f和左右孩子标记flag。删除算法：25/113boolDeleteBST(T1k){ //删除关键字为k的结点f=NULL;return_DeleteBST(r,k,-1); //r为二叉排序树的根结点}

bool_DeleteBST(BSTNode<T1,T2>*p,T1k,intflag){//被DeleteBST方法调用if(p==NULL)returnfalse; //空树返回falseif(p->key==k)returnDeleteNode(p,f,flag); //找到后删除p结点if(k<p->key){f=p;return_DeleteBST(p->lchild,k,0); //在左子树中递归查找}else{f=p;return_DeleteBST(p->rchild,k,1); //在右子树中递归查找}}f记录找到的结点p的双亲结点26/113删除结点p：它仅有左孩子：fp（b）flag=0f->lchild=p->lchildp（a）flag=-1fp（c）flag=1f->rchild=p->lchildr=p->lchildboolDeleteNode(BSTNode<T1,T2>*p,BSTNode<T1,T2>*f,intflag){//删除结点p（其双亲为f）if(p->rchild==NULL){ //结点p只有左孩子(含p为叶子的情况)if(flag==-1) //结点p的双亲为空(p为根结点)r=p->lchild; //修改根结点r为p的左孩子elseif(flag==0) //p为双亲f的左孩子f->lchild=p->lchild; //将f的左孩子置为p的左孩子else //p为双亲f的右孩子f->rchild=p->lchild; //将f的右孩子置为p的左孩子}27/113elseif(p->lchild==NULL){ //结点p只有右孩子if(flag==-1) //结点p的双亲为空(p为根结点)r=p->rchild; //修改根结点r为p的右孩子elseif(flag==0) //p为双亲f的左孩子f->lchild=p->rchild; //将f的左孩子置为p的左孩子else //p为双亲f的右孩子f->rchild=p->rchild; //将f的右孩子置为p的左孩子}删除结点p：它仅有右孩子：与仅有左孩子类似！28/113

当被删结点p有左、右孩子时，采用前面的删除方法，先让q指向其左孩子结点，分为以下两种情况：p->key=q->keyp->lchild=q->lchildp（a）结点q没有右孩子qelse { //结点p有左右孩子BSTNode<T1,T2>*f1=p; //f1为结点q的双亲结点BSTNode<T1,T2>*q=p->lchild; //q转向结点p的左孩子if(q->rchild==NULL){ //若结点q没有右孩子p->key=q->key; //将被删结点p的值用q的值替代p->data=q->data;p->lchild=q->lchild; //删除结点q}29/113p（b）结点q有右孩子qf1p->key=q->keyf1->rchild=q->lchildelse{ //若结点q有右孩子while(q->rchild!=NULL){ //找到最右下结点q,其双亲结点为f1f1=q;q=q->rchild;}p->key=q->key; //将被删结点p的值用q的值替代p->data=q->data;f1->rchild=q->lchild; //删除结点q}}returntrue;}30/1139.3.2平衡二叉树和AVL树既保持BST性质又保证树的高度较小，通过这样的平衡规则和操作来维护O(log2n)高度的二叉排序树称为平衡二叉树，平衡二叉树有多种。AVL树、红黑树、伸展树和Treap等都是平衡二叉树。31/113AVL树的高度平衡性质：树中每个结点的左、右子树的高度至多相差1。也就是说，如果树T中结点v有孩子结点x和y，则|h(x)-h(y)|≤1，h(x)表示以结点x为根的子树高度。526143710-1010-13142567（b）一棵非AVL树（a）一棵AVL树0-1-2-3-2-1032/113template<typenameT1,typenameT2>structAVLNode{

//AVL树结点类模板

T1key;

//关键字k

T2data;

//关键字对应的值d

intht;

//当前结点的子树高度

AVLNode*lchild,*rchild;

//左右指针AVLNode(T1k,T2d){ //构造函数，新建结点均为叶子，高度为1key=k;data=d;ht=1; //当前结点的子树高度lchild=rchild=NULL;}};AVL树中结点类型设计为AVLNode<T1，T2>类模板，每个结点存放[key，data]，其中关键字key为T1类型，数据项data为T2类型。33/113template<typenameT1,typenameT2>classAVLTree{

//AVL树类模板

AVLNode*r;

//AVL的根结点public:AVLTree():r(NULL){ //构造函数intgetht(AVLNode*p){ //返回结点p的子树高度if(p==NULL)return0;returnp->ht;}

//AVL树的其他基本运算算法};

设计对应的AVL树类模板为AVLTree<T1，T2>，其中省略的析构函数与前面BSTClass<T1，T2>中析构函数完全相同。34/1131.旋转操作在AVL树中插入或者删除结点时可能导致失衡，可以通过旋转操作使其平衡，旋转操作分为左旋和右旋两种。很容易证明旋转操作不会改变二叉排序树特性。B左旋AβαγABβαγ右旋35/113左旋算法如下：AVLNode*left_rotate(AVLNode*a){ //以A结点为根做左旋转 AVLNode*b=a->rchild; a->rchild=b->lchild; b->lchild=a; a->ht=max(getht(a->rchild),getht(a->lchild))+1;

//更新A结点的高度 b->ht=max(getht(b->rchild),getht(b->lchild))+1;

//更新B结点的高度 returnb;}B左旋AβαγABβαγ36/113右旋算法如下：AVLNode*right_rotate(AVLNode*b){ //以B结点为根做右旋转 AVLNode*a=b->lchild; b->lchild=a->rchild; a->rchild=b; b->ht=max(getht(b->rchild),getht(b->lchild))+1;

//更新B结点的高度 a->ht=max(getht(a->rchild),getht(a->lchild))+1;

//更新A结点的高度 returna;}BAβαγABβαγ右旋37/1132.AVL树中插入结点先采用二叉排序树插入结点的方法向AVL树中插入一个新结点。再从该新插入结点到根结点方向（向上方向查找）找第一个失衡结点A。如果找不到这样的结点，说明插入后仍然是一棵AVL树，不需要调整。如果找到这样的结点A，称结点A的子树为最小失衡子树（距离插入结点最近且平衡因子的绝对值大于1的结点为根的子树，其高度至少为3），说明插入后破坏了平衡性，需要调整。38/113调整方式以最小失衡子树的根结点A和两个相邻的刚查找过的结点构成两层左右关系来分类（LL、RR、LR和RL之一）。当最小失衡子树调整为平衡子树后，从该子树的根结点继续向上查找，一旦遇到失衡结点便做类似的调整，直到根结点为止，这样就会得到一棵插入结点后的AVL树。ABCL或者RL或者R39/1131）LL型调整ABγhβhαh10插入前BAγhβhαh00调整后LL调整LLABγhβhαh21插入后插入结点右旋一次旋转40/1132）RR型调整ABγhβhαh-10插入前RR插入一结点插入后ABγhβhαh-2-1RR调整BAγhβhαh00调整后左旋一次旋转41/1133）LR型调整ABγhβhαh+110插入前Cδh+1LR调整调整后CB00A-1γhβhαh+1δh+1插入结点插入后ABγhβhαh+12-1Cδh+1LRLR双旋转：A的左子树B先左旋转，再按根结点A右旋转！(2次旋转）42/1134）RL型调整RL调整调整后CA01B0γhβhαh+1δh+1ABγhβhαh+1-10插入前Cδh+10L插入一结点插入后ABγhβhαh+1-21Cδh+1-1RRL双旋转：A的左子树B先右旋转，再按根结点A左旋转！(2次旋转）43/113

【例9.9】输入关键字序列（16，3，7，11，9，26，18，14，15），给出构造一棵AVL树的步骤。1637160161301623-170LR703016044/1131197316-11110-2107316119LL731191600045/113267311916-11026-2RR73119160000260-146/113187311916261-2180RL7311918260016047/113731191826161414101-148/11373119182616-115142150LR731191826150140160构造的结果AVL树49/1133.AVL树中删除结点

首先在AVL树中查找关键字为k的结点x（假定存在这样的结点并且唯一），删除结点x的过程如下：

（1）如果结点x左子树为空，用其右孩子结点替换它，即直接删除结点x。

（2）如果结点x右子树为空，用其左孩子结点替换它，即直接删除结点x。50/113

（3）如果结点x同时有左右子树（这种情况下，结点x是通过值替换间接删除的，称为间接删除结点），分为两种情况：若结点x的左子树较高，在其左子树中找到最大结点q，直接删除结点q，用结点q的值替换结点x的值。若结点x的右子树较高，在其右子树中找到最小结点q，直接删除结点q，用结点q的值替换结点x的值。51/113RL-21xppR(a)pR的左子树高：RLRR-2-1xppR(b)pR的右子树高：RR

（4）当直接删除结点x时，沿着其双亲到根结点方向逐层向上求结点的平衡因子，若一直找到根结点时路径上的所有结点均平衡，说明删除后的树仍然是一棵平衡二叉树，不需要调整，删除结束。若找到路径上的第一个失衡结点p，就要进行调整。①若直接删除的结点在结点p的左子树中。(c)若pR的左右子树高度相同，则做RL或RR调整均可②若直接删除的结点在结点p的右子树中，调整过程类似。52/113【例9.10】对例9.9生成的AVL树，给出删除结点11、9和3的过程。73119182615141653/113删除结点11731191826151416p找到结点11结点1有左右孩子右子树高，找到右孩子的最左小结点qq14值替换1-1-1直接删除14沿着根结点方向求平衡因子731191826151614均平衡54/113删除结点9731191826151614均平衡找到结点9-11直接删除9沿着根结点方向求平衡因子7311182615161455/11373111826151614删除结点3找到结点3直接删除3沿着根结点方向求平衡因子0-21：左子树高RLRL调整147111826161556/1134．AVL树的查找

构造一系列的AVL树T1、T2、T3、…，其中，Th（h=1、2、3、…）是高度为h且结点数尽可能少的AVL树（总是让左子树较高）。高度固定结点个数n最少的平衡二叉树T1T2T3T457/113构造Th，先分别构造Th-1和Th-2，使Th以Th-1和Th-2作为其根结点的左、右子树。ThTh-1Th-2设N(h)（高度h是正整数）为Th的结点数：N(1)=1N(2)=2N(h)=N(h-1)+N(h-2)+158/113Fibonacci数的关系：F(1)=1F(2)=1F(h)=F(h-1)+F(h-2)通过检查两个序列的前几项就可发现两者之间的对应关系：N(h)=F(h+2)-159/113如果树中有n个结点，那么树的最大高度为：含有n个结点的AVL树对应的查找时间复杂度为O(log2n)。结论60/113

另外，设M(h)（高度h是正整数）为Th中最小叶子结点的层次，可以看出有下列关系成立：T1T2T3T4M(1)=1M(2)=2M(h)=min(M(h-1)，M(h-2))+161/113

【例9.11】在含有15个结点的AVL树中查找关键字为28的结点，以下哪些是可能的关键字比较序列？A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36

画出4个查找序列对应的查找树都是二叉排序树，B序列对应的查找树不是一棵二叉排序树，排除选项B。38482862/113设Nh表示高度为h的AVL树中含有的最少结点数，按照前面N(h)的公式求得：N(3)=4，N(4)=7，N(5)=12，N(6)=20>15也就是说，15个结点的AVL树的最大高度为5。而D序列比较了6次还查找失败，显然是错误的，排除选项D。

A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36k=2863/113n=15的AVL树的最小高度为4，即log2(n+1)=4，此时为一棵满二叉树。即h只能是4和5。h=4时为一棵满二叉树，所有叶子结点的层次为4，此时失败的查找需要4次比较，所以选项A不可能？

A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36k=2864/113h=5时，加上外部结点后树高为6，此时将外部结点看成叶子结点，一定也是一棵AVL树。设M(h)表示高度为h的AVL树中最小叶子结点的层次，按照前面M(h)的公式求得M(3)=2，M(4)=3，M(5)=3，M(6)=4。这样说明15个结点的AVL树中最小外部结点层次为4，查找失败至少需要3次比较，排除选项A。答：C

A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36k=2865/1139.3.3红黑树红黑树（red-blacktree）也是一种平衡二叉树，它在AVL树的平衡性质基础上进一步放宽条件，将AVL树中每个结点的左右子树高度差不超过1改为任何结点的左右子树的高度差不超过两倍。为此为每个结点指定颜色，要么为黑色，要么为红色，另外增加外部结点（通常用NIL表示外部结点），同时满足以下性质。66/113根结点的颜色为黑色。所有外部结点的颜色为黑色。如果一个结点是红色，则它的所有孩子结点为黑色，即任何路径中不存在两个相邻的红色结点。从根结点到任一外部结点的路径上包含的黑色结点个数都是相等的。1253410768111513141767/113设红黑树的高度为h，假设从根结点到叶子结点的路径上的黑色结个数为r，由于该路径中至少有一半的黑色结点即有h≤2r（或者h/2≤r）。可以推出从根结点向下的r层都是没有外部结点的，所以这些层中内部结点的个数是2r-1（前r层是一棵满二叉树）。设总的内部结点个数为n，显然n≥2r-1，即r≤log2(n+1)，则 h/2≤r≤log2(n+1)

h≤2log2(n+1)=O(log2n)所以红黑树查找算法的时间复杂度为O(log2n)。12534107681115131417r=3，前3层是一棵满二叉树，全部内部结点个数为23-1=768/1131.红黑树中插入结点操作：先按二叉排序树中插入新结点的方法在红黑树中插入一个新结点X，置当前结点为X（新结点X一定是作为叶子结点插入的），所有的新结点X一律为红色结点，插入中分为如下几种情况。

（1）新结点X为根结点，将其翻转为黑色结点（任何情况下根结点都是黑色结点）。插入过程结束。69/113

（2）如果新结点X的双亲结点P为黑色结点，此时插入新结点后满足红黑树的所有性质，插入过程结束。70/113改变结点颜色：将结点P和结点U由红色变为黑色，将它们的双亲结点G变为红色。下图是当新结点X为A、B、C、D中任何一个结点时的改变结点颜色过程。因为祖父结点G变为红色，再以X为结点G向上继续判断是否存在两个相邻红色结点，如果存在则继续调整。UPGACBDUPGACBD改变颜色（3）父红叔红（祖父必黑）71/113调整与AVL树的调整类似，分为以下4种情况。（4）父红叔黑（祖父必黑）①结点X的双亲结点P是祖父结点G的左孩子（L），结点X是双亲结点P的左孩子（L），调整方式如下图，先以结点G为根做LL调整，再将结点P变为黑色，结点G变为红色。GPUX12453LLGPUX12453LL72/113②结点X的双亲结点P是祖父结点G的左孩子（L），结点X是双亲结点P的右孩子（R），调整方式如下图所示，先以结点G为根做LR调整，再将结点X变为黑色，结点G变为红色。GXUP12453LRGPUX12453LR73/113③结点X的双亲结点P是祖父结点G的右孩子（R），结点X是双亲结点P的右孩子（R），调整方式如图9.33所示，先以结点G为根做RR调整，再将结点P变为黑色，结点G变为红色。RRXPUG124GPUX4512353RR74/113④结点X的双亲结点P是祖父结点G的左孩子（L），结点X是双亲结点P的右孩子（R），调整方式如下图所示，先以结点G为根做LR调整，再将结点X变为黑色，结点G变为红色。LPXUG3124RGPX34U5125LR75/113

【例9.12】给出在如下图所示的红黑树中依次插入70、60、65和62的过程。50901080(a)红黑树76/11350901080(b)插入7070插入过程50901080(a)红黑树插入7077/113509010807050901080(c)插入60706050901080(d)改变颜色7060插入6078/11350901080706050901080(f)LR型调整656070LR901080(e)插入6570606550插入6579/11365905080(i)RL型调整706062105090108065607050901080(g)插入6265607062RL50901080(h)改变结点颜色65607062RL插入6280/1132.红黑树中删除结点在红黑树中删除结点X与二叉排序树中删除结点的方法类似，但也存在明显的差别。先在红黑树中查找结点X，根据结点X的位置分为3种情景：情景1：删除结点X为叶子结点，置N=X。情景2：删除结点X只有一个子结点，置N为该子结点，用结点N的数据替代结点X的数据。情景3：删除结点X有两个子结点，在其右子树中找到最小结点N（结点N一定没有左孩子），用结点N的数据替代结点X的数据。或者在其左子树中找到最大结点N（结点N一定没有右孩子），用结点N的数据替代结点X的数据。转换为删除结点N81/113这样将删除结点X转换为删除结点N，结点N为叶子结点或者只有一个孩子。后面的工作就是删除结点N，又分为3种情况：

（1）若结点N是红色叶子结点，则直接删除结点N，不影响黑色结点个数，删除过程结束。82/113

（2）如果结点N是红色结点且只有一个孩子，该孩子一定是黑色结点，否则路径上出现连续双红结点。

操作：将其孩子结点N'的数据替换结点N的数据，问题转换为删除黑色结点N'，同情况（3）。NN'

NN'N'N'83/113

（3）若结点N为黑色叶子结点或者只有一个孩子，用P表示双亲结点，B表示兄弟结点，BL和BR分别表示结点B的左右孩子即结点N的侄子，图中的白色结点

表示颜色可红可黑。删除操作根据结点B和结点P的不同颜色组合又分为如下4种子情况。BLBBRNP如：1234584/113①兄黑有侄红（N结点是P结点的右孩子）:调整如下，随即完成！LLPBLBBRN12453BBRPBL3421(a)左侄为红色，右侄任意LL,BL,B1255LRPBLBBRN12453BRBLPB1243(b)左侄为黑色，右侄为红色6LR,BR5643585/113对称地（N结点是P结点的左孩子）：调整如下，随即完成！RRPBLBBRN231BNPBLBR413(a)左侄任意，右侄为红色56452RR,BR,B(b)左侄为红色，右侄为黑色RLPBLBBRN23BLPBRB54543211RL,BL86/113②仅父红（只有双亲结点P为红色结点，而兄弟B和侄子均为黑色）：改变颜色，调整随即完成！PBLBBRN1243(a)结点N为右孩子PBLBBR124355PBLBBRN2354(b)结点N为左孩子PBLBBR23541187/113③全黑（兄弟结点B、侄子和双亲结点P均为黑色）：将兄弟B变为红色，再从结点P继续向上回溯直到根结点。PBLBBRN1243(a)结点N为右孩子PBLBBR124355PBLBBRN2354(b)结点N为左孩子PBLBBRN23541188/113④仅兄弟红（只有兄弟B为红色结点，而侄子和双亲结点P均为黑色）：调整如下，此时结点N的兄弟为黑色，转换为①或者②的子情况。RRPBLBBRN2354(b)结点N为左孩子1BNPBLBR13245RRLLPBLBBRN1243(a)结点N为右孩子BBRPNBL345521LL89/113【例9.13】给出在如图(a)所示的红黑树中依次删除5、14和13的过程。81051431361716(a)一棵红黑树90/1131061431381716(b)删除581051431361716删除591/113106143138171610616313817(c)删除14删除1492/11310616313817106163817(d)结点17变为红色全黑：兄弟17变红色106163817(e)结点6变为红色全黑：兄弟6变红色106163817(f)删除1310为根，直接删除13删除1393/113红黑树中一次插入、删除的时间复杂度均为O(log2n)。尽管红黑树不如AVL树那么平衡，但是红黑树插入删除结点的性能优于AVL树，当向红黑树中插入或者删除结点引起红黑树不平衡时只需要最多3次旋转就能解决，而相同条件下，AVL树的旋转次数要多于红黑树。删除时结构发生较大的改变AVL94/1139.3.4*STL中的关联容器所谓关联容器就是容器中每个元素有一个key（关键字），通过key来存储和读取元素。STL中的关联容器有集合（set）和映射（map）两类，均采用红黑树组织数据。由于树结构中没有位置的概念，所以关联容器没有提供顺序容器中的[]，front()、push_front()、back()、push_back()以及pop_back()操作。95/1131.set（集合容器）/multiset（多重集容器）set和multiset都是集合类模板，其元素值称为关键字。set中元素的关键字是唯一的，multiset中元素的关键字可以不唯一，而且默认情况下会对元素按关键字自动进行升序排列。查找速度比较快（时间复杂度为O(log2n)），同时支持集合的交、差和并等一些集合上的运算。96/113set/multiset的主要成员函数成员函数说明empty()判断容器是否为空size()返回容器中实际元素个数insert(k)插入元素kerase(k)从容器删除元素kerase(it)从容器删除迭代器it指向的元素clear()删除所有元素count(k)返回容器中关键字k出现的次数find(k)如果容器中存在关键字为k的元素，返回该元素的迭代器，否则返回end()值begin()用于正向迭代，返回容器中第一个元素的位置end()用于正向迭代，返回容器中最后一个元素后面一个位置rbegin()用于反向迭代，返回容器中最后一个元素的位置rend()用于反向迭代，返回容器中第一个元素前面一个位置97/113STL为set/multiset提供了通用算法lower_bound(beg，end，k)和upper_bound(beg，end，k)等。前者返回一个迭代器指向第一个关键字大于等于k的元素，后者返回一个迭代器指向第一个关键字大于k的元素。98/113#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s; //定义set容器sset<int>::iteratorit; //定义set容器迭代器its.insert(1);s.insert(3);s.insert(2);s.insert(2); //2重复，不会插入printf("s:");for(it=s.begin();it!=s.end();it++)printf("%d",*it); //输出:123printf("\n");99/113multiset<int>ms; //定义multiset容器msmultiset<int>::iteratormit; //定义multiset容器迭代器mitms.insert(1);ms.insert(3);ms.insert(2);ms.insert(2); //重复的2会插入printf("ms:");for(mit=ms.begin();mit!=ms.end();mit++)printf("%d",*mit); //输出:1223printf("\n");return0;}100/1132.map（映射容器）/multimap（多重映射容器）map和multimap都是映射类模板。映射是指元素类型为（key，value），其中key为关键字，value是对应的值，可以使用关键字key来访问相应的值value。map/multimap中的key和value是一个pair结构类型。structpair{

T1first;

//关键字T2second;

//值}101/113map/multimap的主要成员