1 背景

对于二叉排序树，时间复杂度最差时候会是 O(n)，比如插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行。为了改变排序二叉树存在的不足，Rudolf Bayer 在 1972 年发明了另一种改进后的排序二叉树：红黑树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。

2 定义

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的两倍，红黑树的时间复杂为O（log(N)）。具体来说，红黑树是满足如下性质的二叉查找树（binary search tree）：
（1）每个结点要么是红的要么是黑的。
（2）根结点是黑的。
（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点，和我们说的叶子节点不是一样的）都是黑的。
（4）如果一个结点是红的，那么它的两个儿子都是黑的。
（5）对于任意结点而言，其到叶结点树尾端NIL指针（叶子节点的孩子）的每条路径都包含相同数目的黑结点。

注：
黑色高度：从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度

3 红黑树与AVL树对比

（1）AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
（2）红黑树的插入删除比AVL树更便于控制操作
（3）红黑树整体性能略优于AVL树，因为红黑树旋转情况少于AVL树

4 树结构调整

在树的结构发生改变时（插入或者删除操作），往往会破坏上述5个条件中的条件4或条件5，需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight），左右旋在前面的课程已讲解。
（1）Y右旋
父亲y变成左子x的右子，左子x的右子B变成y左子B
（2）X左旋
父亲x变成右子y的左子，右子y的左子B变成x的右子B

5 代码实现

在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。

5.1 红黑树的插入

（1）调整思想
首先要知道红黑树是基于排序二叉树或者说二叉查找树进行插入的，,红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。前面说了，插入一个节点后要担心违反特征 4 和 5，数学里最常用的一个解题技巧就是把多个未知数化解成一个未知数。我们这里采用同样的技巧，把插入的节点直接染成红色，这样就不会影响特征 5，只要专心调整满足特征 4 就好了。这样比同时满足 4、5 要简单一些。染成红色后，我们只要关心父节点是否为红，如果是红的，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，这些操作的同时不能影响 不同路径上的黑色节点数一致的规则。

（2）插入步骤
1）基于二叉查找树插入
2）插入后结构调整
【1】父亲节点和叔叔节点都是红色
假设插入的是节点 X，这时父亲节点 A 和叔叔节点B 都是红色，爷爷节点 C 一定是黑色。
红色节点的孩子不能是红色，这时不管 X 是 A 的左孩子还是右孩子，只要同时把 A 和 B 染成黑色，C 染成红色即可。这样这个子树左右两边黑色个数一致，也满足特征 4。
但是这样改变后C 染成红色，C的父亲如果是红色岂不是又违反特征 4。因此需要以 爷爷节点 C 为新的调整节点，再次进行调整操作，以此循环，直到父亲节点不是红的，就没有问题了。

【2】父亲节点为红色，叔叔节点为黑色
1】当前节点是父亲的左孩子，当前节点=X
假设插入的是节点 X，这时父亲节点 A 是红色，叔叔节点 B 是黑色，爷爷节点 C 一定是黑色。红色节点的孩子不能是红色，但是直接把父亲节点 A 涂成黑色也不行，这条路径多了个黑色节点。可以通过右旋C，这时候右子树多了一个黑色，把C染红，然后父亲节点染黑就可以

2】当前节点是父亲的右孩子,一开始当前节点=X，后来当前节点=A
先以当前节点X的父节点A为支点进行左旋，然后就转换成1）中的场景了，然后以A作为当前节点进行1）的步骤就行了

5.2 红黑树的删除

（1）调整思想
根据红黑树的第 5 个特性：如果当前待删除节点是红色的，它被删除之后对当前树的特性不会造成任何破坏影响。而如果被删除的节点是黑色的，这就需要进行进一步的调整来保证后续的树结构满足要求。这里研究的是删除黑色节点的情况。为了保证删除节点父亲节点左右两边黑色节点数一致，需要重点关注父亲节点没删除的那一边节点是不是黑色。如果删除后父亲节点另一边比删除的一边黑色节点多，就要想办法搞到平衡，具体的平衡方法有如下几种方法：把父亲节点另一边（即删除节点的兄弟树）其中一个节点弄成红色，也少一个黑色；或者把另一边多的黑色节点旋转过来一个

（2）删除步骤
1）基于二叉查找树的删除
2）删除后结构调整
只考虑删除的是黑色节点
【1】兄弟如果是红的，当前节点=X
说明兄台的孩子都是黑的，其实把兄弟转成黑的是为了转化成2中的场景
1】把兄弟搞成黑的
2】父亲搞成红的
3】左旋转父亲（结果兄弟给当前节点分一个黑孩子）
4】接下来对比旋转后的兄弟

