红黑树在C++ STL 和 java Collection 里面作为Set, Map 的底层存储结构，非常重要。作为CS树中一个特别树种， 理解了它， 差不多就算入门道了。套用钱砚堂赞王芗斋先生的话：(郭老)夫子之墙高千仞，君既入室且登堂。
/*RBTree.java -- Red Black Tree
doc:
0. 红黑树与AVL树的比较：
插入最多只需要2次旋转(插入12时)；树高度最多为2*log(n)
1. 红黑树是2-3-4树的二叉表示。
2. 2-3-4树映射为红黑树的特征：
根节点是黑色的； 不可能出现连续两个红节点；
2-3-4树的一个节点对应到红黑树中一个黑节点。
3. 2-3-4树的插入方法：
沿路分裂4-节点；总是在叶子节点处插入。
网上一直有人问下面的R1-R4插入规则是怎么来的，其实是由2,3推导出的。
2-3-4树插入很容易在纸上画出来，节点转换到红黑树也容易；但是直接画
红黑树要对旋转很熟练才行。
4. 关于X的右旋实际上是指把X的位置提升一层，X的父节点下降一层，
即“右转螺旋升”。像六封四闭跟步后的手下按，腰螺旋上升。
关于类和成员的权限，我的做法是:
1. C文件什么都不加默认是extern，java里面什么都不加默认是package-private，即同一目录内访问没有限制。
2. 如果对应的C文件里面函数前面是static, 则java里面的方法加上private。
3. 如果是强调给第三方用，就加上public。
官方参考http://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html
author: ludi 2014.03
*/
class RBNode
>
{
final static int BLACK = 0, RED = 1;
RBNode
parent, left, right; int color; T nodeva lue; RBNode(T item, RBNode
left, RBNode
right, RBNode
parent, int color) { nodeva lue = item; this.left = left; this.right = right; this.parent = parent; this.color = color; } } public class RBTree
> { RBNode
root; RBNode
NIL = null; public RBTree() {/*构造方法: 这样构造NIL使得它可以像其他节点那样参与旋转*/ if (NIL == null) NIL = new RBNode
(null, null, null, null, RBNode.BLACK); root = NIL; } public void deleteTree(RBNode
t) {/*析构方法*/ if (t != NIL){ deleteTree(t.left); deleteTree(t.right); t = null; } } private void rotate (RBNode
pivot, int type) {/*type == 0: 左旋*/ RBNode
p = pivot.parent, g = pivot.parent.parent; if(0 == type){ p.right = pivot.left; pivot.left = p; pivot.parent = g; p.parent = pivot; if (p.right != NIL) p.right.parent = p; }else{ p.left = pivot.right; pivot.right = p; pivot.parent = g; p.parent = pivot; if (p.left != NIL) p.left.parent = p; } if (p == root) root = pivot; else if (p == g.right) g.right = pivot; else g.left = pivot; } private void split4Node(RBNode
x) {/*提升4-节点并做必要的旋转*/ /*翻转颜色*/ x.color = RBNode.RED; x.left.color = RBNode.BLACK; x.right.color = RBNode.BLACK; RBNode
p = x.parent; if (p.color == RBNode.RED){/*如果父节点是红色则需要旋转*/ RBNode
g = x.parent.parent; g.color = RBNode.RED; if ( p == g.left && x == p.right ){/*x是g的内部孙子*/ rotate(x, 0); x.color = RBNode.BLACK; p = x; /*准备右旋*/ }else if ( p == g.right && x == p.left ){ rotate(x, 1); x.color = RBNode.BLACK; p = x; }else{ p.color = RBNode.BLACK; } rotate(p, p == g.left 1 : 0); } } public boolean add(T item) {/*插入*/ RBNode
curr = root, parent = NIL, newNode; while (curr != NIL){/*查找插入点*/ if (curr.nodeva lue.equals(item)) return false; /*R1 沿路分裂4-节点*/ if (curr.left.color == RBNode.RED && curr.right.color == RBNode.RED) split4Node(curr); parent = curr; if (item.compareTo(curr.nodeva lue) < 0) curr = curr.left; else curr = curr.right; } /*R2 新节点以红节点插入*/ newNode = new RBNode
(item, NIL, NIL, parent, RBNode.RED); if (parent == NIL){ root = newNode; }else{ if (item.compareTo(parent.nodeva lue) < 0) parent.left = newNode; else parent.right = newNode; /*R3 出现连续的红节点需要旋转*/ if (parent.color == RBNode.RED) split4Node(newNode); } root.color = RBNode.BLACK; /*R4 根节点是黑色的*/ return true; } /*下面是非核心方法，仅用来练习二叉树*/ void visitInOrder(RBNode
t){ if(t == NIL)return; visitInOrder(t.left); System.out.print(t.nodeva lue + " "); visitInOrder(t.right); } int height(RBNode
t){ int hl, hr; if(t == NIL)return -1; hl = height(t.left); hr = height(t.right); hl = 1 + (hl > hr hl : hr); System.out.print(t.nodeva lue + ":" + hl + " "); return hl; } } class Test{ public static void main(String[] arg){ RBTree
tree = new RBTree
(); //int[] arr = {40, 20, 10, 35, 50, 25, 30}; int[] arr = {2,15,12,4,8,10,25,35,55,11}; for(int x: arr){ tree.add(x); } System.out.println("tree height: "); tree.height(tree.root); System.out.println(); System.out.println("visitInOrder:"); tree.visitInOrder(tree.ro