讲透学烂二叉树 (五)：分支平衡—AVL 树与红黑树伸展树自平衡

关注

发布于: 2 小时前

简叙二叉树二叉树的最大优点的就是查找效率高，在二叉排序树中查找一个结点的平均时间复杂度是 O(log₂N)；

在《讲透学烂二叉树(二)：树与二叉/搜索/平衡等树的概念与特征》提到

二叉排序树是为了实现动态查找而设计的数据结构，它是面向查找操作的。对于目标节点的查找过程类似与有序数组的二分查找，在二叉排序树中查找一个结点的平均时间复杂度是 O(log n)；

设节点数目为 n，树的深度为 h，假设树的每层都被塞满(第 L 层有 2^L 个节点，层数从 1 开始)，则根据等比数列公式可得 h=log（n+1）。即最好的情况下，二叉查找树的查找效率为 O(log n)。当二叉查找树退化为单链表时，比如，只有右子树的情况,如下图所示，此时查找效率为 O(n)。

760432-20160715124214998-1281755358.png

总之，二叉查找树越是“矮胖”，也就是每层尽可能地被“塞满”（每个父节点均有两个子节点）时，查找效率越高。

每层都被塞满时，查找效率最高，最高为 O(log n)。

当二叉查找树退化为单链表时，查找效率最低，最低为 O(n)。

为了解决二叉查找树退化为单链表时查找效率低下的问题，引入了平衡二叉树(AVL)。

平衡二叉树的基本操作插入：插入节点，让树平衡

删除：删除节点，让树平衡

旋转：旋转操作，它可以使得某一个结点提升到他父亲的位置而不破坏平衡二叉树的性质。

伸展：就是把当前节点，移动至树根，或者说，把当前节点变成根节点。

更多了解旋转与伸展相关内容，推荐阅读《伸展树（Splay Tree）进阶 - 从原理到实现》，这里我们首先将二叉树

平衡二叉树平衡二叉树（Balanced Binary Tree）又被称为 AVL 树（有别于 AVL 算法）

在 AVL 中任何节点的两个儿子子树的高度最大差别为 1，所以它也被称为高度平衡树，n 个结点的 AVL 树最大深度约 1.44log2n。查找、插入和删除在平均和最坏情况下都是 O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在 O(logN)。但是频繁旋转会使插入和删除牺牲掉 O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

平衡二叉树的常用算法有红黑树、AVL 树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在 O(log2n)，大大降低了操作的时间复杂度。

最小二叉平衡树的节点的公式如下：

F(n)=F(n-1)+F(n-2)+1

这个类似于一个递归的数列，可以参考 Fibonacci 数列，1 是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

平衡因子某结点的左子树与右子树的高度或深度差即为该结点的平衡因子（BF,Balance Factor），平衡二叉树（AVL 树）上所有结点的平衡因子只可能是 -1，0 或 1

下图中就标注了所有节点的平衡因子

平衡二叉树平衡因子计算

（平衡因子计算时左子树 - 右子树或右子树 - 左子树都可以，因为判断树是否平衡的条件是：每个结点的左右子树的高度之差的绝对值不超过 1，只不过判断失衡以后还要判断是哪一种失衡，这就需要根据情况来选择是左-右还是右-左了）

平衡二叉树查找节点在 AVL 树中查找与在二叉查找树中查找完全一样，因为 AVL 树总是保持平衡的，树的结构不会由于查询而改变，这里就不再赘述了

平衡二叉树插入节点先梳理一下步骤

平衡二叉树插入步骤

先来实现搜索最低失衡节点，搜索最低失衡节点是从新插入的节点（也就是叶子节点）

往上搜索（也可以说成从新增结点开始向根部回溯），搜索到的第一个平衡因子>1（|左子树高度-右子树高度|>1）的节点，作为最低失衡节点，因为是从新插入的节点往上搜索，二叉树的搜索是单向的（结构体成员中只有左右子树），单独使用一个函数来实现逆向搜索实现起来并不方便，这里就把搜索最低失衡节点的操作放到递归实现的插入操作中

