数据结构之从2-3 树理解红黑树
2-3 树
在介绍红黑树之前有必要先介绍一下2-3树，因为直接理解红黑树是有一定难度的，而红黑树其实是2-3 树的等价二叉树形式，清楚了2-3 树的逻辑，红黑树自然就迎刃而解了。
2-3 树是最简单的B树，是搜索树的一种，其结构中有两种节点，有两个孩子的被称为2-节点，三个孩子的被称为3-节点：
2-3树节点
它满足BST的基本性质，所谓满足性质是：对于一个2-节点来说其左子树的值比该节点小，右子树值比该节点大。对于一个3-节点来说其中的两个值从小到大排列，中间孩子的值是介于该节点两个值之间的。
2-3树是一棵绝对平衡的树结构，在插入过程中会始终保持绝对平衡，绝对平衡是指：在该树中，对于任意节点，其子树的高度相等；或者从根出发到该树任意一个叶子节点经过的节点数相等。
下面通过2-3树的建树过程来看一下为什么2-3树是一棵绝对平衡树，假设添加的顺序是：
42，37，12，18，6，11，5
- 2-3树的添加过程除根节点外不会往空位置添加元素，它会依次添加出2-节点，3-节点；当新来一个元素要往3-节点继续添加时，则先形成4-节点，当然此时已不符合2-3树的定义了，再将4-节点分裂即可：
情况1
- 若叶子节点形成4-节点，则分裂后的根节点要与其父亲节点融合：
情况2
- 若分裂后与父亲节点融合导致父亲节点成为4-节点，则父亲节点再进行一次分裂：
情况3
自此，这个建树过程已完毕，其中要处理的一共就这三种情况，可以看到，这种建树方式可以保证所得的树是一棵绝对平衡树。而且可以发现 ，我们的添加过程是从大到小的，若是往BST中添加这些元素，树早已偏斜。可见2-3树的平衡性。
红黑树与2-3树的等价
好了，现在可以开始介绍红黑树了，红黑树是一种二叉树。红黑树与2-3树之所以等价是因为红黑树相当于在2-3树的节点上做了对应，2-节点对应到红黑树变化不大，3-节点对应到红黑树则要做相应变化：
红黑树与2-3树等价
其中红色节点表示在红黑树对应的原2-3树中，该节点与其父亲节点是融合在一块的。
将红色节点放在左边的红黑树叫做左倾红黑树，相应地有有右倾红黑树，原理是一致的。本篇所有讨论均基于左倾红黑树。
在算法导论中，作者Thomas H. Cormen直接给出了红黑树的性质（定义）：
红黑树定义
翻译：
1.每个节点都是红或黑
2.根节点是黑色
3.每个叶子（这里的叶子是指最后的空节点）是黑色
4.若一个节点是红色，则它的孩子节点都是黑色
5.从任一节点到叶子节点，经过的黑色节点个数相等
如果直接看这个定义一定会懵逼的，但是现在再来看这个定义就清晰多了，其中1、2显然，3、4、5都可以由2-3树往红黑树的转换中推出。值得注意的是，红黑树并不是AVL那样的平衡二叉树，可以计算得到红黑树的最大高度可能是2logn级别（当经过的每个黑节点之前都有红节点时），但从任一节点到叶子节点，经过的黑色节点个数相等，故也称红黑树为“黑平衡”。
红黑树的添加（插入）操作
接下来我们讨论红黑树的添加元素操作，由红黑树的性质不难知道，插入的每个元素初始必然都是红色的，不过根比较特殊，根是黑色的这是定义。对于本篇实现的红黑树的添加操作，不失一般性，共有5种情况：
- 1.前两种对应于2-3树向2节点插入元素。插入节点在黑色节点左侧（就是比父亲节点小），则直接插入。
- 2.插入节点在黑色节点右侧，此时执行左旋转操作：
左旋转
- 3.接下来三种是对应于2-3树向3-节点添加元素。case1：添加x2在黑色节点右边，形成3-节点，则进行颜色翻转：
颜色翻转
- 4.case2：添加在x的左侧形成3-节点，先执行右旋转，再进行颜色翻转即可：
右旋转-颜色翻转
- 5.case3：添加在左侧的右侧形成3-节点，先执行左旋转变为case4，再按case4处理：
按case4
通过上面的分析，不难实现出一个红黑树，下面给出红黑树类的具体实现：
'''RBTree.java'''
import java.util.ArrayList;
public class RBTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;//私有且不可更改
private class Node{
public K key;
public V value;
public Node left, right;
public boolean color;//true代表红色
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;//初始化为红色,因为新节点总要和某个节点融合
}
}
private Node root;
private int size;
public RBTree(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
//辅助函数判断节点颜色
private boolean isRed(Node node){
if(node == null)
return BLACK;
return node.color;
}
private void flipColors(Node node){
//颜色翻转
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
// 向RB树中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK;//保持根节点为黑色
}
//红黑树左旋转,返回旋转后的根
private Node leftRotate(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
//右旋转
private Node rightRotate(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// 向以node为根的RB树中插入元素(key, value)，递归算法
// 返回插入新节点后树的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value);
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
//维护红黑树性质
//下面三个操作不是互斥的而是每次都要看一下是否满足各个的条件，可能都要做
if(isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
if(isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);
if(isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
}
// 返回以node为根节点索树中，key所在的节点
private Node getNode(Node node, K key){
if(node == null)
return null;
if(key.equals(node.key))
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
public boolean contains(K key){
return getNode(root, key) != null;
}
public V get(K key){
Node node = getNode(root, key);
return node == null ? null : node.value;
}
public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 返回以node为根的树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 删除掉以node为根的树中的最小节点
// 返回删除节点后新的树的根
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
可以看到，上述代码是在BST代码的基础上修改的，相比于BST的代码，在节点中加入了表示颜色的布尔变量；设置了辅助函数左旋转、右旋转以及颜色翻转；添加操作中对红黑树的性质进行维护。
（由于删除操作有点复杂，暂时没有给出，过两天补上。。。）
