让我们开始吃树~

提起树状数据结构的家族，我们不得不从二叉树开始说起。

在学二叉树的时候，我们知道，二叉树是指每个结点最多只有两个子结点的树。

二叉树，是指树中每个结点最多只有两个结点的树。当然，二叉树本身好像没有什么太大的作用。我们平时所说的二叉树，基本上就是指二叉排序树(二叉查找树)。

二叉查找树（BST）

二叉查找树就是在二叉树的基础上增加有序性，这个有序性一般是指自然顺序，有了有序性，我们就可以使用二叉树来快速的查找、删除、插入元素了。

但是，二叉查找树有个非常严重的问题，试想，还是这三个元素，如果按照A、B、C的顺序插入元素会怎样？

那么如果按照顺序插入，就会变成一个单链表。没错，当按照元素的自然顺序插入元素的时候，二叉查找树就退化成单链表了，单链表的插入、删除、查找元素的时间复杂度是多少？？

所以，在极限状态下，二叉查找树的时间复杂度是非常差的。

既然，插入元素后有可能导致二叉查找树的性能变差，我们是不是增加了一些手段，让插入后的二叉查找树依然性能良好？

这种手段，就叫做平衡。可以做到自平衡的树就叫做平衡树。

平衡树

平衡树，是指插入、删除元素后可以自平衡的二叉查找树。我们平衡的手段，就是旋转。

平衡这个概念一直都有，直到62年，发明了第一种平衡树—-AVL树。

严格来说，平衡树是指可以自平衡的二叉查找树，关键词就是：自平衡、二叉、查找（有序）。

AVL树

AVL树是指任意节点的两个子树的高度差不超过1的平衡树。

当数据量非常多的时候，你会非常难以判断这是否是一颗AVL树，比如

如果把上面看成一颗二叉排序树，他是一颗AVL树，其实你很难一眼就看出来他是一颗AVL树，这就是AVL树的第一个缺点，不够直观，特别是当结点特别多的时候。

第二个缺点就是，在插入和删除的时候自平衡的过程非常的复杂。

基于这些缺点，所以，后来又发展出来了各种各样的神奇的平衡树。

多路平衡二叉树

索引

一般来说，我们操作的数据都是存储在内存（CPU）中的，但如若我们要操作的数据集非常大，大到内存已经没办法处理了怎么办呢？如数据库中的上千万条记录的数据表、硬盘中的上万个文件等，他们必然不能都存储在内存中，而是存储在外存中的。

对于外存中的数据，常见如数据库，我们通常通过索引表来进行数据查找和交互，一般来说，索引表本身也很大，因为数据库的数据非常多，因此索引也不可能全部存储在内存中，因此索引表往往也是以索引文件的形式存储的磁盘上。Mysql的MyISAM引擎的索引文件和数据文件是分离的，一张数据库表就有它对应的索引表，索引表中一个索引对应一条数据库记录的磁盘地址，内存中发起请求通过指定索引的查找索引表即可定位唯一的一条数据；当然Mysql的InnoDB引擎的索引表也是数据表，即索引表保存了索引和完整的数据记录。但是不管怎么说数据的查找都会依赖索引，并且建议通过索引查找，因为如果没有走索引，那就会走全表扫描，使得查找效率大大降低。 因为索引文件同样存储在磁盘上，这样的话，索引查找过程中每查找一次就要产生一次磁盘I/O消耗，相对于CPU存取，I/O存取的消耗要高几个数量级，访问磁盘的成本大概是访问内存的十万倍左右。

实际上，考虑到磁盘IO是非常高昂的操作，计算机操作已经系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。

每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k大小的连续磁盘块，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助，通常，索引节点的大小被设计为一页的大小。

多路平衡查找树

对于一旦涉及到这样的外部存储设备（外存），关于时间复杂度的计算就会发生变化，访问某个表/集合元素的时间已经不仅仅是寻找该元素所需比较次数的函数，我们必须考虑对硬盘IO进行操作的时间。由于IO耗时远大于CPU耗时，所以此处评价一个数据结构作为索引的优劣最重要的指标就是要尽量减少查找过程中磁盘IO的存取次数。

