2014.04.03更新插入部分

1. 为什么要以红节点插入？
  如果以黑节点插入，因为我们是在叶节点插入，则到该节点的路径的黑高度增一，导致不平衡，再把它弄平衡就不容易了。因此这里的要点是“时时保持平衡”。

2. 插入的调整为什么要有case1,2,3？
  a,b,c,d的黑高度都不变； 最终状态，插入节点上升了一层，使得树更趋于平衡。
各个case都是局部变换，从a到d至少要经过这么多步骤，没有更少的操作了。

红黑树节点的删除，值替换后不改变红黑属性，归结为删除最多有一个孩子的节点，对应到2-3-4树叶节点的：
1. 4-节点
2. 3-节点
3. 2-节点
   a.兄节点至少是3-节点: 两次转移.
   b.弟节点是2-节点:一次转移，一次融合.
   c.父节点是2-节点:cascading
2-3-4树的删除太复杂，估计没人用在实践中；并且还有个缺点：
真正该删除的保留，而其他节点被删除，如果仍然被程序其他部分持有，就悲剧了。
因此算法导论第三版做了更改，许多其他书籍引用还是第2版的做法。

删除后的调整

/*
         |
         B
      /     \
	 A       D
	/ \    /   \
   a   b  C     E
         / \   / \
		c   d e   f
*/

0. 只涉及到A到E五个节点，周围节点a-f不变。

1. 最终目的状态是经过A的黑高度加一，其他节点高度不变。

2. 初始状态是经过A的黑高度少了一。

3. 初始树的形态有多种： 

(A,D) = (b,r)

 (A,D,Dl,Dr) = (b,b,b,b) 

(A,D,Dl,Dr) = (b,b,r,b) 

(A,D,Dl,Dr) = (b,b,*,r)

其中Dl,Dr分别是D的左右儿子，*表示颜色任意；

Q: 插入一个元素后马上删除之，树的形态会不会变？
A: 见下面的输出，只差一个局部的旋转而已。

图片来源: http://blog.chinaunix.net/uid-26575352-id-3061918.html

语言注记
====
L1 如果我们想这样定义类:
Struct Node{
 int val;
 Struct Node *child[2];
};可以简化fixup()代码，但是java不支持，只能这样:Node.java
class Node{
 int val;
 Node[] child = {null, null};
 public Node(int _val, Node l, Node r){
  val = _val;
  child[0] = l; child[1] = r;
 }

 public static void main(String[] arg){
  Node b = new Node(1, null, null),
    c = new Node(2, null, null),
    a = new Node(0, b, c);

  System.out.printf("%d %d\n", a.child[0].val, a.child[1].val);

 }
}
如果非要这样子，我们自然引出这样的问题：因为数组是在堆上分配的，java如何避免内存碎片化？

L2 我的jdb 不能stop in 行号，只能这样stop in RBTree.plant断点在函数开头，
如果函数很长则颇为不便，是不是jdk 1.5 for windows 的不支持呢？

附jdb #gdb 的对比
====
stop in RBTree.plant #break plant
clear #delete
cont #c

locals #info local
dump var #print *var
print val #print var
set val = x # print val = x
where  #bactrace
up, down #frame n
next, step #next, step

threads/thread #info thread/ thread n

monitor cmd #?
catch, watch #?
trace #跟踪函数的进出

classes：列举当前已知的类。
suspend, resume：线程的suspend和resume，需要加线程号为参数。
methods, fileds：列举类的方法和成员变量。

树的输出，根据后序和中序可以重构二叉树。

 附代码：

/*RBTree.java -- Red Black Tree

author: ludi 2014.04
*/
class RBNode<T extends Comparable<T>>
{
		 RBNode<T> parent, left, right;
		 int color;
		 T nodeValue;

		 RBNode(T item, RBNode<T> left, RBNode<T> right,
					 	  RBNode<T> parent, int color)
		{
			nodeValue = item;
			this.left = left;
			this.right = right;
			this.parent = parent;
			this.color = color;
		}
}

public class RBTree<T extends Comparable<T>>
{
	 RBNode<T> root;	
	 RB