前言
最近，看HashMap的时候，看到了其中的实现用到了红黑树。于是就想来复习一下，老久以前学的东西差不多都忘掉了。
红黑树的本质是二叉搜索树，它的约束条件更多而已。这篇复习笔记首先过一下二叉搜索树，然后再进入红黑树。
二叉搜索树 （BST）
BST满足如下三个特性：
- 左子树上所有结点的值均小于它的根结点的值。
- 右子树上所有结点的值均大于它的根结点的值。
- 左、右子树也分别为二叉搜索树。
在BST中搜索元素的过程类似于二分法，从根节点开始，小于根节点从左边搜索，大于根节点则从右边搜索。以这个原则不断搜索即可找到目标。
看起来BST算是比较优秀对吧，但是呢，假如我们遇到下面这棵BST：
这种情况一下去搜索5，那么时间复杂度就为n，相当于对所有元素都遍历了一遍（这正是红黑树会避免的一个缺点，红黑树后面会详细讲到）。
上面简单介绍了BST的基本性质，以及其搜索算法，下面会介绍它的插入节点的算法和删除节点的算法。
BST 插入节点的算法
向树b插入新的节点n时，过程如下：
- 如果
b是空树，则把n作为b的根节点，否则： - 如果根节点等于
n，则返回（因为我们不考虑一棵树中有重复节点的情况），否则： - 若根节点小于
n，那么将节点插入左子树，否则： - 若根节点大于
n，那么将节点插入右子树。
重复以上步骤，最终新节点会插入到树中，并且始终会落到叶子节点上。
BST删除节点的算法
若想从BST中删除节点n，有下面的几种情况：
- 若
n为叶子节点，直接删除，不影响树的结构。
- 若
n的左子树（或右子树）为空，可以删除n并将左子树（或右子树）向上层移动到n的位置。
- 如果
n的左子树和右子树都不为空时，此时假设其父节点为p，n的左子树最右下的点为s，做法为：交换n与s的位置，然后按照情形2删除n。
听起来比较绕，结合下图来理解就比较简单了。
BST性能
BST在删除、插入、搜索的复杂度等于树高，最坏的情况下复杂度为O(n)，平均的复杂度为O(logn)。这个平均复杂度是怎么去算的呢？我是这么去理解的：
每个叶子节点的深度是不一样的，并且搜索节点的复杂度是等于节点的深度。所以这里就把每个叶子节点深度都相同，看做一种平均状态，此时的BST也是一棵完全二叉树。
对于一棵是完全二叉树的BST，进行搜索时，搜索次数k与节点数n满足如下关系
次数 k
|
剩余待搜索节点数 |
|---|---|
| 1 | n/2^1 |
| 2 | n/2^2 |
| ··· | ··· |
| k | n/2^k |
当 n/2^k = 1 时已经搜索到了叶子节点，于是计算得到
k = logn
红黑树（Red–black tree）
上面我们讲到了，BST的深度可能为 n，这种情况下去搜索和顺序搜索没有区别。于是鲁道夫·拜尔发明了一种自平衡二叉搜索树。
红黑树在满足二叉搜索树的特性之外，还增减了5个特性：
1 . 叶子节点是红色或者黑色。
2 . 根是黑色。
3 . 所有叶子都是黑色（叶子是NIL节点）。
4 . 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
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为红黑，那么它的父亲和儿子一定是黑色，我们可以直接用它的黑色儿子替换它，这样并不会破坏性质3和性质4，又因为删除的是一个红色节点，性质5又得以保证。 - 被删除节点
n为红色而它的儿子节点红色，直接将儿子节点顶替上来，并将儿子节点后重新绘制为黑色，这样性质3，性质4和性质5都得以保证。
需要进一步讨论的情形是被删除节点及它的儿子节点两者都是黑色。我们首先要把删除的节点替换为它的儿子，现在我们称呼顶替上来的这个儿子节点为 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 做重新平衡。
需要对
p做重新平衡的是因为经过p的路径都少一个黑色节点，类似于n。
情形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，有如下两种情况：
- 它如果通过
n的新兄弟，那么它以前和现在必然通过s和n，它们只是交换了颜色，所以路径上的黑色节点数目得以保持。 - 它通过
n的新叔父sr。那么它以前通过sr，s，p，但是现在只通过sr，s，可以看到无论p是红色还是黑色，路径上的黑色节点数目依然不变。
至此，树已经达到平衡状态。
结语
终于是理清楚了，红黑树的插入和删除操作还是比较复杂，但是一步步去理解也是行得通的，记录该文便于后期查阅和复习。
另外，本文参考了维基百科红黑树，它上面讲得非常细致。
