二叉搜索树与红黑树

最近，看 HashMap 的时候，看到了其中的实现用到了红黑树。于是就想来复习一下，老久以前学的东西差不多都忘掉了。

红黑树的本质是二叉搜索树，它的约束条件更多而已。这篇复习笔记首先过一下二叉搜索树，然后再进入红黑树。

BST满足如下三个特性：

在BST中搜索元素的过程类似于二分法，从根节点开始， 小于 根节点从 左 边搜索， 大于 根节点则从 右 边搜索。以这个原则不断搜索即可找到目标。

看起来BST算是比较优秀对吧，但是呢，假如我们遇到下面这棵BST：

这种情况一下去搜索 5 ，那么时间复杂度就为n，相当于对所有元素都遍历了一遍（这正是 红黑树 会避免的一个缺点，红黑树后面会详细讲到）。

上面简单介绍了BST的基本性质，以及其搜索算法，下面会介绍它的插入节点的算法和删除节点的算法。

向树 b 插入新的节点 n 时，过程如下：

重复以上步骤，最终新节点会插入到树中，并且始终会落到叶子节点上。

若想从BST中删除节点n，有下面的几种情况：

听起来比较绕，结合下图来理解就比较简单了。

BST在删除、插入、搜索的复杂度等于树高，最坏的情况下复杂度为 O(n) ，平均的复杂度为 O(logn) 。这个平均复杂度是怎么去算的呢？我是这么去理解的：

对于一棵是完全二叉树的BST，进行搜索时，搜索次数 k 与节点数 n 满足如下关系

当 n/2^k = 1 时已经搜索到了叶子节点，于是计算得到

上面我们讲到了，BST的深度可能为 n ，这种情况下去搜索和顺序搜索没有区别。于是 鲁道夫·拜尔 发明了一种自平衡二叉搜索树。

红黑树在满足二叉搜索树的特性之外，还增减了5个特性：

下面是一个具体的图例

正是这几个特性确保了红黑树的关键特性： 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长 。所以红黑树的查找性能教于BST是更高效的。

关键特性可以这么理解得来：最短路径可能全是黑色节点，由于特性4就会导致最长路径上不会有两个连续的红色的点，红色节点最多的情况也只能是一个红色一个黑色相间这样，所以这条最长路径的长度不会多于最短路径长度的2倍。

对于搜索而言，BST和红黑树是一样的，但是插入和删除节点红黑树会更加复杂一些。下面对插入和删除操作进行详细讲解。

插入新的节点，首先会默认它是红色，假若将其设置为黑色，就会导致这条路径上多出一个黑色节点，这样会非常难以调整。在插入的节点的过程中， 性质1 和 性质3 总是保持着。

删除节点一共有5中情形：

情形1： 新节点 n 位于树的根上，直接将其绘制为黑色即可。

情形2： 新节点 n 的父节点 p 为黑色，无需做调整。

情形3： 新节点 n 的父节点 p 和叔父节点 u 都是红色，我们可以把 p 和 u 设置为红色并将 n 的祖父节点 g 设置为红色（用来保证性质5）。但是 g 可能为根节点或者 g 的父节点也为红色，所以此时还需要假设 g 为新增的节点进行各种情况的检查。

情形4： 新节点 n 的父节点 p 是红色而叔父节点 u 是黑色或者缺少，这种情形下分为了两种情形。

1 若新节点 n 是其父节点 p 的右子节点且父节点 p 又是其父节点 g 的左子节点，这种情况下，需要 左旋转 调换新节点 n 和其父节点 p 的角色，但是此时 p 又违背了性质4，所以接着需要以 情形5 处理 p 。

2 这种情况与上面一种情况恰好相反，若新节点 n 是其父节点 p 的左子节点且父节点 p 又是其父节点 g 的右子节点，需要 右旋转 调换新节点 n 和其父节点 p 的角色，同样需要以 情形5 处理 p 。

情形5： 若新节点 n 的父节点 p 是红色，其叔父节点 u 是黑色或者缺少，这种情形下也分为了两种情况。

