一、背景引入
二叉排序树的性能取决于二叉树的层数，最好的情况O(log n)存在于完全二叉排序树的情况下，其访问性能近似于折半查找（图左）；最差的情况是O(n)，比如插入的元素是有序的，生成的二叉树就是一个链表，这种情况下，需要遍历全部元素才能找到目标元素（图右）。
为了改变排序二叉树存在的不足，Rudolf Bayer 在 1972 年发明了另一种改进后的排序二叉树：红黑树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
二、什么是红黑树
先来看看Wikipedia 中有关Red–black tree的介绍：
A red–black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
简单翻译：
红黑树，一种自平衡的二叉查找树，但在每个结点上有一个额外的存储位表示结点的颜色，可以是Red或Black。这些颜色位用来确保红黑树在插入和删除操作后仍能够近乎平衡。
性能分析：插入、删除、查找 最坏时间复杂度都为
![]()
image.png
应用领域
由于统计性能好于平衡二叉树（AVL树），因此在很多地方都有应用。，比如在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。
应用举例
HashMap作为Map接口的一个实现类，在java开发中经常用到。其数据结构如下图所示：
从图中可以看出，HashMap底层使用的结构包括两部分:table和bucket。table指的是数组，是HashMap的主体，哈希表利用数组一次定位的特性，将当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可以完成操作，存储位置=f(关键字)。bucket指的是链表，主要是为了解决哈希冲突而存在的，试想如果插入的元素中存在大量哈希冲突，那么链表的长度会越来越长，这样对于查找某一个元素可能需要遍历整个链表才能找到，其性能可想而知。因此在jdk1.8中HashMap的bucket部分引入了红黑树。
首先看看红黑树长啥样：
图中的叶节点并没有画出来，而是以NIL指针代替，这是因为叶节点在这里并不包含数据，只是作为结束符。
为了便于理解，我们拿TreeMap来分析：
红黑树的数据结构
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
.......
}
其中Entry是TreeMap的内部类。
红黑树特性
红黑树在原有的二叉查找树基础上增加了如下几个要求：
1.Every node is either red or black.
2.The root is black.
3.Every leaf (NIL) is black.
4.If a node is red, then both its children are black.
5.For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
中文意思是：
1.每个节点要么是红色，要么是黑色；
2.根节点永远是黑色的；
3.所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
4.每个红色节点的两个子节点一定都是黑色；
5.从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
其中：
性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。 因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1)
性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。
红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。
三、红黑树的三大基本操作
左旋：
右旋：
着色
红黑树的左旋右旋
红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。比如 X 左旋(右图转成左图)的结果，是让在 Y 左子树的黑色节点跑到 X 右子树去。
左旋
指定节点 x 的左旋 (右图转成左图)：
//这里 p 代表 x
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right; // p 是上图中的 x，r 就是 y
p.right = r.left; // 左旋后，x 的右子树变成了 y 的左子树 β
if (r.left != null)
r.left.parent = p; //β 确认父亲为 x
r.parent = p.parent; //y 取代 x 的第一步：认 x 的父亲为爹
if (p.parent == null) //要是 x 没有父亲，那 y 就是最老的根节点
root = r;
else if (p.parent.left == p) //如果 x 有父亲并且是它父亲的左孩子，x 的父亲现在认 y 为左孩子，不要 x 了
p.parent.left = r;
else //如果 x 是父亲的右孩子，父亲就认 y 为右孩子，抛弃 x
p.parent.right = r;
r.left = p; //y 逆袭成功，以前的爸爸 x 现在成了它的左孩子
p.parent = r;
}
}
可以看到，x 节点的左旋就是把 x 变成 右孩子 y 的左孩子，同时把 y 的左孩子送给 x 当右孩子
右旋
指定节点 y 的右旋 (左图转成右图)：
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
同理，y 节点的右旋就是把 y 变成 左孩子 x 的右孩子，同时把 x 的右孩子送给 x 当左子树。
四、红黑树的平衡插入
红黑树的插入主要分两步：
首先和二叉查找树的插入一样，查找、插入
然后调整结构，保证满足红黑树状态
对结点进行重新着色
以及对树进行相关的旋转操作
红黑树的插入在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。
红黑树的插入修复
红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。
同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。
因此我们需要在插入黑色节点后进行结构调整，保证红黑树始终满足这 5 条特征。
调整思想
插入、染红后的调整有 2 种情况：
情况1.父亲节点和叔叔节点都是红色：
情况2.父亲节点为红色，叔叔节点为黑色
前面说了，插入一个节点后要担心违反特征 4 和 5，数学里最常用的一个解题技巧就是把多个未知数化解成一个未知数。我们这里采用同样的技巧，把插入的节点直接染成红色，这样就不会影响特征 5，只要专心调整满足特征 4 就好了。这样比同时满足 4、5 要简单一些。染成红色后，我们只要关心父节点是否为红，如果是红的，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，这些操作的同时不能影响 不同路径上的黑色节点数一致的规则。
情况1：父亲节点和叔叔节点都是红色：
假设插入的是节点 N，这时父亲节点 P 和叔叔节点 U 都是红色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，这时不管 N 是 P 的左孩子还是右孩子，只要同时把 P 和 U 染成黑色，G 染成红色即可。这样这个子树左右两边黑色个数一致，也满足特征 4。
但是这样改变后 G 染成红色，G 的父亲如果是红色岂不是又违反特征 4 了？
这个问题和我们插入、染红后一致，因此需要以 爷爷节点 G 为新的调整节点，再次进行调整操作，以此循环，直到父亲节点不是红的，就没有问题了。
情况2：父亲节点为红色，叔叔节点为黑色
假设插入的是节点 N，这时父亲节点 P 是红色，叔叔节点 U 是黑色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，但是直接把父亲节点 P 涂成黑色也不行，这条路径多了个黑色节点。怎么办呢？
既然改变不了你，那我们就此别过吧，我换一个更适合我的！
我们怎么把 P 弄走呢？看来看去，还是右旋最合适，通过把 爷爷节点 G 右旋，P 变成了这个子树的根节点，G 变成了 P 的右子树。
右旋后 G 跑到了右子树上，这时把 P 变成黑的，多了一个黑节点，再把 G 变成红的，就平衡了！
情况2：父亲节点为红色，叔叔节点为黑色
N 位于 P 的右孩子位置，将 P 左旋，就化解成上述情况了。
源码分析
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //直接染成红色，少点麻烦
//这里分析的都是父亲节点为红色的情况，不是红色就不用调整了
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 插入节点 x 的父亲节点位于左孩子
Entry<K,V> y = rightOf(parentOf(parentOf(x))); // y 是 x 的叔叔节点
if (colorOf(y) == RED) { //如果 y 也是红色，只要把父亲节点和 y 都变成黑色，爷爷节点变成红的，就 Ok 了
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //如果叔叔节点 y 不是红色，就需要右旋，让父亲节点变成根节点，爷爷节点去右子树去，然后把父亲节点变成黑色、爷爷节点变成红色
//特殊情况：x 是父亲节点的右孩子，需要对父亲节点进行左旋，把 x 移动到左子树
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else { 。。。。。。}} //和上面对称的操作
五、一句话概括
在插入调整时为了简化操作我们直接把插入的节点涂成红色，这样只要保证插入节点的父节点不是红色就可以了。