我们之前谈的树，都是一个节点可以有多个孩子，但是它自身只存储一个元素。二叉树限制更多，节点最多只能有两个孩子。一个节点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大（节点拥有子树的个数的最大值），要么树的高度非常大，甚至两者都必须足够大才行，这就使得IO次数非常多，这显然成了时间效率上的瓶颈，并且由于一次IO读取一个节点的数据，普通二叉树并不能容纳更多的数据，这样又造成了磁盘块空间的浪费。

以上种种限制迫使我们设计出每一个节点可以存储多个元素，并且数据结构的高度可控的数据结构，为此引入了多路查找树的概念。一颗平衡多路查找树同样可以使得数据的查找效率保证在O(logN)这样的对数级别上，此时底数为叉数或者阶。

多路查找树（muitl-way search tree），其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。由于它是一颗平衡查找树，所有元素之间存在某种特定的排序关系。在这里，每一个节点可以存储多少个元素，以及它的孩子数的多少是非常关键的。

2-3树

因为AVL树所带来的搜索性能的提升，不足以弥补平衡树所带来的性能损耗。所以，就开始思考，有没有一种绝对平衡的树。没有高度差，没有高度差就没有平衡因子，没有平衡因子就没有旋转操作。

随着这种思考，衍生出了2-3树。也就是二叉-三叉树。

2-3树就是一种绝对平衡的树，任意节点到它所有的叶子结点的深度都是相等的。

定义

一颗2-3树或为一颗空树，或有以下结点组成：

2-节点：含有一个元素和两个子树，左子树的所有元素的值均小于它的父结点，右子树所有元素的值均大于它的父结点。

3-节点：还有两个元素和三个子树（左中右 子树），左子树所有元素的值均小于它的父结点，中子树所有元素的值都位于父结点两个元素之间，右子树所有元素的值均大于它的父结点。

2-3树查找元素

2-3树的查找类似于二分，根据元素的大小来决定来决定查找的方向。要判断一个元素是否存在，我们就要先将待查找元素和根元素比较，如果他和任意一个相等，那查找命中，否则根据比较结果来选择查找方向。

2-3树插入元素

插入元素首先进行查找命中。若查找命中则不插此元素。如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中，则在叶子结点中插入这个元素。

空树的插入很简单，创建一个结点就可以了。如果不是空树，插入又分成了四种情况：

1、向2-结点中插入元素

2、向一颗只含有一个3-节点的树中插入元素

如果命中查找结束于3-节点，先临时将其成为4-节点，把待插入元素添加到其中，然后将4-节点转化为3个2-节点，中间的节点成为左右节点的父节点。如果之前临时4-节点有父节点，就会变成向一个父节点为2-节点的3-节点中插入元素，中间节点与父节点为2-节点的合并。

3、向一个父结点为2-节点的3-节点中插入元素

同前者

4、向一个父结点为3-节点的3-节点中插入元素

插入元素后一直向上分解临时的4-节点，直到遇到2-节点的父节点变成3-节点不再分解。如果达到树根节点还是4-节点，则进行分解根节点，此时树高+1（只有分解根节点才会增加树高），下面动画2-3树插入会出这个例子。

2-3树的删除操作

2-3树的删除也分为三种情况，与插入相反。

1、当删除元素为于3-节点的叶子结点上

只需要删除该元素即可，不会影响到整棵树的其他结点结构。

2、当删除元素位于非叶子结点

使用中序遍历找到待删除节点的后继节点，然后将后继节点与待删除节点位置互换，此时就将问题转化为删除节点为叶子节点（平衡树的非叶子节点中序遍历后继节点肯定是叶子节点），如果该叶子是3-节点，则跟情况（1）一样，如果该节点是2-节点，则跟后面的情况（3）一样；

3、当删除元素位于2-结点的叶子结点上

删除元素2-结点的叶子结点的步骤相对很复杂，删除后需要做出相应的判断。并根据判断结果调整树的结构。

1、删除结点为2结点，父结点为2结点，兄弟结点为3结点。

操作步骤：当前待删除节点的父节点是2-节点、兄弟节点是3-节点，将父节点移动到当前待删除节点位置，再将兄弟节点中最接近当前位置的key移动到父节点中。

2、删除结点为2-结点，父结点为2-结点，兄弟结点为2-结点

操作步骤：当前待删除节点的父节点是2-节点、兄弟节点也是2-节点，先通过移动兄弟节点的中序遍历直接后驱到兄弟节点，以使兄弟节点变为3-节点；

删除结点4位2-结点，兄弟结点7也为2结点，需要中序遍历得到兄弟结点7的直接后继8，然后结点7和8构成3-结点。