1 新节点 n 是其父节点 p 的左子节点，且父节点 p 又是其父节点 g 左子节点。在这种情况下，由 性质4 我们知道 g 只能为黑色，此时我们对 g 进行一次 右旋转 ，并交换父节点 p 和祖父节点 g 的颜色，于是就能够满足 性质4 和 性质5 。

2 类似地，这种情况与上述的情况相反： 新节点 n 是其父节点 p 的右子节点，且父节点 p 又是其父节点 g 右子节点，此时我们对 g 进行 左旋转 ，同样也需要交换父节点 p 和祖父节点 g 的颜色。

以上就是插入新节点的5种情形。

关于删除节点，能够保证 如果删除节点有两个儿子，可以化解成删除另一个只有一个儿子节点的问题。

又因为如果删除的节点没有儿子节点，只需要将下面任意一个nil节点上移替换待删除的节点，所以下面我们只需要讨论 删除只有一个儿子节点的问题。

我们首先讨论两种比较简单的情形。

需要进一步讨论的情形是被删除节点及它的儿子节点两者都是黑色。 我们首先要把删除的节点替换为它的儿子，现在我们称呼顶替上来的这个儿子节点为 n ，称呼它的父亲为 p ，它的兄弟为 s ， s 的左右儿子节点分别为： sl ， sr 。因为删除了一个黑色节点，树需要重新平衡，有下面几种情形需要考虑。

情形1： n 是新的根。这种情况，无需再进行处理了，所有性质都得以保证。

注意 ：在情形2, 5, 6下，我们假定 n 是它的父亲的左儿子。假如 n 是右儿子，则这些情形下的左和右应该对调。

情形2 ： s 为红色，这种情形下我们对 p 进行 左旋转 ，并调换 p 和 s 的颜色。这样处理之后， n 和 sl 成为了兄弟节点， n 到 p 的路径上是已经删除了一个黑色节点，让 sl 直接成为 n 的兄弟节点肯定是不平衡的，会违背 性质5 。所以接着需要按照 情形4 ， 情形5 或 情形6 来处理。

情形3： n 的父亲、 s 和 s 的儿子都是黑色。这种情形下，我们重绘 s 为红色。通过 s 的所有路径都少了一个黑色节点，另外从 n 到 p 的路径也少了一个黑色节点， p 这棵子树是已经平衡了，但是还有其它没有经过 p 的路径就会多出一个黑色节点，所以仍然是不平衡的，需要从 情形1 开始，对 p 做重新平衡。

情形4： s 和 s 的儿子都是黑色， 但是 p 为红色，这种情况下，我们交换 p 和 s 的颜色，这样不会影响不通过 n 的路径上黑色节点的个数，同时通过 n 的路径上的黑色节点又补上来一个，树已经平衡。

情形5： n 是它父亲的左儿子， s 是黑色， sl 红色， sr 黑色。这种情形下我们在 s 上做右旋转，并交换 s 和 sl 的颜色。所有路径的黑色节点个数都没有变，通过 n 的路径仍然缺少一个黑色节点，所以需要进一步进入 情形6 。

情形6： n 是它父亲的左儿子， s 是黑色， s 的右儿子是红色。在这种情况下，我们在 p 上做左旋转，并交换 p 和 s 的颜色，并将 sr 置为黑色。现在的情况是，无论 p 的初始颜色是红色还是黑色，通过 n 的路径都增加了一个黑色节点。

此时，如果一个路径不通过 n ，有如下两种情况：

至此，树已经达到平衡状态。

终于是理清楚了，红黑树的插入和删除操作还是比较复杂，但是一步步去理解也是行得通的，记录该文便于后期查阅和复习。

另外，本文参考了 维基百科红黑树 ，它上面讲得非常细致。

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。

性质1: 每个节点要么是 黑色 ,要么是 红色 。

性质2: 根节点是 黑色 。

性质3: 每个叶子节点(NIL)是黑色。

性质4: 每个 红色 节点的两个子节点一定都是 黑色 。

性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 !

从性质5又可以推出:

性质51: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。

插入操作包括两部分工作:

注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。

最简单的一种情景,直接把插入结点作为根结点就行

注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。

处理: 更新当前结点的值,为插入结点的值

由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。

依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点

因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红

处理:

1将P和U结点改为黑色

2将PP改为红色

3将PP设置为当前结点,进行后序处理

