c 2 java第2編赤黒樹の挿入

赤と黒の木は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<T extends Comparable<T>>
{
		 final static int BLACK = 0, RED = 1;

		 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;	
	 RBNode<T> NIL = null;

	public RBTree()
	{/*    :     NIL                */
		if (NIL == null)
			NIL = new RBNode<T>(null, null, null, null, RBNode.BLACK);
		root = NIL;
	}

	public void deleteTree(RBNode<T> t)
	{/*    */
		 if (t != NIL){
			  deleteTree(t.left);
			  deleteTree(t.right);
			  t = null;
		 }
	}

	private void rotate (RBNode<T> pivot, int type)
	{/*type == 0:   */
		RBNode<T> 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<T> x)
	{/*  4-         */
		/*    */
		x.color = RBNode.RED;
		x.left.color = RBNode.BLACK;
		x.right.color = RBNode.BLACK;

		RBNode<T> p = x.parent;
		if (p.color == RBNode.RED){/*             */
			RBNode<T> 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<T> curr = root, parent = NIL, newNode;

		while (curr != NIL){/*     */
			if (curr.nodeValue.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.nodeValue) < 0)
				curr = curr.left;
			else
				curr = curr.right;
		}
		
		/*R2          */
		newNode = new RBNode<T>(item, NIL, NIL, parent, RBNode.RED);

		if (parent == NIL){
			root = newNode;
		}else{
			if (item.compareTo(parent.nodeValue) < 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> t){
		if(t == NIL)return;
		visitInOrder(t.left);
		System.out.print(t.nodeValue + " ");
		visitInOrder(t.right);
	}

	 int height(RBNode<T> 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.nodeValue + ":" + hl + " ");
		return hl;
	}



}

class Test{
	 public static void main(String[] arg){
		RBTree<Integer> tree = new RBTree<Integer>();

		//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.root);
		System.out.println();

		tree.deleteTree(tree.root);
		tree = null;

	}
}

/*
ludi@ubun:~/java
$ javac -encoding UTF-8 RBTree.java && java Test
tree height: 
2:0 8:0 11:0 10:1 4:2 15:0 55:0 35:1 25:2 12:3 
visitInOrder:
2 4 8 10 11 12 15 25 35 55 
ludi@ubun:~/java
$ 
*/

 
  削除操作が複雑なので、後で参考にして悟ってから貼り付けます.