平衡二叉树插入步骤演示

搞清楚了各个节点的高度，平衡因子的计算也比较方便了，下面就是 AVL 树的核心操作“旋转”，不同的失衡情况有不同的旋转方式，一共有四种节点失衡情况，如下图

1590962-20190812213300943-751024165.jpg

二叉树不平衡的四种情况不同失衡情况下的示例二叉树，如下图（读者可能会发现“最低失衡节点的左子树的左子树还有非空节点”这个判断依据，对第二组图适用，但对于第一组图不太合适）

二叉树不平衡的四种情况

AVL 树单旋转和双旋转单旋转单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图 3 是左左情况的解决方案，节点 k2 不满足平衡特性，因为它的左子树 k1 比右子树 Z 深 2 层，而且 k1 子树中，更深的一层的是 k1 的左子树 X 子树，所以属于左左情况。

平衡二叉树-单旋转

为使树恢复平衡，我们把 k2 变成这棵树的根节点，因为 k2 大于 k1，把 k2 置于 k1 的右子树上，而原本在 k1 右子树的 Y 大于 k1，小于 k2，就把 Y 置于 k2 的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵 AVL 树，因为 X 向上一移动了一层，Y 还停留在原来的层面上，Z 向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得 X 高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。

双旋转对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图 4 是左右情况的解决方案，节点 k3 不满足平衡特性，因为它的左子树 k1 比右子树 Z 深 2 层，而且 k1 子树中，更深的一层的是 k1 的右子树 k2 子树，所以属于左右情况。

平衡二叉树-双旋转

为使树恢复平衡，我们需要进行两步，第一步，把 k1 作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以 k2 为根的平衡二叉树。

745aae90c6e6a89.png

首先要确定中心结点，即最小失衡结点 A，其平衡因子的绝对值为 2，主要有四种不平衡的情况：

（1）在 A 的左儿子 B 的左子树插入，又称为 LL—右旋转；

（2）在 A 的左儿子 C 的右子树插入 P，又称为 LR—左右旋转；

（3）在 A 的右儿子 C 的左子树插入 P，又称为 RL—右左旋转；

（4）在 A 的右儿子 B 的右子树插入，又称为 RR—左旋转。

要记住两个重要节点，一个是失衡结点，另一个是失衡结点的儿子，该儿子在失衡路径上，旋转操作则是依据失衡结点的儿子为中心，对失衡结点进行下移动。在这四种失衡情况中（1）和（4）两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转，（2）和（3）两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

二叉树左右旋转讲解在进行旋转操作时，首先要找到最小失衡结点，判断失衡的类型，然后选择旋转的类型，如何判断呢？根据上面的图片中的结点 A，BF 为 2 确定为左儿子左边 L，根据左儿子的 BF 为-1，则确定为 R，此时属于不平衡情况（2），使用双旋转，下面详细介绍单旋转和双旋转的四种旋转方式。

1、LL 右旋转 LL 右旋转

P 下移，占据 C 的右儿子空穴，C 的右儿子称为 P 的左儿子

2、RR 左旋转 RR 左旋转

P 下移，占据 C 的左儿子空穴，C 的左儿子作为 P 的右儿子。

3、LR 左右旋转 LR 左右旋转

双旋转分为两步：左旋转，以 P 的儿子 C 作为失衡结点，Q 的右儿子 q，Q 下移，占据 q 的左儿子，q 的左儿子左儿子作为 Q 的右儿子，q 作为 P 的左儿子。

右旋转，P 下移，作为 p 的右儿子，q 的右儿子作为 P 的左儿子。

4、RL 右左旋转 LR 左右双旋转