注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。

处理:

处理:

该情景对应情景42,只是方向反转,直接看图

处理:

处理:

普通的二叉搜索树在最坏的情况下，可能退化成一个链表。而又因为二叉搜索树的所有操作的性能（添加，删除，查找等），与二叉搜索树的高度有关。在最坏的情况下，二叉搜索树的高度和元素个数相同，此时二叉搜索树的效率降为了O(n)级别。

所以为了防止我们的二叉搜索树退化成一个链表，就产生了 平衡二叉树 。 平衡二叉树 可以保证它的左右两个子树的高度差不会超过1。平衡二叉树有很多实现，一个经典实现就是 红黑树 。

在红黑树中将树中的节点划分为两种状态，分别用黑色和红色来表示。

红黑树为了保证自己能够平衡子树，所以制订以下五个规则：

1、每个节点必须有颜色，要么黑色，要么红色，没有别的颜色。

2、根节点必须是黑色

3、所有的空节点(nil节点)都认为是黑色节点。

4、红色的节点不能连续，即一个红色的节点，它的父节点和子节点不能也是红色的，

5、无论从哪一个节点起始，到它每个叶子节点的路径中，黑色节点数量必须相同。

在对红黑树进行添加、删除等操作之后，必须使红黑树符合这5个规则。

那么问题来了，在添加删除操作之后，树中节点的数量都变了，是怎么保证整个树满足上述这些规则呢？

这里涉及到3种操作， 变色 、 左旋 和 右旋 。通过这个三种操作，在增删节点之后调整树的形状结构，使它满足上述5个规则。这也是红黑树能保持平衡的原因。

变色操作 我们在下文的添加、删除节点的实际操作中，再进行在描述。

先来说一下左右旋。

文字描述一下就是，2的右孩子节点4，变为了2的父节点，2由父节点变为4的左孩子。同时，4原来的左孩子变为2的右孩子。

右旋与左旋相反，即以某节点为支点进行顺时针旋转。同样，我们看下图，是以5为支点进行的右旋:

文字描述同样反过来，5的左孩子节点3，变为5的父节点，5由父节点变为3的右孩子。3原来的右孩子变为5的左孩子。

首先是在树中找到新节点正确的位置，寻找位置的过程与普通的二叉搜索树相同，只是将新插入的节点默认为 红色节点 。为什么默认为红色？因为如果你将新节点默认为黑色，则插入后肯定会打破原本符合规则的红黑树（上述第5条规则）。但是，如果你将新节点定为红色，则有可能不用任何操作就符合红黑树规则，如下图，当新插入的红色节点，它的父亲节点为黑色时候，此时已经满足红黑树规则了。所以用红色比黑色好。

如果很不巧，新插入的节点的父亲节点也为红色，因为红色节点不能连续，所以我们需要调整红黑树的结构使其满足规则。在调整的过程中我们会遇到3种需要处理的情况，我们来一一进行说明。

情况1：

插入新节点40， 此时它的父节点为红色，并且它的叔叔节点（即51）也为红色 。此时我们需要进行 变色 操作。 将该节点的父亲节点、叔叔节点都变为黑色，祖父节点变为红色 。

此时上图已经满足红黑树的规则。但有的时候我们经过了变色操作后，仍不满足红黑树的规则，会遇到下面的情况。

情况2：

如图，我们插入新的节点53，在按情况1的操作变色后，变成了这样:

最后我们说一下情况3的情景，如下图：

我们向树中插入新节点37，在按情况1的操作变色后，变成了这样：

情况3：

3种情况我们说明完了，但是你可能还会有这样的疑问，什么时候进行左旋，什么时候进行右旋；什么时候以父节点为支点旋转，什么时候又以祖父节点为支点旋转？

那么我们可以总结一下，当遇到连续的红色节点应该怎么办： 当前节点我们叫它X，如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置相同，此时，就以祖父节点为支点，进行反向旋转。例如：X为父节点的左孩子，X的父节点同样也是其祖父节点的左孩子，此时以祖父节点为支点进行右旋；

如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置不同，则以X的父节点为支点，进行旋转，旋转方向与X相对于父节点左右位置相反。例如：X为其父节点的左孩子，X的父节点为祖父节点的右孩子，此时以X的父节点为支点进行一次右旋。