重复1情况

3、删除结点为2-结点，父结点为3-结点

操作步骤：当前待删除节点的父节点是3-节点，拆分父节点使其成为2-节点，再将再将父节点中最接近的一个拆分key与中孩子合并，将合并后的节点作为当前节点。

2-3树为满二叉树，删除叶子结点

2-3 树作为一种平衡查找树，查询效率比普通的二叉排序树要稳定许多。但是2-3树需要维护两种不同类型的结点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。

可以看到，上面自平衡的过程中，出现了一种节点，它具有四个子节点和三个数据元素，这个节点可以称作4节点，如果把4节点当作是可以允许存在的，那么，就出现了另一种树：2-3-4树。

2-3-4树

2-3-4树，它的每个非叶子节点，要么是2节点，要么是3节点，要么是4节点，且可以自平衡，所以称作2-3-4树。

2节点、3节点、4节点的定义在上面已经提及，我们再重申一下：

2节点：包含两个子节点和一个数据元素；

3节点：包含三个子节点和两个数据元素；

4节点：包含四个子节点和三个数据元素；

插入M，依旧符合2-3-4树的规则。在插入N呢？

插入N，L上移。

F上移

是不是挺简单的，至少比AVL树那种左旋右旋简单得多。同样地，在2-3-4树自平衡的过程中出现了临时的5节点，所以，如果允许5节点的存在呢？嗯，2-3-4-5树由此诞生！同样地，还有2-3-4-5-6树、2-3-4-5-6-7树……子子孙孙，无穷尽也~所以，有人就把这一类树归纳为一个新的名字：B树。

B树

B树，表示的是一类树，它允许一个节点可以有多于两个子节点，同时，也是自平衡的，叶子节点的高度都是相同的。所以，为了更好地区分一颗B树到底属于哪一类树，我们给它一个新的属性：度（Degree）。具有度为3的B树，表示一个节点最多有三个子节点，也就是2-3树的定义。具有度为4的B树，表示一个节点最多有四个子节点，也就是2-3-4树的定义。

B树，一个节点可以存储多个元素，有利于缓存磁盘数据，整体的时间复杂度趋向于O(log n)，原理也比较简单，所以，经常用于数据库的索引，包括早期的mysql也是使用B树来作为索引的。但是，B树有个大缺陷，比如，我要按范围查找元素，以上面的2-3-4树为例，查找大于B且小于K的所有元素，该怎么实现呢？很难，几乎无解，所以，后面又出现替代B树的方案：B+树。当然了，B+树不是本节的重点，本节的重点是红黑树。 来了来了，有意思的红黑树来了

红黑树

我们先用图来体会

我可以跟大家说，这棵树，就是一颗红黑树。红黑树就是2-3-4树。

我们知道2-3-4的插入、删除、查找元素的原理是相当简单的，那么，我们是不是可以利用2-3-4树来记忆红黑树呢？答案是肯定的，我们就来看看如何利用2-3-4树来快速掌握红黑树，再也不用死记硬背了

现在，我们来看一看红黑树的精髓所在，我们来看一看，什么是红黑树的黑高，为什么要有红黑树，红黑树的旋转跟AVL有什么区别，如何去选择？红黑树是如何保持平衡的？直接进入正题

什么是红黑树

红黑树是一颗自平衡的二叉排序树，树上的每一个结点都遵循下面的规则（特别注意，这里的自平衡和平衡二叉树AVL的高度有区别）。我们再来看一看红黑树的定义：

1、每一个结点都有一个颜色，要么是红色，要么是黑色。

2、树的根结点为黑色

3、树中不存在两个相邻的红色节点（红色节点的父结点和孩子结点均不为黑色）

4、从任意一个结点出发，包括根结点，到其任何后代NULL结点（默认都是黑色啊）的每条路径都具有相同数量的黑色结点。

这就是一颗典型的红黑树，树中的每个结点的颜色要么是黑色，要么是红色；根结点 6 为黑色结点；树中不存在两个相邻的红色结点，比如结点 15 为红色结点，其父亲节点 6 与两个孩子结点就一定是黑色，而不能是红色； 从结点到其后代的 NUll结点 的每条路径上具有相同数目的黑色结点，比如根结点 6 到其左子树的 NULL结点 包含三个黑色结点，到其右子树所有的 NULL 结点也包含三个黑色结点。 可能还不够清晰，为此我对上图做了修改为所有默认为黑色的 NULL 结点给了一个标记。