右旋转，P 的右儿子 C 作为新的失衡结点 Q，Q 的左儿子 q，Q 下移，作为 q 的右儿子，q 的右儿子作为 Q 的左儿子，q 作为 P 的右儿子。

左旋转，P 下移，占据 q 的左儿子，q 的左儿子作为 P 的右儿子。

先梳理一下步骤

fixAfterInsertion 方法逻辑顺序图

平衡树，旋转代码实现

//AVL 树节点信息 template<class T>class TreeNode{public:TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}T data;//值 int hgt;//高度 unsigned int freq;//频率 TreeNode* lson;//指向左儿子的地址 TreeNode* rson;//指向右儿子的地址};//AVL 树类的属性和方法声明 template<class T>class AVLTree{private:TreeNode<T>* root;//根节点 void insertpri(TreeNode<T>* &node,T x);//插入 TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找 void insubtree(TreeNode<T>* node);//中序遍历 void Deletepri(TreeNode<T>* &node,T x);//删除 int height(TreeNode<T>* node);//求树的高度 void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转 void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转 void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转 void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转 int Max(int cmpa,int cmpb);//求最大值

public:    AVLTree():root(NULL){}    void insert(T x);//插入接口    TreeNode<T>* find(T x);//查找接口    void Delete(T x);//删除接口    void traversal();//遍历接口

复制代码

};//计算节点的高度 template<class T>int AVLTree<T>::height(TreeNode<T>* node){if(node!=NULL)return node->hgt;return -1;}//求最大值 template<class T>int AVLTree<T>::Max(int cmpa,int cmpb){return cmpa>cmpb?cmpa:cmpb;}//左左情况下的旋转 template<class T>void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2){TreeNode<T>* k1;k1=k2->lson;k2->lson=k1->rson;k1->rson=k2;

k2->hgt=Max(height(k2->lson),height(k2->rson))+1;k1->hgt=Max(height(k1->lson),k2->hgt)+1;

复制代码

}//右右情况下的旋转 template<class T>void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2){TreeNode<T>* k1;k1=k2->rson;k2->rson=k1->lson;k1->lson=k2;

k2->hgt=Max(height(k2->lson),height(k2->rson))+1;k1->hgt=Max(height(k1->rson),k2->hgt)+1;

复制代码

}//左右情况的旋转 template<class T>void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3){SingRotateRight(k3->lson);SingRotateLeft(k3);}//右左情况的旋转 template<class T>void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3){SingRotateLeft(k3->rson);SingRotateRight(k3);}//插入 template<class T>void AVLTree<T>::insertpri(TreeNode<T>* &node,T x){if(node==NULL)//如果节点为空,就在此节点处加入 x 信息{node=new TreeNode<T>();node->data=x;return;}if(node->data>x)//如果 x 小于节点的值,就继续在节点的左子树中插入 x{insertpri(node->lson,x);if(2==height(node->lson)-height(node->rson))if(x<node->lson->data)SingRotateLeft(node);elseDoubleRotateLR(node);}else if(node->data<x)//如果 x 大于节点的值,就继续在节点的右子树中插入 x{insertpri(node->rson,x);if(2==height(node->rson)-height(node->lson))//如果高度之差为 2 的话就失去了平衡,需要旋转 if(x>node->rson->data)SingRotateRight(node);elseDoubleRotateRL(node);}else ++(node->freq);//如果相等,就把频率加 1node->hgt=Max(height(node->lson),height(node->rson));}//插入接口 template<class T>void AVLTree<T>::insert(T x){insertpri(root,x);}//查找 template<class T>TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x){if(node==NULL)//如果节点为空说明没找到,返回 NULL{return NULL;}if(node->data>x)//如果 x 小于节点的值,就继续在节点的左子树中查找 x{return findpri(node->lson,x);}else if(node->data<x)//如果 x 大于节点的值,就继续在节点的左子树中查找 x{return findpri(node->rson,x);}else return node;//如果相等,就找到了此节点}//查找接口 template<class T>TreeNode<T>* AVLTree<T>::find(T x){return findpri(root,x);}//删除 template<class T>void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x){if(node==NULL) return ;//没有找到值是 x 的节点 if(x < node->data){Deletepri(node->lson,x);//如果 x 小于节点的值,就继续在节点的左子树中删除 xif(2==height(node->rson)-height(node->lson))if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) )DoubleRotateRL(node);elseSingRotateRight(node);}