在红黑树中删除节点，肯定要涉及到要删的这个节点是红色的还是黑色的。删除红色比较简单，我们先说一下删除红色节点。

删除节点要考虑这个节点所处的位置，所以我们罗列一下红色的节点所有可能的位置情况。

你可能会发现为什么少了一种情况？它不能只有左子树或者只有右子树吗我们可以看下图:

很明显，这四种情况都不符合红黑树的规则，所以根本不会出现这种情况。

而对于既有左子树也有右子树的情况。 我们可以先和普通的二叉搜索树的删除操作一样，将它与前驱或者后继交换一下 。它就又变成第一种情况——成为了一个叶子节点。所以我们只需考虑当它是叶子节点的情况。

接下来我们看一下当要删除的节点是黑色的时候应该怎么办。

同样我们列一下节点位置可能的情况：

第三种情况和删除红色节点时的处理方法一样，可以转换成第一种或第二种情况，所以我们只关心前两种情况。

当要删除的黑色节点只有一个子树时：

最后我们看一下最难处理的一种情况。

要删除的黑色节点是叶子节点时：

情况1：待删除黑色节点20，它的兄弟节点为红色。

操作方法为：将远侄子节点变黑，兄弟节点与父亲节点互换颜色，最后以父节点为支点进行 左旋 。(为什么是左旋？因为待删除的20是左孩子，我们要将左子树长度拉长，将它沉下来，使它变成多余的节点好删除它，如果它是右孩子，则进行右旋)

操作后如下图就完成了。

情况3：待删除黑色节点20，它的兄弟节点为黑色，但它没有红色的远侄子节点(即nil点，记住，nil点算黑色)，只有红色的近侄子节点。

操作后如下图:

此时有了红色的远侄子，就满足了情况2，再按情况2进行一次操作就完成了。

情况4：待删除黑色节点20，它的兄弟节点为黑色，远侄子、近侄子节点都没有。(即两个nil节点，nil节点算黑色)

我们将上图红黑树按流程演示一下:

第一步按情况4操作，将55变红。并将父节点50看做当前节点，继续操作。

此时有关红黑树的知识就说完了。

以上所有内容都为自己查阅资料学习理解之后手敲的。尽量得采用通俗易懂的描述和解释让读者更明白。27张图都是自己亲自画的，花费了四天才写完，如果觉得写的还可以，麻烦点亮喜欢支持一下，如果还是不懂，可以下方留言QQ等****，我亲自告诉你。

红黑树的定义

插入的是红色（因为红黑树的性质中有一条，根节点到任意叶子节点的黑色节点相同，插入红色降低调整概率）

①当父节点是黑色，没有问题，直接插入，不会破坏平衡。

②当父节点是红色，且叔父同色（父节点和叔叔节点颜色相同），此时只需要变色

变色规则：把父和叔同时变成黑色，祖父变成红色，然后再把祖父当做当前节点，继续向上判断颜色，知道平衡

③当父节点是红色，且叔父不同色，这种情况需要旋转加变色处理

一次旋转的情况：左左（右旋），右右（左旋）

什么意思呢？即新节点在父节点的左边，父节点也在祖父节点的左边，此时，只需以父节点为轴，一次右旋转即可。然后根据第②点，修正颜色即可

右右的情况刚好相反，不用赘述

两次旋转的情况：右左（先左旋转，再右旋转），左右（先右旋转，再左旋转）

即插入的新节点是父亲的右节点，而父亲是祖父的左节点，此时，先以父节点为轴，左旋转，左旋之后，情况变成了左左，此时，再以父节点为轴，进行一次右旋，然后根据第②点改变颜色即可达到平衡

左右情况和右左情况相反，操作也正好对称，不再赘述

可以根据上述的规则，随意插入一组数据，来验证是否正确，红黑树生成网址 >

红黑树是处于二叉树和平衡二叉树之间的一种折中方案的算法。说起来红黑树也算是比较难理解的一个数据结构了吧，因为其本身的增删节点，除了左旋右旋还需要变色的复杂操作。

为什么有平衡二叉树这种适合适合查找的数据结构在，还需要红黑树呢？还是先从二叉树说起。

