红黑树的原理和常见操作
1. 概述
在jdk1.8中，HashMap和ConcurrentHashMap中都采用了红黑树这一数据结构。即当链表达到一定的长度后，就把链表转化成红黑树。这其中主要利用了红黑树的良好性质，不管你节点怎样，他始终保持查找时间复杂度为O(logn)。这样的性质相对于链表在长度很长的时候有很大的优势。O(logn）<O(lgn)
2. 红黑树的定义
- 每个结点要么是红的，要么是黑的。
- 根结点是黑的。
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
- 如果一个结点是红的，那么它的俩个儿子都是黑的。
-
对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
一棵典型的红黑树如下：
红黑树
3. 红黑树的插入
在这里，默认你熟悉二叉查找树的结构，以及他的插入和删除操作。红黑树本质上是一棵二叉查找树。
对红黑树的插入，我们先按二叉查找树去插入，然后对对树做调整，使其满足红黑树的五条定义。（这是因为你插入会破坏其中的规则）
二叉查找树的插入伪代码如下：
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
可以看出，RB-INSERT(T, z)前面的第1-13行代码基本就是二叉查找树的插入代码，然后第14-16行代码把z的左孩子、右孩子都赋为叶结点nil，再把z结点着为红色，最后为保证红黑性质在插入操作后依然保持，调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色，并旋转。
换言之
- 如果插入的是根结点，因为原树是空树，此情况只会违反性质2，所以直接把此结点涂为黑色。
- 如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时也是什么也不做。
但当遇到下述3种情况时：
- 插入修复情况1：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
- 插入修复情况2：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子
- 插入修复情况3：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子
3.1 插入修复情况1：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。
插入的伪代码如下：
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ▹ Case 1
6 color[y] ← BLACK ▹ Case 1
7 color[p[p[z]]] ← RED ▹ Case 1
8 z ← p[p[z]] ▹ Case 1
如下面两个调整前的图和调整之后的图做对比。其中4为新添加的点。它的父节点为红色，叔叔节点为红色。那么调整就是把4的叔叔节点变为黑色（8节点），4的祖父节点变为红色，把当前结点指向祖父结点，从新的当前结点重新开始算法（7节点变为N)。
3.1.1 调整前的树
3.1.2 调整后的红黑树
3.2 插入修复情况2：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子
9 else if z = right[p[z]]
10 then z ← p[z] ▹ Case 2
11 LEFT-ROTATE(T, z) ▹ Case 2
调整之前的图如3.1.2，经过调整后得到如下的图。过程是当前结点的父结点做为新的当前结点，以新当前结点为支点左旋.
3.2.2 调整之后的树
3.3 插入修复情况3：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子
12 color[p[z]] ← BLACK ▹ Case 3
13 color[p[p[z]]] ← RED ▹ Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3
调整过程是把父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋。最后，把根结点涂为黑色，整棵红黑树便重新恢复了平衡。调整之前的图如3.2.2，经过调整后得到下图。
3.3.2调整后的图
3. 红黑树的删除
在这里默认你熟悉二叉查找树的删除操作。
下面我们用一个分析技巧：我们从被删结点后来顶替它的那个结点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的结点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父结点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。"--saturnman。
如果是以下情况，恢复比较简单：
- 当前结点是红+黑色
解法，直接把当前结点染成黑色，结束此时红黑树性质全部恢复。 - 当前结点是黑+黑且是根结点， 解法：什么都不做，结束。
下面4中特殊情况
- 删除修复情况1：当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)
- 删除修复情况2：当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色
- 删除修复情况3：当前结点颜色是黑+黑，兄弟结点是黑色，兄弟的左子是红色，右子是黑色
- 删除修复情况4：当前结点颜色是黑-黑色，它的兄弟结点是黑色，但是兄弟结点的右子是红色，兄弟结点左子的颜色任意
4.1 删除修复情况1：当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)。
解法：把父结点染成红色，把兄弟结点染成黑色，之后重新进入算法（我们只讨论当前结点是其父结点左孩子时的情况）。此变换后原红黑树性质5不变，而把问题转化为兄弟结点为黑色的情况(注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟结点为黑色的情况)。
变化前
变化后
4.2 删除修复情况2：当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色。
解法：把当前结点和兄弟结点中抽取一重黑色追加到父结点上，把父结点当成新的当前结点，重新进入算法。（此变换后性质5不变）。伪代码如下。
//调用RB-DELETE-FIXUP(T, x) 的9-11行代码
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 2
11 x p[x] ▹ Case 2
4.3 删除修复情况3：当前结点颜色是黑+黑，兄弟结点是黑色，兄弟的左子是红色，右子是黑色。
解法：把兄弟结点染红，兄弟左子结点染黑，之后再在兄弟结点为支点解右旋，之后重新进入算法。此是把当前的情况转化为情况4，而性质5得以保持。伪代码如下
//调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ▹ Case 3
14 color[w] ← RED ▹ Case 3
15 RIGHT-ROTATE(T, w) ▹ Case 3
16 w ← right[p[x]] ▹ Case 3
4.4 删除修复情况4：当前结点颜色是黑-黑色，它的兄弟结点是黑色，但是兄弟结点的右子是红色，兄弟结点左子的颜色任意。
解法：把兄弟结点染成当前结点父结点的颜色，把当前结点父结点染成黑色，兄弟结点右子染成黑色，之后以当前结点的父结点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。代码如下
//调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
17 color[w] ← color[p[x]] ▹ Case 4
18 color[p[x]] ← BLACK ▹ Case 4
19 color[right[w]] ← BLACK ▹ Case 4
20 LEFT-ROTATE(T, p[x]) ▹ Case 4
21 x ← root[T] ▹ Case 4
以上就是红黑树的结构和性质，对于面试和源码的理解很有帮助。
参考文章：
教你透彻了解红黑树