else if(x > node->data){     Deletepri(node->rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x     if(2==height(node->lson)-height(node->rson))        if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))            DoubleRotateLR(node);        else            SingRotateLeft(node);}
else//如果相等,此节点就是要删除的节点{    if(node->lson&&node->rson)//此节点有两个儿子    {        TreeNode<T>* temp=node->rson;//temp指向节点的右儿子        while(temp->lson!=NULL) temp=temp->lson;//找到右子树中值最小的节点        //把右子树中最小节点的值赋值给本节点        node->data=temp->data;        node->freq=temp->freq;        Deletepri(node->rson,temp->data);//删除右子树中最小值的节点        if(2==height(node->lson)-height(node->rson))        {            if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))                DoubleRotateLR(node);            else                SingRotateLeft(node);        }    }    else//此节点有1个或0个儿子    {        TreeNode<T>* temp=node;        if(node->lson==NULL)//有右儿子或者没有儿子        node=node->rson;        else if(node->rson==NULL)//有左儿子        node=node->lson;        delete(temp);        temp=NULL;    }}if(node==NULL) return;node->hgt=Max(height(node->lson),height(node->rson))+1;return;

复制代码

}//删除接口 template<class T>void AVLTree<T>::Delete(T x){Deletepri(root,x);}//中序遍历函数 template<class T>void AVLTree<T>::insubtree(TreeNode<T>* node){if(node==NULL) return;insubtree(node->lson);//先遍历左子树 cout<<node->data<<" ";//输出根节点 insubtree(node->rson);//再遍历右子树}//中序遍历接口 template<class T>void AVLTree<T>::traversal(){insubtree(root);}JavaScript 代码，暂未实现

平衡二叉搜索树的分类平衡的二叉搜索树一般分为两类：

严格维护平衡的，树的高度控制在 log2n，使得每次操作都能使得时间复杂度控制在 O(logn)，例如 AVL 树，红黑树；

非严格维护平衡的，不能保证每次操作都控制在 O(logn)，但是每次操作均摊时间复杂度为 O(logn)，例如伸展树。

平衡二叉树之红黑树红黑树是一种自平衡二叉查找树，又称之为"对称二叉 B 树"。设平衡二叉树的深度为 N，则 N%2=0 结点为黑色，N%2=1 结点为红色。这些约束确保了红黑树的关键特性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

450px-Red-black_tree_example.svg.png

红黑树的自平衡操作：因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(logn) 次。

我们首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的（违背性质 5）。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意:

性质 1 和性质 3 总是保持着。

性质 4 只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。

性质 5 只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。

红黑树的插入操作：假设，将要插入的节点标为 N，N 的父节点标为 P，N 的祖父节点标为 G，N 的叔父节点标为 U。在图中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含的。

情形 1: 该树为空树，直接插入根结点的位置，违反性质 1，把节点颜色有红改为黑即可。

情形 2: 插入节点 N 的父节点 P 为黑色，不违反任何性质，无需做任何修改。在这种情形下，树仍是有效的。性质 5 也未受到威胁，尽管新节点 N 有两个黑色叶子子节点；但由于新节点 N 是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。

注：情形 1 很简单，情形 2 中 P 为黑色，一切安然无事，但 P 为红就不一样了，下边是 P 为红的各种情况，也是真正难懂的地方。

