说到红黑树，让人又爱又恨啊，真是一种令人头大的数据结构。我也没少被他折磨过，尽管在工作中，在网文中多次看到过关于它的原理解释，但大多都是一上来就是五条定义，然后紧跟着就是红黑树插入的代码实现，翻转代码实现，让人难以理解消化，搞的人云里雾里的。这是因为五条定义以及代码实现都是红黑树定义和实现的精炼结果了，如果连红黑树的设计思想，它的推演过程都不知道，就直接把一个研究成果丢过来，搁谁也难以通过结果反向去理解它的实现原理吧。本文介绍对红黑树推演过程，看完此文保证对红黑树的定义，翻转可以轻松理解了。网上也有很多类似的文章，不过我决定对红黑树这个老大难做一次全面彻底的总结。
红黑树的定义
先摆一下红黑树的官方定义吧，红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求，也叫红黑树的五大定义
- 节点是红色或黑色。
- 根节点是黑色
- 所有叶子都是黑色。（叶子是NUIL节点，也叫空节点）
- 如果一个节点是红色，则它的子节点必须是黑色
- 从一个节点到该节点的所有叶节点的路径包含相同数目的黑色节点
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。因为红黑树是一种特化的二叉查找树，所以红黑树上的查找与普通二叉查找树相同。
红黑树的用途
在推演红黑树之前，再来了解一下红黑树的用途吧，明白它在计算机科学中有多重要。
JDK的Map
在我们愉快的使用Java给我提供的集合类时，却很少会去想它们为什么这么好用吧（用就完事了，想那么多干嘛，是嫌头发太多了吗 ！）在Java的集合类中有两个使用到了红黑树数据结构，分别是 TreeMap 和 HashMap。其中 HashMap是JDK在1.8之后才使用的，用于提升HashMap的性能。
Linux非实时任务调度
Linux 的稳定内核版本在 2.6.24 之后，使用了新的调度程序 CFS，所有非实时可运行进程都以虚拟运行时间为 key 值挂在一棵红黑树上，以完成更公平高效地调度所有任务。CFS 弃用 active /expired 数组和动态计算优先级，不再跟踪任务的睡眠时间和区别是否交互任务，并且在调度中采用基于时间计算键值的红黑树来选取下一个任务，根据所有任务占用 CPU 时间的状态来确定调度任务优先级。
Linux虚拟内存
32 位 Linux 内核虚拟地址空间划分 0－3G 为用户空间，3－4G 为内核空间，因此每个进程可以使用 4GB的虚拟空间。同时，Linux 定义了虚拟存储区域( VMA) 以便于更好表示进程所使用的虚拟空间，每个 VMA是某个进程的一段连续虚拟空间，其中的单元具有相同的特征，所有的虚拟区域按照地址排序由指针链接为一个链表。当发生缺页中断时搜索 VMA 到指定区域时，则需要频繁操作，因此选用了红黑树以减少查找时间。
红黑树的推演过程
来到这里，就请耐心看完吧，因为真正精彩的才刚刚开始。红黑树的起源，自然是二叉查找树了，对于二叉树的概念就不说了非常简单。
二叉树
这种树结构从根节点开始，左子节点小于它，右子节点大于它。每个节点都符合这个特性，所以易于查找，是一种很好的数据结构。但是它有一个问题，就是容易偏向某一侧，这样就像一个链表结构了，失去了树结构的优点，查找时间会变坏。所以我们都希望树结构都是矮矮胖胖的，就像左边这样，而右边的就是极端情况的二叉树，已经退化成一个链表了
基于这种需求，平衡树的概念就应运而生了。平衡树简单的意思就是当二叉树出现右边这种极端情况时，把这颗树重新构造成一颗新的有左右子树的二叉树，这样所有节点的数据查找效率就会相对均衡。例如把上图中右边极端情况下的二叉树重新构造成如下结构
红黑树就是一种平衡树，它可以保证二叉树基本符合矮矮胖胖的结构，但是在理解红黑树之前，必须先了解另一种树，叫2-3树，红黑树背后的实现原理就是它。
2-3树的概念
2-3树是二叉树的变种，它存在两种类型的节点，把这两种节点分别叫做2-节点和3-节点，树中的2和3分别代表节点有几个子节点。
2-节点：也叫普通节点，包含一个元素，拥有两个子节点3-节点：它是2-节点的扩充版，包含两个元素，拥有三个子节点。对于3-节点有这样一个排列约束，如下图中最左边的子节点3小于父节点5，中间的子节点7大小介于父节点5和10之间，最右边的11大于父节点10
在这两种节点的配合下，2-3树可以保证在插入值过程中，任意叶子节点到根节点的距离都是相同的。完美实现了矮胖矮胖的目标。怎么配合的呢，下面来看2-3树的构造过程。
2-3树的构造
我们从零开始构造一颗2-3树，如果你的想象力足够强大，你可以边读边在脑海中形成一个构造树的动画过程，如果不行的话可以用笔在纸上画一画。我们知道在二叉查找树中，插入过程从根节点开始比较，小于节点值往右继续与左子节点比，大于则继续与右子节点比，直到某节点左或右子节点为空，把值插入进去。但在2-3树中，情况稍微有些变化，因为2-3树中存在两种不同的节点类型，插入思路大致如下：
- 如果将值插入一个2-节点，则将2-节点扩充为一个3-节点。
- 如果将值插入一个3-节点，分为以下几种情况。下面会分别讨论这几种情况
3-节点没有父节点
即整棵树就只有它一个3-节点。此时，将3-节点扩充为一个4-节点，即包含三个元素的节点，这违背了2-3树的定义，因此将其分解重组，变成一棵二叉树。
此时二叉树依然保持平衡。
3-节点有一个2-节点的父节点
此时的操作是，3-节点扩充为4-节点，然后分解重组4-节点，然后将分解后的新树的父节点融入到原来2-节点的父节点中去，形成一个3-节点。这个过程稍微有点复杂，直接上图，跟着图中箭头走一遍。
3-节点有一个3-节点的父节点
3-节点有一个3-节点要插入时，就有点复杂了，因此3-节点插入一个节点后会变成4-节点，此时违背了2-3树的定义，3-节点会分解重组成2-节点，生成的新树的父节点会融入到原本的父级，而原本的父级也是一个3-节点，融入一个新节点后会变成4-节点，又违背了2-3树的定义，于是继续分解重组，整个树增加一层，仍然保持平衡。为了便于直观理解，直接上图吧，下图从零构建一颗2-3树
图中最后构建出了一个有6个数据的2-3树，可以看出最后2-3树包含两个2-节点，最完美的地方在于，从根节点到每个叶子节点的路径长度是一样的。可以说是一颗完美的树。因此2-3树的设计完全可以保证二叉树保持矮矮胖胖的状态，保持其性能良好。但是，将这种直白的表述写成代码实现起来并不方便，因为要处理的情况太多。这样需要维护两种不同类型的节点，将链接和其他信息从一个节点复制到另一个节点，将节点从一种类型转换为另一种类型等等，因此红黑树登场了。
红黑树
红黑树的背后逻辑就是2-3树的逻辑，红黑树使用了红色来标记2-节点（包含两个元素的节点）中左边的那个元素，黑色用于标记普通节点（包含一个元素的节点）和2-节点中右边的那个元素，总而言之，可以大致理解为用红色标记2-节点，用黑色标记普通节点。如果要直接从红黑树的代码去理解它是如何工作的以及背后的道理，就比较困难了。所以你一定要理解它的演化过程，才能真正的理解红黑树。基于这个结论，我们可以非常简单的把刚刚得到的2-3树，转换成一颗红黑树
只需三步就可以把一颗2-3树变为红黑树，实际上2-3树已经是一颗红黑树了
- 把2-3树中所有3-节点的两个元素分开
- 把3-节点中的左元素标记为红色，右元素标记为黑色，普通节点标记为黑色
- 把3-节点展开，注意3-节点展开时，两个左边的子节点要划给红元素。此外，展开时3-节点中的红元素总是向左下方倾斜，3-节点中的黑元素总是向右上方倾斜
至此红黑树的构造过程就结束了，红色树的构造，插入就是2-3树的插入逻辑，至于左旋，右旋其实就对应于2-3树出现4-时分解重组成2-节点的过程。我再把刚刚得到的红黑树中的红节点摆平，又可以还原成一颗2-3树了，如下图
Java实现红黑树
如果能很好的理解2-3树，基本红黑树也就不是问题了，最后可以按照2-3树的思路，尝试去实现一下红黑树的插入，查找删除逻辑。这里我贴一份红黑树的Java实现，代码中有比较多的注释，方便理解查阅
NodeColor.java
public class NodeColor {
public static String Red = "red";
public static String Black = "black";
}RedBlackTreeNode.java
public class RedBlackTreeNode {
private String color;
private int key;
private RedBlackTreeNode left;
private RedBlackTreeNode right;
private RedBlackTreeNode parent;
//构造Nil结点
public RedBlackTreeNode(){
this.color = NodeColor.Black;
this.key = 0;
this.left = null;
this.right = null;
this.parent = null;
}
//构造结点
public RedBlackTreeNode(String color, int key, RedBlackTreeNode left, RedBlackTreeNode right, RedBlackTreeNode parent){
this.color = color;
this.key = key;
this.left = left;
this.right = right;
this.parent = parent;
}
//获取颜色
public String getColor() {
return color;
}
//设置颜色
public void setColor(String color) {
this.color = color;
}
//获取值
public int getKey() {
return key;
}
//设置值
public void setKey(int key) {
this.key = key;
}
//获取左子树
public RedBlackTreeNode getLeft() {
return left;
}
//设置左子树
public void setLeft(RedBlackTreeNode left) {
this.left = left;
}
//获取右子树
public RedBlackTreeNode getRight() {
return right;
}
//设置右子树
public void setRight(RedBlackTreeNode right) {
this.right = right;
}
//获取父结点
public RedBlackTreeNode getParent() {
return parent;
}
//设置父结点
public void setParent(RedBlackTreeNode parent) {
this.parent = parent;
}
}RedBlackTree.java
public class RedBlackTree {
private static RedBlackTreeNode nil = new RedBlackTreeNode();
private RedBlackTreeNode root = new RedBlackTreeNode();
//构造空红黑树
public RedBlackTree(){
root = nil;
}
//创建结点
public RedBlackTreeNode RB_NODE(int key){
RedBlackTreeNode node = new RedBlackTreeNode(NodeColor.Red, key, nil, nil, nil);
return node;
}
//判断是否为Nil结点
public boolean IsNil(RedBlackTreeNode node){
if( node == nil){
return true;
}else{
return false;
}
}
//获取根结点
public RedBlackTreeNode getRoot() {
return root;
}
//设置根结点
public void setRoot(RedBlackTreeNode root) {
this.root = root;
}
//插入结点
public void RB_INSERT(RedBlackTree T, RedBlackTreeNode z){
//临时变量结点y，存储临时结点，默认为Nil
RedBlackTreeNode y = T.nil;
//x初试为根结点
RedBlackTreeNode x = T.getRoot();
//循环二查找合适的插入点
while( IsNil(x) == false ){
//保存当前结点，作为结果的根结点
y = x;
if( z.getKey() < x.getKey() ){
//查找左子树
x = x.getLeft();
}else{
//查找右子树
x = x.getRight();
}
}
//临时结点y设置为插入点的父结点
z.setParent(y);
if( IsNil(y) == true ){
//空树时设置z为根结点
T.setRoot(z);
}else if( z.getKey() < y.getKey() ){
//插入为左子树
y.setLeft(z);
}else{
//插入为右子树
y.setRight(z);
}
//将插入结点的左右子树设为Nil，颜色为红色，已经在构造时设置过，可以省略
z.setLeft(T.nil);
z.setRight(T.nil);
z.setColor(NodeColor.Red);
//插入调整
RB_INSERT_FIXUP(T, z);
}
//插入调整
public void RB_INSERT_FIXUP(RedBlackTree T, RedBlackTreeNode z){
//当z的父结点为红色时，插入结点和父结点同为红色，需要调整
while( z.getParent().getColor() == NodeColor.Red ){
//插入结点的父结点是祖父节点的左子树
if( z.getParent() == z.getParent().getParent().getLeft() ){
//y定义为叔叔结点
RedBlackTreeNode y = z.getParent().getParent().getRight();
//case1：如果叔叔结点为红色，上层父结点和叔叔结点设为黑色，祖父节点设为红色
if( y.getColor() == NodeColor.Red ){
z.getParent().setColor(NodeColor.Black);
y.setColor(NodeColor.Black);
z.getParent().getParent().setColor(NodeColor.Red);
//祖父结点设为z
z = z.getParent().getParent();
}
//case2：插入结点为父结点的右子树，（叔叔结点一定为黑色）,父结点设为z，对z左旋
else if( z == z.getParent().getRight() ){
//对父结点左旋
z = z.getParent();
LEFT_ROTATE(T, z);
}
//case3：插入结点为父结点的左子树，（叔叔结点一定为黑色），父结点设为黑色，祖父结点设为红色，对祖父结点右旋
z.getParent().setColor(NodeColor.Black);
z.getParent().getParent().setColor(NodeColor.Red);
RIGHT_ROTATE(T, z.getParent().getParent());
}
//插入结点的父结点是祖父节点的右子树，同理，方向交换
else{
RedBlackTreeNode y = z.getParent().getParent().getLeft();
if( y.getColor() == NodeColor.Red ){
z.getParent().setColor(NodeColor.Black);
y.setColor(NodeColor.Black);
z.getParent().getParent().setColor(NodeColor.Red);
z = z.getParent().getParent();
}
else if( z == z.getParent().getLeft() ){
z = z.getParent();
RIGHT_ROTATE(T, z);
}
z.getParent().setColor(NodeColor.Black);
z.getParent().getParent().setColor(NodeColor.Red);
LEFT_ROTATE(T, z.getParent().getParent());
}
}
T.getRoot().setColor(NodeColor.Black);
}
//删除结点子函数，把根结点为u的子树替换为根结点为v的子树
public void RB_TRANSPLANT( RedBlackTree T, RedBlackTreeNode u, RedBlackTreeNode v){
//u为根结点
if( IsNil(u.getParent()) ){
T.root = v;
}
//u为左子树
else if( u == u.getParent().getLeft() ){
u.getParent().setLeft(v);
}
//u为右子树
else{
u.getParent().setRight(v);
}
//父结点交换
v.setParent(u.getParent());
}
//查找后继
public RedBlackTreeNode TREE_MINIMUM(RedBlackTreeNode x){
//不断查找左子树
while( IsNil(x.getLeft()) == false ){
x = x.getLeft();
}
return x;
}
//删除结点
public void RB_DELETE(RedBlackTree T, RedBlackTreeNode z){
//临时结点y保存即将删除的结点z信息
RedBlackTreeNode y = z;
//在结点删除或者移动前必须保存结点的颜色
String yOriginColor = y.getColor();
//临时结点x，用于记录y的位置
RedBlackTreeNode x = null;
//case1：z无左子树，直接将右子树置于z位置
if( IsNil(z.getLeft()) == true ){
x = z.getRight();
RB_TRANSPLANT(T, z, z.getRight());
}
//case2：z无右子树，直接将左子树置于z位置
else if( IsNil(z.getRight()) == true ){
x = z.getLeft();
RB_TRANSPLANT(T, z, z.getLeft());
}
//case3：z有左右子树
else{
//找到右子树中最小的结点，即z的后继
y = TREE_MINIMUM(z.getRight());
//删除的实际是y的位置的结点，要记录y的颜色
yOriginColor = y.getColor();
//y可能有右孩子，一定无左孩子，保存右孩子
x = y.getRight();
//若y为z的右孩子，直接相连
if( y.getParent() == z ){
x.setParent(y);
}
//若不相连
else{
RB_TRANSPLANT(T, y, y.getRight());
y.setRight(z.getRight());
y.getRight().setParent(y);
}
RB_TRANSPLANT(T, z, y);
y.setLeft(z.getLeft());
y.getLeft().setParent(y);
y.setColor(z.getColor());
}
//删除结点为黑色时需要调整
if( yOriginColor == NodeColor.Black ){
RB_DELETE_FIXUP(T, x);
}
}
//删除调整
public void RB_DELETE_FIXUP(RedBlackTree T, RedBlackTreeNode x){
//临时结点
RedBlackTreeNode w = null;
//非根结点且为黑色
while( x != T.getRoot() && x.getColor() == NodeColor.Black ){
//x为父结点左孩子
if( x == x.getParent().getLeft() ){
//w为兄弟结点
w = x.getParent().getRight();
//case1：w兄弟结点为红色
if( w.getColor() == NodeColor.Red ){
//w设为黑色
w.setColor( NodeColor.Black );
//被删结点的父结点设为黑色
x.getParent().setColor( NodeColor.Red );
//对x的父结点左旋
LEFT_ROTATE(T, x.getParent());
//更新x的兄弟结点
w = x.getParent().getRight();
}
//case2：w兄弟结点和两个孩子结点都为黑
if( w.getLeft().getColor() == NodeColor.Black && w.getRight().getColor() == NodeColor.Black ){
//w设为黑色
w.setColor(NodeColor.Red);
//重设x为x的父结点
x = x.getParent();
}
//case3：w兄弟结点为黑，w的左孩子为红，右孩子为黑
else if( w.getRight().getColor() == NodeColor.Black ){
//w的左孩子设为黑
w.getLeft().setColor(NodeColor.Black);
//w设为红
w.setColor(NodeColor.Red);
//右旋
RIGHT_ROTATE(T, w);
//更新w
w = x.getParent().getRight();
}
//case4：w兄弟结点为黑，w的右孩子为红
w.setColor(x.getParent().getColor());
x.getParent().setColor(NodeColor.Black);
w.getRight().setColor(NodeColor.Black);
LEFT_ROTATE(T, x.getParent());
x = T.getRoot();
}
//x为父结点右孩子
else{
w = x.getParent().getLeft();
if( w.getColor() == NodeColor.Red ){
w.setColor( NodeColor.Black );
x.getParent().setColor( NodeColor.Red );
RIGHT_ROTATE(T, x.getParent());
w = x.getParent().getLeft();
}
if( w.getRight().getColor() == NodeColor.Black && w.getLeft().getColor() == NodeColor.Black ){
w.setColor(NodeColor.Red);
x = x.getParent();
}
else if( w.getLeft().getColor() == NodeColor.Black ){
w.getRight().setColor(NodeColor.Black);
w.setColor(NodeColor.Red);
LEFT_ROTATE(T, w);
w = x.getParent().getLeft();
}
w.setColor(x.getParent().getColor());
x.getParent().setColor(NodeColor.Black);
w.getLeft().setColor(NodeColor.Black);
RIGHT_ROTATE(T, x.getParent());
x = T.getRoot();
}
}
x.setColor(NodeColor.Black);
}
//左旋
public void LEFT_ROTATE(RedBlackTree T, RedBlackTreeNode x){
//左旋结点右子树不能为空
if ( IsNil(x.getRight()) == true )
return;
//定义y结点
RedBlackTreeNode y = x.getRight();
//y左子树 -> x右子树
x.setRight(y.getLeft());
//x -> y左子树父结点
y.getLeft().setParent(x);
//x父结点 -> y父结点
y.setParent(x.getParent());
//y -> x父结点左/右子树或根结点
if( IsNil(x.getParent()) == true){
//x为根结点，y设为根结点
T.setRoot(y);
}else if( x.getParent().getLeft() == x){
//x为左子树，y设为左子树
x.getParent().setLeft(y);
}else{
//x为右子树，y设为右子树
x.getParent().setRight(y);
}
//x -> y左子树
y.setLeft(x);
//y -> x父结点
x.setParent(y);
}
//右旋
public void RIGHT_ROTATE(RedBlackTree T, RedBlackTreeNode x){
//右旋结点父结点不能为空
if ( IsNil(x.getParent()) == true )
return;
//定义y结点
RedBlackTreeNode y = x.getParent();
//x右子树 -> y左子树
y.setLeft(x.getRight());
//y -> x右子树父结点
x.getRight().setParent(y);
//y父结点 -> x父结点
x.setParent(y.getParent());
//x -> y父结点左/右子树或根结点
if( IsNil(y.getParent()) == true){
//y为根结点，x设为根结点
T.setRoot(x);
}else if( y.getParent().getLeft() == y){
//y为左子树，x设为左子树
y.getParent().setLeft(x);
}else{
//y为右子树，x设为右子树
y.getParent().setRight(x);
}
//y -> x右子树
x.setRight(y);
//x -> y父结点
y.setParent(x);
}
//前序遍历
public void preorder(RedBlackTreeNode t){
if(IsNil(t) == false){
System.out.println(t.getKey());
preorder(t.getLeft());
preorder(t.getRight());
}
}
//中序遍历
public void midorder(RedBlackTreeNode t){
if(IsNil(t) == false){
midorder(t.getLeft());
System.out.println(t.getKey());
midorder(t.getRight());
}
}
//后序遍历
public void postorder(RedBlackTreeNode t){
if(IsNil(t) == false){
postorder(t.getLeft());
postorder(t.getRight());
System.out.println(t.getKey());
}
}
}Test.java
public class Test {
public static void main(String[] args) {
RedBlackTree T = new RedBlackTree();
RedBlackTreeNode node1 = T.RB_NODE(5);
T.RB_INSERT(T, node1);
RedBlackTreeNode node2 = T.RB_NODE(10);
T.RB_INSERT(T, node2);
RedBlackTreeNode node3 = T.RB_NODE(15);
T.RB_INSERT(T, node3);
T.preorder(T.getRoot());
}
}
