红黑树（Red-Black Tree），一种特殊的二叉查找树，红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)；
红黑树主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常高；
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍；
例如Java集合中TreeMap，TreeSet，HashMap等，以及Linux虚拟内存的管理
红黑树的特性:
- 每个节点或者是黑色，或者是红色；
- 根节点是黑色；
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点]；
- 如果一个节点是红色的，则它的子节点必须是黑色的；
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
性质3中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
性质4的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。 因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1) 。
性质5是成为红黑树最主要的条件，红黑树的插入、删除操作都是为了遵守这个规定。红黑树是相对是接近平衡的二叉树。它以性质 5 作为一种平衡方法，使自己的性能得到了提升。特性5确保没有一条路径会比其他路径长出俩倍。
当对红黑树进行增删操作时，以上约束条件可能被破坏，需要通过调整使得查找树重新满足红黑树的约束条件。调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作：左旋和右旋。
一个不错的在线演示添加、删除红黑树：http://sandbox.runjs.cn/show/2nngvn8w
红黑树node定义：
class Entry<K extends Comparable<K>,V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public Entry(K key, boolean color, Entry<K,V> parent, Entry<K,V> left,Entry<K,V> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
红黑树插入：
图解；来源自：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/5-TreeSet%20and%20TreeMap.md
add.png
/**
* put方法 insert到红黑树
*/
public V put(K key, V value) {
if(key == null) {
throw new NullPointerException("key不能为空！");
}
int cmp;
Entry<K,V> parent;
Entry<K,V> t = root;
// 第一次插入
if (t == null) {
root = new Entry<>(key, value, null);
root.color = BLACK;
return null;
}
do {
parent = t;
cmp = key.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
// 找到key的value，更新value并返回旧value
V oldValue = t.value;
t.value = value;
return oldValue;
}
} while (t != null);
// 插入新node
Entry<K,V> entry = new Entry(key, value, parent);
// 设置新增节点的颜色为红色
entry.color = RED;
if (cmp < 0)
parent.left = entry;
else
parent.right = entry;
// 将它重新修正为一颗二叉查找树
fixAfterInsertion(entry);
return null;
}
/*
* 对红黑树的节点进行左旋转
* 左旋示意图(对节点x进行左旋)
* px px
* / /
* x y
* / \ --(左旋)-- / \
* lx y x ry
* / \ / \
* ly ry lx ly
*/
private void leftRotate(Entry<K, V> x) {
// 设置x的右孩子为y
Entry<K, V> y = x.right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.left;
if (y.left != null)
y.left.parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.parent;
if (x.parent == null) {
this.root = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
} else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/*
* 对红黑树的节点进行右旋转
* 右旋示意图(对节点y进行左旋)：
* py py
* / /
* y x
* / \ / \
* x ry lx y
* / \ / \
* lx rx rx ry
*/
private void rightRotate(Entry<K, V> y) {
// 设置x是当前节点的左孩子。
Entry<K, V> x = y.left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.parent;
if (y.parent == null) {
this.root = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
else
y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
/**
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
* @param entry 新插入的结点
*/
private void fixAfterInsertion(Entry<K, V> entry) {
Entry<K, V> parent,gparent;
// 若父节点存在，并且父节点的颜色是red
while( (parent = parentOf(entry))!= null && isRed(parent)) {
gparent = parentOf(parent); // 祖父节点
// 父节点是 祖父节点的左子树
if(gparent.left == parent) {
Entry<K, V> uncle = gparent.right; // 叔节点
// 叔节点 存在且是红色
if( (uncle!=null) && colorOf(uncle) == RED) {
uncle.color = BLACK;
parent.color = BLACK;
gparent.color = RED;
entry = gparent;
continue;
}
// 叔叔是黑色，且当前节点是右孩子
if(parent.right == entry) {
Entry<K, V> tmp;
leftRotate(parent);
tmp = parent;
parent = entry;
entry = tmp;
}
// 叔叔是黑色，且当前节点是左孩子
parent.color = BLACK;
gparent.color = RED;
rightRotate(gparent);
} else {
// 父节点是 祖父节点的右子树
Entry<K, V> uncle = gparent.left; // 叔节点
// 叔节点 存在且是红色
if( (uncle!=null) && colorOf(uncle) == RED) {
uncle.color = BLACK;
parent.color = BLACK;
gparent.color = RED;
entry = gparent;
continue;
}
// 叔叔是黑色，且当前节点是左孩子
if(parent.left == entry) {
Entry<K, V> tmp;
rightRotate(parent);
tmp = parent;
parent = entry;
entry = tmp;
}
// 叔叔是黑色，且当前节点是右孩子
parent.color = BLACK;
gparent.color = RED;
leftRotate(gparent);
}
}
// 将根节点设为黑色
root.color = BLACK;
}
测试添加：
public class Main {
public static void main(String[] args) {
RBTree<Integer, String> tree = new RBTree<Integer, String>();
int[] ins = new int[]{20,5,32,3,10,45,8,16,6};
for (int i : ins) {
tree.put(i, ""+ i);
}
tree.printZhong();
tree.printXian();
}
}
结果：
中序遍历：[[3 : 3]+(false), [5 : 5]+(true), [6 : 6]+(true), [8 : 8]+(false), [10 : 10]+(false), [16 : 16]+(false), [20 : 20]+(true), [32 : 32]+(false), [45 : 45]+(true)]
先序遍历：[[10 : 10]+(false), [5 : 5]+(true), [3 : 3]+(false), [8 : 8]+(false), [6 : 6]+(true), [20 : 20]+(true), [16 : 16]+(false), [32 : 32]+(false), [45 : 45]+(true)]
其中：false为黑；true为红
红黑树.png
红黑树删除操作：
删除的节点的两种情况：
1）删除点p的左右子树都为空，或者只有一棵子树非空。
2）删除点p的左右子树都非空。
对于上述情况1，处理起来比较简单，直接将node删除（左右子树都为空时），或者用非空子树替代node（只有一棵子树非空时）；对于情况2，可以用node的后继s（树中大于node的最小的那个元素）代替node，然后使用情况1删除s（此时s一定满足情况1）。
删除原理示意图：
TreeMap_fixAfterDeletion.png
删除节点程序：
/**
* 删除节点
*/
public void remove(K key) {
Entry<K, V> node;
if ((node = search(root, key)) != null)
remove(node);
}
private void remove(Entry<K, V> node) {
Entry<K, V> child, parent;
boolean color;
// 删除的node不为空
if (node.left != null && node.right != null) {// 2. 删除点p的左右子树都非空。
Entry<K,V> s = successor(node);// 得到后继
node.key = s.key;
node.value = s.value;
node = s; // 为了删除后继节点，不用递归，这么赋值的；
}
Entry<K,V> replacement = (node.left != null ? node.left : node.right);
if (replacement != null) { // 删除点node只有一棵子树非空；
Entry<K, V> parentNode = parentOf(node);
if(parentNode == null) {
this.root = replacement;
}
if(parentNode.left == node) {
parentNode.left = replacement;
} else {
parentNode.right = replacement;
}
replacement.parent = parentNode;
node.left = node.right = node.parent = null; // 置为null；
if (node.color == BLACK)
fixAfterDeletion(replacement);// 调整
} else if (node.parent == null) { // node没有子节点，并且没有父节点
this.root = null;
} else {
if (node.color == BLACK)
fixAfterDeletion(node);// 调整
if (node.parent != null) {
if (node == node.parent.left)
node.parent.left = null;
else if (node == node.parent.right)
node.parent.right = null;
node.parent = null;
}
}
}
/**
* 红黑树删除修正函数
*
* 在从红黑树中删除节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
* @param node 待修正的节点
*/
private void fixAfterDeletion(Entry<K,V> node) {
while (node != root && colorOf(node) == BLACK) {
// node为其父节点的左子树
if (node == leftOf(parentOf(node))) {
Entry<K,V> bro = rightOf(parentOf(node));
// node的兄弟节点为红
if (colorOf(bro) == RED) {
setColor(bro, BLACK);
setColor(parentOf(node), RED);
leftRotate(parentOf(node));
bro = rightOf(parentOf(node));
}
// node的兄弟节点的两个子树为黑
if (colorOf(leftOf(bro)) == BLACK && colorOf(rightOf(bro)) == BLACK) {
setColor(bro, RED);
node = parentOf(node);
} else {
// node的兄弟节点的左子树为红，右子树为黑
if (colorOf(rightOf(bro)) == BLACK) {
setColor(leftOf(bro), BLACK);
setColor(bro, RED);
rightRotate(bro);
bro = rightOf(parentOf(node));
}
// node的兄弟节点的右子树为红，左子树随意
setColor(bro, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(bro), BLACK);
leftRotate(parentOf(node));
node = root;
}
} else {
Entry<K,V> sib = leftOf(parentOf(node));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(node), RED);
rightRotate(parentOf(node));
sib = leftOf(parentOf(node));
}
if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
node = parentOf(node);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
leftRotate(sib);
sib = leftOf(parentOf(node));
}
setColor(sib, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(leftOf(sib), BLACK);
rightRotate(parentOf(node));
node = root;
}
}
}
setColor(node, BLACK);
}
/**
* 寻找p的后继（树中大于p的key的最小的那个元素）
* @param p
* @return
*/
private Entry<K, V> successor( Entry<K, V> p) {
if(p == null) {
return null;
}
Entry<K, V> node = p.right;
if(node != null) {
while(node.left != null) {
node = node.left;
}
return node;
}
// 因为设定p左右子树不为空，所以不会走到这一步
return null;
}