现在解释规则的第四条简直不能再清晰了！比如根结点 6 到 NULL结点 a 的路径 6→2→a 上的黑色结点为 3 个，从根结点 6 到结点 c 的路径 6→15→10→9→c 中包含的黑色结点个数也是 3 个，同理从根结点 6 到其他所有 NULL结点 的黑色结点数都是 3 。再举个栗子，从红色结点 15 到NULL结点 d 的路径 15→18→g 包含 2 个黑色结点，到NULL结点 c 的路径 15→10→9→c 也包含黑色结点 2 个，从结点 15 到其所有后代的 NULL结点的 黑色结点数目都是 2 。

为什么要有红黑树

大多数二叉排序树BST的操作（查找、最大值、最小值、插入、删除等等）都是O（h）的时间复杂度，h 为树的高度。但是对于斜树而言（BST极端情况下出现），BST的这些操作的时间复杂度将达到O（n），n就是结点数。为了保证BST的所有操作的时间复杂度的上限为O（logn） ，就要想办法把一颗BST树的高度一直维持在logn，而红黑树就做到了这一点，红黑树的高度始终都维持在logn，n 为树中的顶点数目。

这个时候就有一个疑问，不对啊。AVL树不也始终是一个均值么？

红黑树RBT与平衡二叉树AVL的比较

AVL 树比红黑树更加平衡，但AVL树在插入和删除的时候也会存在大量的旋转操作。所以当你的应用涉及到频繁的插入和删除操作，切记放弃AVL树，选择性能更好的红黑树；当然，如果你的应用中涉及的插入和删除操作并不频繁，而是查找操作相对更频繁，那么就优先选择 AVL 树进行实现。

一颗红黑树到底是如何保持平衡的呢？

举一个很简单但是很经典的例子，包含三个结点的单链是不可能出现在红黑树当中的。关于这一点，我们可以自己绘制一条单链，然后尝试为其着色，来判断。

从上图中可以发现，将根结点 9 涂黑色，其他结点分四种情况着色，结果都不满足红黑树的性质要求。唯一的办法就是调整树的高度

这就算我们对于红黑树的初探，然后我们来看两个重要的概念。

什么是一颗红黑树的黑高？

在一颗红黑树中，从某个结点 x 出发（不包含该结点）到达一个叶结点的任意一条简单路径上包含的黑色结点的数目称为 黑高 ，记为 bh(x) 。所以我们发现，其实6和15的黑高是一样的，都是2。

计算结点 6 的黑高，从结点 6 到结点 c 的路径是 6→15→10→9→c ，其中黑色结点为 6、10、c ，但是在计算黑高时，并不包含结点本身，所以从结点 6 到结点 c 的路径上的黑色结点个数为 2 ，那么 bh(6)=2 ；从结点 15 到结点 c 的路径为 15→10→9→c ，其中黑色结点为 10、c ，所以从结点 15 到结点 c 的路径上黑色结点数目为 2 ，bh(15)=2 。

因为红黑树的黑高为其根结点的黑高。所以根据红黑树的性质3和性质4，一颗红黑树的黑高bh一定>= h/2。

1 2 3	Number of nodes from a node to its farthest descendant leaf is no more than twice as the number of nodes to the nearest descendant leaf. 从一个结点到其最远的后代叶结点的顶点数目不会超过从该结点到其最近的叶结点的结点数目的两倍。

Copy

其中黑高 bh 就表示从根结点 6 到离它最近的叶结点 2 包含的结点数 2 ，而 h 则表示从根结点 6 到其最远的叶结点 9 所包含的结点数目 4 ，显然这一公式是合理的。

引出来一个道理：一颗有n个结点的红黑树的高度h<=2lg(n+1)。

这就合并成了一颗2-3-4树，这棵树中的每一个结点有2、3、4个孩子结点，而一颗2-3-4树的叶结点有着相同的深度h‘。

也正是基于这个，所以对于有n个结点的红黑树而言，不论查找、删除、最大值、最小值等等的时间复杂都平均下来了，也就是O（logn）。

红黑树的插入

其实红黑树的操作也很简单，就是比AVL多了一个着色的操作。

在AVL中，我们通过左旋和右旋来调整由于插入和删除所造成的不平衡的问题。在红黑树中，我们使用两种方式：