【2】兄弟节点如果是黑色的，兄弟的孩子就具有不确定性了，接上【1】，此时兄弟是E，假如有两孩子是F和G，并且都是黑色的
1】 兄弟的孩子都是黑色的
A. 把兄弟染成红的即可，那么子树就算调整完了
B. 以父节点为当前节点，继续往上调整父级节点
刚好这里X的父亲节点是红色的，那么直接把父亲节点染黑即可，不会影响到性质5

2】 兄弟节点的孩子最多只有1个黑色的时候，接上【1】，此时兄弟是E，假如E有两孩子F和G，有一孩子，假如G是黑色的
《1》兄弟有个孩子是黑色的
这个步骤是为了转换成兄弟的孩子没有黑色的情况,即都是红色的
A.把不是黑的那个孩子搞黑
B.兄弟搞红
C.兄弟右旋转
D.以后对比旋转后的兄弟

《2》兄弟的孩子都是红色的,接上《1》，假如F还有个孩子是红色的H，当然没有也没关系，兄弟的孩子只要没有黑色的都是要走这个步骤
A.把兄弟涂成跟父亲一样的颜色
B.然后把父亲搞黑
C.把兄弟的右孩子搞黑
D.父亲节点左旋
E．刚好X的父亲C不是根节点，并C是黑色的，所以继续以C作为当前节点研究上一级

【3】只要当前节点的父亲是黑色的并且当前节点还不是根节点，
就要继续步骤【1】和【2】，否则当前节点要么是红色节点或者是根，那就染黑然后结束

5.3 具体代码实现

public class RedBlackTree{private class Node{public E e;public int color;public Node parent;public Node(E e){this.e = e;this.color = 0;this.parent = null;}}private Node root;public RedBlackTree(){root=null;}	/*** 插入* @param node * @return*/	public void insert(Node node){//这个是二叉搜索树的插入算法，前面讲过了，这里不讲了insertBinarySearchTree(node);//插入后的结构调整fixAfterInsertion(node);}/*** 插入后的结构调整* @param x 节点集合* @return*/	private void fixAfterInsertion(Node x) {//直接染成红色，降低问题的复杂性x.color = RED;  //当前不是根几点，并且父亲节点是红色的，才需要调整while (x != null && x != root && x.parent.color == RED) {// 插入节点 x 的父亲节点位于左孩子if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {   //叔叔节点		Node y = rightOf(parentOf(parentOf(x)));  //如果叔叔是红色if (colorOf(y) == RED) {    setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} //如果叔叔是黑色else {    //当前节点是父亲的右孩子，要多做一次左旋   if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} //和上面对称，原理一样else {     Node y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color = BLACK;}/*** 从二分搜索树中删除元素* @param e* @return*/public void delete(Node node){//这个是二叉搜索树的删除算法，前面讲过了，这里不讲了Node x = deleteBinarySearchTree(node);//删除后的结构调整fixAfterDeletion(x);}	/*** 删除后的结构调整* @param x 节点集合* @return*/		private void fixAfterDeletion(Node x) {//当前节点不是根节点，并且是黑节点，要继续调整while (x != root && colorOf(x) == BLACK) {//当前节点是左孩子if (x == leftOf(parentOf(x))) {//兄弟节点Node sib = rightOf(parentOf(x));//兄弟是红色，转化成兄弟是黑色的场景if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateLeft(parentOf(x));sib = rightOf(parentOf(x));}/*兄弟是黑色的场景*///兄弟两孩子都是黑色的if (colorOf(leftOf(sib))  == BLACK &&colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} //兄弟最多有一个孩子是黑色else {//兄弟有一个孩子是黑色的，转化成兄弟没有孩子是黑色的场景if (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK);setColor(sib, RED);rotateRight(sib);sib = rightOf(parentOf(x));}/*兄弟没有一个孩子是黑色的都要做下面几个步骤*/setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x));x = root;}} //当前节点是右孩子，原理和左孩子一样，对称操作else { Node sib = leftOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateRight(parentOf(x));sib = leftOf(parentOf(x));}if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(leftOf(sib)) == BLACK) {setColor(rightOf(sib), BLACK);setColor(sib, RED);rotateLeft(sib);sib = leftOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(leftOf(sib), BLACK);rotateRight(parentOf(x));x = root;}}}setColor(x, BLACK);}	}