二叉查找树的特点就是 左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

二叉树的查询颇有 二分查找 的思想，如果查询一个节点，n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。为什么说是正常情况，因为上面的树其实不只是二叉树而且还是平衡二叉树。

那如果不正常的情况下，二叉树是啥样的呢？下面是一种退化为类似链表的二叉树的极端情况。这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，类似于在做全表扫描，为了避免这种情况的发生，平衡二叉树在这种情况下登场了。平衡二叉树除了具有二叉树的全部特性外，加了一个规则，就是每个节点的左子树和右子树的高度差至多等于1。

嗯，这样的话就不会出现一棵链表了。平衡二叉树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。这样平衡二叉树对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。平衡二叉树通过 构建、插入、删除、左旋、右旋 等操作来达到平衡。

MySQL索引中 B树和B+树是基于平衡二叉树的进一步改进 。B+树索引按照存储方式的不同分为 聚集索引 和 非聚集索引。

二叉树的算法实现 其实就是要插入的节点都开始和根节点比，小的放节点左边大的右边，如果位置上已经有节点了就再迭代，把当前节点作为根节点来判断放左右，直到有空位置为止。

有了平衡二叉树这么优秀的结构为什么还需要红黑树，因为平衡二叉树要求 每个节点的左子树和右子树的高度差至多等于1 ，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树规则，进而我们都需要通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树。如果频繁增删就会带来性能问题。所以红黑树出现了。

红黑树特性：

1、具有二叉查找树的特点。

2、根节点是黑色的；

3、 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据 。

4、 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。

5、 每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。（限制了高度）

下面是两棵红黑树的例子（黑色的空叶子节点没有画出）：

上面的例子似乎有点平衡二叉树的味道，但它并不是必须满足平衡二叉树的深度差不超过1的条件，如下面的例子。

红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。但与平衡树不同的是，红黑树在插入、删除等操作， 不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整。 意思是查效率相当，但改效率高于平衡树，这也是我们为什么大多数情况下使用红黑树的原因。只不过据说单单在查找方面的效率的话，平衡树会比红黑树快点。

综上，可以说 红黑树是一种不大严格（没有深度差要求）的平衡树 。也可以说是一个折中方案。

那么红黑树如何进行左旋，右旋和变色来达到平衡呢 笔者也还没完全吃透，不过理解了上面的这些应该也够驰骋沙场了。

参考文献：

腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

红黑树旋转

首先按照BST常规算法，执行：r = removeat(x,_hot)

x由孩子r接替 //另一孩子记作w（即黑的NULL）

条件1和2依然满足，但3和4不一定 //在原树中，考查x与r

若二者之一为红，则3和4不难满足

双黑缺陷

若x与r均黑double-black

摘除x并代之以r后，全树黑深度不再统一，原B-树中x所属节点下溢

在新树中，考查r的父亲p = r->parent， r的兄弟s = r==p->lc p->rc : p->lc

以下分四种情况处理

BB-1：s为黑，且至少有一个红孩子t

3+4重构：t、s、p重命名为a、b、c

r保持黑；a和c染黑；b继承p的原色

如此，红黑树性质在全局得以恢复——删除完成 //zig-zag等类似

BB-2R：s为黑，且两个孩子均为黑；p为红

r保持黑；s转红；p转黑

在对应的B-树中，等效于下溢节点与兄弟合并

红黑树性质在全局得以恢复

失去关键码p之前，上层节点不会继续下溢，合并之前，在p之左或右侧还必有（问号）关键码。必为黑色，有且仅有一个

BB-2B：s为黑，且两个孩子均为黑；p为黑

s转红；r与p保持黑

BB-3：s为红（其孩子均为黑）

zag(p)或zig(p)；红s转黑，黑p转红

既然p已转红，接下来绝不会是情况BB-2B，而只能是BB-1或BB-2R

复杂度

红黑树的每一删除操作都可在O(logn)时间内完成

其中，至多做

1O(logn)次重染色

2一次“3+4”重构

3一次单旋

以上就是关于二叉搜索树与红黑树全部的内容，包括:二叉搜索树与红黑树、红黑树的用途、红黑树原理讲解等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！