情形 3: 如果父节点 P 和叔父节点 U 二者都是红色，(此时新插入节点 N 做为 P 的左子节点或右子节点都属于情形 3,这里右图仅显示 N 做为 P 左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点 G 为红色(用来保持性质 4)。现在我们的新节点 N 有了一个黑色的父节点 P。因为通过父节点 P 或叔父节点 U 的任何路径都必定通过祖父节点 G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点 G 的父节点也有可能是红色的，这就违反了性质 4。为了解决这个问题，我们在祖父节点 G 上递归地进行上述情形的整个过程（把 G 当成是新加入的节点进行各种情形的检查）。比如，G 为根节点，那我们就直接将 G 变为黑色（情形 1）；如果 G 不是根节点，而它的父节点为黑色，那符合所有的性质，直接插入即可（情形 2）；如果 G 不是根节点，而它的父节点为红色，则递归上述过程（情形 3）。

二叉树插入操作

情形 4: 父节点 P 是红色而叔父节点 U 是黑色或缺少，新节点 N 是其父节点的左子节点，而父节点 P 又是其父节点 G 的左子节点。在这种情形下，我们进行针对祖父节点 G 的一次右旋转; 在旋转产生的树中，以前的父节点 P 现在是新节点 N 和以前的祖父节点 G 的父节点。我们知道以前的祖父节点 G 是黑色，否则父节点 P 就不可能是红色(如果 P 和 G 都是红色就违反了性质 4，所以 G 必须是黑色)。我们切换以前的父节点 P 和祖父节点 G 的颜色，结果的树满足性质 4。性质 5 也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点 G，现在它们都通过以前的父节点 P。在各自的情形下，这都是三个节点中唯一的黑色节点。

2.png

情形 5: 父节点 P 是红色而叔父节点 U 是黑色或缺少，并且新节点 N 是其父节点 P 的右子节点而父节点 P 又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形 4 处理以前的父节点 P 以解决仍然失效的性质 4。注意这个改变会导致某些路径通过它们以前不通过的新节点 N（比如图中 1 号叶子节点）或不通过节点 P（比如图中 3 号叶子节点），但由于这两个节点都是红色的，所以性质 5 仍有效。

3.png

注: 插入实际上是原地算法，因为上述所有调用都使用了尾部递归。

红黑树的删除操作：如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质 3 和性质 4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质 5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质 5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质 5。

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为 N(在新的位置上)，称呼它的兄弟(它父亲的另一个儿子)为 S。在下面的示意图中，我们还是使用 P 称呼 N 的父亲，SL 称呼 S 的左儿子，SR 称呼 S 的右儿子。

如果 N 和它初始的父亲是黑色，则删除它的父亲导致通过 N 的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质 5，树需要被重新平衡。有几种情形需要考虑:

情形 1: N 是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。

注意: 在情形 2、5 和 6 下，我们假定 N 是它父亲的左儿子。如果它是右儿子，则在这些情形下的左和右应当对调。

情形 2: S 是红色。在这种情形下我们在 N 的父亲上做左旋转，把红色兄弟转换成 N 的祖父，我们接着对调 N 的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在 N 有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色 S 的一个儿子），所以我们可以接下去按情形 4、情形 5 或情形 6 来处理。

1.png

情形 3: N 的父亲、S 和 S 的儿子都是黑色的。在这种情形下，我们简单的重绘 S 为红色。结果是通过 S 的所有路径，它们就是以前不通过 N 的那些路径，都少了一个黑色节点。因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点，所以仍然违反性质 5。要修正这个问题，我们要从情形 1 开始，在 P 上做重新平衡处理。

2.png

情形 4: S 和 S 的儿子都是黑色，但是 N 的父亲是红色。在这种情形下，我们简单的交换 N 的兄弟和父亲的颜色。这不影响不通过 N 的路径的黑色节点的数目，但是它在通过 N 的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。

4.png

情形 5: S 是黑色，S 的左儿子是红色，S 的右儿子是黑色，而 N 是它父亲的左儿子。在这种情形下我们在 S 上做右旋转，这样 S 的左儿子成为 S 的父亲和 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在 N 有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形 6。N 和它的父亲都不受这个变换的影响。

5.png

情形 6: S 是黑色，S 的右儿子是红色，而 N 是它父亲的左儿子。在这种情形下我们在 N 的父亲上做左旋转，这样 S 成为 N 的父亲（P）和 S 的右儿子的父亲。我们接着交换 N 的父亲和 S 的颜色，并使 S 的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质 3 没有被违反。但是，N 现在增加了一个黑色祖先: 要么 N 的父亲变成黑色，要么它是黑色而 S 被增加为一个黑色祖父。所以，通过 N 的路径都增加了一个黑色节点。

此时，如果一个路径不通过 N，则有两种可能性:

它通过 N 的新兄弟。那么它以前和现在都必定通过 S 和 N 的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。

它通过 N 的新叔父，S 的右儿子。那么它以前通过 S、S 的父亲和 S 的右儿子，但是现在只通过 S，它被假定为它以前的父亲的颜色，和 S 的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质 4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。

6.png

红黑树实现源码 #define BLACK 1#define RED 0

using namespace std;

class bst {private:

struct Node {    int value;    bool color;    Node *leftTree, *rightTree, *parent;
    Node() {        color = RED;        leftTree = NULL;        rightTree = NULL;        parent = NULL;        value = 0;    }
    Node* grandparent() {        if (parent == NULL) {            return NULL;        }        return parent->parent;    }
    Node* uncle() {        if (grandparent() == NULL) {            return NULL;        }        if (parent == grandparent()->rightTree)            return grandparent()->leftTree;        else            return grandparent()->rightTree;    }
    Node* sibling() {        if (parent->leftTree == this)            return parent->rightTree;        else            return parent->leftTree;    }};
void rotate_right(Node *p) {    Node *gp = p->grandparent();    Node *fa = p->parent;    Node *y = p->rightTree;
    fa->leftTree = y;
    if (y != NIL)        y->parent = fa;    p->rightTree = fa;    fa->parent = p;
    if (root == fa)        root = p;    p->parent = gp;
    if (gp != NULL) {        if (gp->leftTree == fa)            gp->leftTree = p;        else            gp->rightTree = p;    }
}
void rotate_left(Node *p) {    if (p->parent == NULL) {        root = p;        return;    }    Node *gp = p->grandparent();    Node *fa = p->parent;    Node *y = p->leftTree;
    fa->rightTree = y;
    if (y != NIL)        y->parent = fa;    p->leftTree = fa;    fa->parent = p;
    if (root == fa)        root = p;    p->parent = gp;
    if (gp != NULL) {        if (gp->leftTree == fa)            gp->leftTree = p;        else            gp->rightTree = p;    }}
void inorder(Node *p) {    if (p == NIL)        return;
    if (p->leftTree)        inorder(p->leftTree);
    cout << p->value << " ";                if (p->rightTree)        inorder(p->rightTree);}
string outputColor(bool color) {    return color ? "BLACK" : "RED";}
Node* getSmallestChild(Node *p) {    if (p->leftTree == NIL)        return p;    return getSmallestChild(p->leftTree);}
bool delete_child(Node *p, int data) {    if (p->value > data) {        if (p->leftTree == NIL) {            return false;        }        return delete_child(p->leftTree, data);    } else if (p->value < data) {        if (p->rightTree == NIL) {            return false;        }        return delete_child(p->rightTree, data);    } else if (p->value == data) {        if (p->rightTree == NIL) {            delete_one_child(p);            return true;        }        Node *smallest = getSmallestChild(p->rightTree);        swap(p->value, smallest->value);        delete_one_child(smallest);
        return true;    }}
void delete_one_child(Node *p) {    Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;    if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {        p = NULL;        root = p;        return;    }        if (p->parent == NULL) {        delete  p;        child->parent = NULL;        root = child;        root->color = BLACK;        return;    }        if (p->parent->leftTree == p) {        p->parent->leftTree = child;    } else {        p->parent->rightTree = child;    }    child->parent = p->parent;
    if (p->color == BLACK) {        if (child->color == RED) {            child->color = BLACK;        } else            delete_case(child);    }
    delete p;}
void delete_case(Node *p) {    if (p->parent == NULL) {        p->color = BLACK;        return;    }    if (p->sibling()->color == RED) {        p->parent->color = RED;        p->sibling()->color = BLACK;        if (p == p->parent->leftTree)            rotate_left(p->sibling());        else            rotate_right(p->sibling());    }    if (p->parent->color == BLACK && p->sibling()->color == BLACK            && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {        p->sibling()->color = RED;        delete_case(p->parent);    } else if (p->parent->color == RED && p->sibling()->color == BLACK            && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {        p->sibling()->color = RED;        p->parent->color = BLACK;    } else {        if (p->sibling()->color == BLACK) {            if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED                    && p->sibling()->rightTree->color == BLACK) {                p->sibling()->color = RED;                p->sibling()->leftTree->color = BLACK;                rotate_right(p->sibling()->leftTree);            } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK                    && p->sibling()->rightTree->color == RED) {                p->sibling()->color = RED;                p->sibling()->rightTree->color = BLACK;                rotate_left(p->sibling()->rightTree);            }        }        p->sibling()->color = p->parent->color;        p->parent->color = BLACK;        if (p == p->parent->leftTree) {            p->sibling()->rightTree->color = BLACK;            rotate_left(p->sibling());        } else {            p->sibling()->leftTree->color = BLACK;            rotate_right(p->sibling());        }    }}
void insert(Node *p, int data) {    if (p->value >= data) {        if (p->leftTree != NIL)            insert(p->leftTree, data);        else {            Node *tmp = new Node();            tmp->value = data;            tmp->leftTree = tmp->rightTree = NIL;            tmp->parent = p;            p->leftTree = tmp;            insert_case(tmp);        }    } else {        if (p->rightTree != NIL)            insert(p->rightTree, data);        else {            Node *tmp = new Node();            tmp->value = data;            tmp->leftTree = tmp->rightTree = NIL;            tmp->parent = p;            p->rightTree = tmp;            insert_case(tmp);        }    }}
void insert_case(Node *p) {    if (p->parent == NULL) {        root = p;        p->color = BLACK;        return;    }    if (p->parent->color == RED) {        if (p->uncle()->color == RED) {            p->parent->color = p->uncle()->color = BLACK;            p->grandparent()->color = RED;            insert_case(p->grandparent());        } else {            if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {                rotate_left(p);                rotate_right(p);                p->color = BLACK;                p->leftTree->color = p->rightTree->color = RED;            } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {                rotate_right(p);                rotate_left(p);                p->color = BLACK;                p->leftTree->color = p->rightTree->color = RED;            } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {                p->parent->color = BLACK;                p->grandparent()->color = RED;                rotate_right(p->parent);            } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {                p->parent->color = BLACK;                p->grandparent()->color = RED;                rotate_left(p->parent);            }        }    }}
void DeleteTree(Node *p) {    if (!p || p == NIL) {        return;    }    DeleteTree(p->leftTree);    DeleteTree(p->rightTree);    delete p;}

复制代码

public:

bst() {    NIL = new Node();    NIL->color = BLACK;    root = NULL;}
~bst() {    if (root)        DeleteTree(root);    delete NIL;}
void inorder() {    if (root == NULL)        return;    inorder(root);    cout << endl;}
void insert(int x) {    if (root == NULL) {        root = new Node();        root->color = BLACK;        root->leftTree = root->rightTree = NIL;        root->value = x;    } else {        insert(root, x);    }}
bool delete_value(int data) {    return delete_child(root, data);}