1、重新着色

2、旋转

当红黑树中出现不平衡的状态，我们首先会考虑重新着色，如果重新着色依旧不能使红黑树平衡，那么就考虑旋转。插入操作主要有两种情况，具体取决于叔叔结点的颜色。如果叔叔结点是红色的，我们会重新着色。如果叔叔结点是黑色的，我们会旋转或者重新着色，或者两者都考虑。

假设x是新插入的一个结点。

1、进行标准的BST插入并将新插入的结点设置为红色

2、如果x是根结点，将x的颜色转化为黑色（整棵树的黑高增加1）

3、如果x的父结点p不是黑色并且x不是根结点，则：

1）、如果x的叔叔结点u是红色；

2）、如果x的叔叔结点u是黑色，则对于x、x的父结点p和x的爷爷结点g有四种情况：

1 2 3 4 5 6 7 8 9 10 11 12 13	LL（p是g的左孩子且x是p的左孩子） LR（P是g的右孩子且x是p的右孩子） RR（p是g的右孩子且x是p的右孩子） RL（p是g的右孩子且x是p的左孩子） 将插入结点x的父结点p和叔叔结点u的颜色变成黑色 将x的爷爷结点g设置为红色 将g看作是x，对于新的x重复2、3两步

Copy

插入结点x的叔叔结点u是红色

对于新插入结点 x，我们执行标准的 BST 插入之后，将插入结点 x 着色为红色；如果插入结点不是根结点，且x的父结点 p 为红色结点，分为 1) 和 2) 两种情况处理，我们先看的是 1) 的情况：x 的叔叔结点 u 为红色，如下图所示：

第一步：将父亲结点p和叔叔结点u都设置为黑色

第二步：将g的颜色设置为红色

第三步：针对于g结点，在执行第二，第三步。

插入结点x的叔叔结点u为黑色

当插入结点x的叔叔结点为黑色的时候，根据插入接待你x、x的父结点p和x的爷爷结点g可能出现的位置关系，分为四种情况。

LL

LR

首先通过左旋p转化为LL的情况：

然后按照LL的情况处理：

RR

RL

先右旋转化成RR的情况

然后按照RR的情况处理

到这里，插入排序就全部讲完了。但我也知道很多人可能会有疑惑，那就让我们来构造一颗红黑树，看看运用上述规则到底是否适用。

红黑树插入操作示例

下面就带大家构造一颗稍微复杂一点儿的红黑树：

初始时，我们已知的插入依次插入：

第一步：插入结点2，结点2就是根结点，设置为黑色：

第二步：插入结点6，首先执行标准的BST插入操作并将结点6设置为红色，但6号结点的父结点为2的颜色为黑色，所以什么都不用做。

第三步：插入结点9，执行BST插入，设置为红色。其父结点6颜色为红色，且叔叔结点null为黑色，属于RR的情况。故对其爷爷结点2进行左旋操作，并交换g和p的颜色。

第四步：插入结点 10，执行标准的 BST 插入操作并设置为红色，其父结点 9为红色，其叔叔结点 2为红色结点，将其父结点 9 和叔叔结点涂黑色，并将其爷爷结点涂红色并设置为新的x，判断其爷爷结点 6 ，发现为根结点，重新更新为黑色。

第五步：插入结点 12，执行标准的BST插入操作并设置为红色，其父结点 10为红色，其叔叔结点为黑色，其爷爷结点 9为红色，RR 的情况，则左旋 g ，交换 g 和 p 的颜色。

第六步：插入结点15

第七步：插入20

第八步：插入18

第九步：插入结点1

第十步：插入结点5

第十一步：插入结点13

红黑树的删除

说起红黑树的删除操作，就不得不提我们讲的红黑树的插入。与红黑树的插入操作类似，红黑树的删除也是重新着色和旋转来保证每一次删除操作后依旧满足红黑树的属性。

在插入操作中，通过判断插入结点 x 的叔叔结点 u 的颜色来确定恰当的平衡操作。而删除操作中，是通过检查兄弟结点的颜色来决定恰当的平衡操作。 红黑树中插入一个结点最容易出现两个连续的红色结点，违背红黑树的性质3（红黑树中不存在两个相邻的红色结点）。而删除操作，最容易造成子树黑高（Black Height）的变化（删除黑色结点可能导致根结点到叶结点黑色结点的数目减少，即黑高降低）。 与插入操作相比，红黑树的删除操作相对复杂一点，但多点儿耐心，还是没有问题的。为了理解删除操作，我们先来看一个 双黑（Double Black） 的概念。

当删除结点 v 是黑色结点，且其被其黑色子节点替换时，其子结点就被标记为 双黑。

所以说，删除操作最主要的任务就是将转化为双黑结点转换为我们普通的黑色结点。

删除操作总纲

删除操作总体上分为三步，我们先提高挈领地看一下，有个宏观概念，然后步步为营，攻陷删除。

首先我们假定要删除的结点为 v ，u 是用来替换 v 的孩子结点（注意，当 v 是叶结点时， u 是 NULL结点，且NULL结点我们还是当做黑色结点处理）。

删除操作总纲：

1、执行标准的BST的删除操作

2、简单情况：u或者v时红色

3、复杂情况：u和v都是黑色

1）u是双黑结点

2）当前结点u是双黑结点且不是根结点

a）u的兄弟结点s是黑色且s的孩子结点至少有一个是红色（LL、LR、RR、RL）

b）u的兄弟结点s是黑色且它的两个孩子都是黑色

c）u的兄弟结点s是红色（s是其父结点p的左孩子、s是其父结点的右孩子）

3）当前结点u是双黑结点且是根结点

1、执行标准的BST删除操作

在标准的 BST 删除操作中，我们最终都会以删除一个叶子结点或者只有一个孩子的结点而结束（对于内部节点，就是要删除结点左右孩子都存在的情况，最终都会退化到删除结点是叶子结点或者是只有一个孩子的情况）。所以我们仅需要处理被删除结点是叶结点或者仅有一个孩子的情况。

2、简单情况：u或者v是红色

如果 u 或者 v 是红色，我们将替换结点 v 的结点 u 标记为黑色结点（这样黑高就不会变化）。注意这里是 u 或者 v 是红色结点，因为在一棵红黑树中，是不允许有两个相邻的红色结点的，而结点 v 是结点 u 的父结点，因此只能是 u 或者 v 是红色结点。

删除结点 v 为黑色结点 10 ，替换结点 v 的结点 u 为红色结点 9 的情况：

删除结点v为红色结点20，替换结点v的结点u为黑色NULL结点的情况：

3、复杂情况 u和v都是黑色结点

3.1 结点u是双黑结点

当要删除结点 v 和孩子结点 u 都是黑色结点，删除结点 v ，导致结点 u 变为双黑结点。当 u 变成双黑结点时，我们的主要任务将变成将该双黑结点 u 变成普通的单黑结点。一定要特别注意，我们在上篇就提到的，NULL结点为黑色结点 ， 所以删除黑色的叶子结点就会产生一个双黑结点。

3.2 当前结点u是双黑结点且不是根结点

当前结点 u 是双黑结点且不是根结点，又包含三种情况进行处理。我们约定结点 u 的兄弟结点为 s .

u的兄弟结点s是黑色且s的孩子结点至少有一个是红色

对于这种情况，需要对 u 的兄弟结点 s 进行旋转操作，我们将 s 的一个红色子结点用 r 表示，u 和 s 的父结点用 p 表示，那么结点 p 、s 和 r 的位置将出现以下四种情况（LL、LR、RR、RL）。

LL（s 是 p 的左孩子，r 是 s 的左孩子，或者 s 的两个孩子都是红色结点）：

我们删除下图中的结点 25 为例进行说明：

删除结点 25 ，用结点 25 的NULL结点 替换结点 25 ，产生一个双黑结点 u ，双黑结点 u 的兄弟结点 s 为 15 ，结点 s 是其父结点 20（p） 的左孩子，其左孩子 10（r） 正好是红色结点。即为 LL 情况。

s 的左孩子 r 颜色设置为 s 的颜色，s 的颜色设置为父结点 p 的颜色，然后右旋p结点。

LR（s是p的左孩子，r是s的右孩子，或者s的两个孩子都是红色）

删除结点25，不过结点25的兄弟结点15只有一个右孩子18

将结点r的颜色设置为p的颜色。

左旋结点15（s）

右旋结点20（p），p的颜色设置为黑色，双黑变单黑

RR（s 是 p 的右孩子，r 是 s 的右孩子，或者 s 的两个孩子都是红色结点）： 删除结点 2 ，用结点 2 的NULL结点 a 替换结点 2 ，产生一个双黑结点 u ，双黑结点 u 的兄弟结点 s 为 15 ，结点 s 是其父结点 6（p） 的右孩子，其右孩子 18（r） 正好是红色结点。即为 RR 情况（仔细观察其实和 LL 情况是对称的）。

r的颜色变为s的颜色，s的颜色变为p的颜色。

左旋p，p的颜色设置为黑色，双黑变单黑

RL情况（s 是 p 的右孩子，r 是 s 的左孩子，或者 s 的两个孩子都是红色结点）： 该情况与 LR情况是对称的

结点r的颜色变为p的颜色

右旋结点15

左旋结点6（p），p的颜色设置为黑色，双黑变单黑

u 的兄弟结点 s 是黑色且 s 的两个孩子结点都是黑色

对于这种情况需要递归地进行处理，如果删除结点后得到的双黑结点的父结点此时为黑色，则结点 u 变单黑，且结点 u 的父结点 p 变双黑，然后对结点 u 的父结点 p 继续进行处理，直到当前处理的双黑结点的父结点为红色结点，此时将双黑结点的父结点设置为黑色，双黑结点变为单黑结点（红色 + 双黑 = 单黑）。

假设以 10 为根结点的子树为整棵树的左子树，删除结点 9 ，产生双黑结点 c 且其兄弟结点 12（s） 为黑色，兄弟结点的左右孩子均为黑色。

此时双黑结点的兄弟结点 12 变为红色结点，然后将 u 的父结点 10 变为双黑结点，一直向上判断。

那么这个过程什么时候结束呢？

如下图，删除结点12，得到一个双黑结点u，双黑结点的兄弟结点31及兄弟结点的孩子结点均为黑色，且双黑结点的父结点19为红色结点，刚好是不再继续向上判断的情况：

此时只需要将结点 u 的兄弟结点 31 的颜色变为红色，双黑结点 u 的父结点 19 由红色变为黑色结点，双黑结点 u 变为单黑结点。

u的兄弟结点s是红色结点

当前 u 的兄弟结点 s 是红色结点时，通过旋转操作将 u 当前的兄弟结点向上移动，并对 u 的父结点和其旋转前的兄弟结点重新着色，接着继续对结点 u 旋转后的兄弟结点 s 进行判断，确定相应的平衡操作。旋转操作将 u 的兄弟结点情况又会转换为前面刚提到的3.2（a）和（b）的情况。根据兄弟结点 s 是父结点 p 的左右孩子又分为两种情况。

情况一：u 的兄弟结点 s 是父结点 p 的左孩子 ,对结点 p 进行右旋操作。

删除结点 18 ，产生一个双黑结点 u ，且 u 的兄弟结点 s 是红色，兄弟结点 s 是其父结点的左孩子，接着就是对其父结点 15 进行右旋操作。

对结点 15 进行右旋操作，并且对旋转前的 p 和 s 进行重新着色后，继续对双黑结点旋转后的兄弟结点进行判断，发现此时正好和 3.2（b）的情况是一样，进行相应处理，如下图所示。

情况二：u 的兄弟结点 s 是父结点 p 的左孩子 ,对结点 p 进行左旋操作（这种情况与上面的是对称的）。

删除结点 6 ，产生一个双黑结点 u ，且 u 的兄弟结点 10（s） 为红色，s 是父结点 p 的右孩子，左旋P

对双黑结点 u 旋转后的兄弟结点继续判断：

3.3 当前结点u是双黑结点且是根结点

当前结点 u 是双黑结点且是根结点时，直接将双黑结点变为单黑结点，整颗红黑树的黑高减 1.

红黑树与AVL树的比较

红黑树中的每个结点需要一个存储位表示结点的颜色，可以是红或黑。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保对于每一个结点其到叶子结点的最长路径不会超过最短路径的两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同结点的情况下，AVL树的高度<=红黑树），相对于要求严格的AVL树来说，它的旋转次数少，所以对于插入，删除操作较多的情况下，使用红黑树。

来自一年后的补充:
红黑树的逻辑操作，第一次啃需要很长时间，啃下来之后长时间不复习，也很容易忘记，真正熟练的理解红黑树的详细逻辑是有一定困难的，而有时候不需要在这些地方上浪费太多的时间。（几乎忘得一干二净的我如此补充到