红黑树

红黑树 规则
* 1.每个节点不是红色就是黑色
* 2.根总是黑色
* 3.如果节点是红色，则它的两个子节点必须是黑色(反之则不一定)
* 4.从根到叶节点或空子节点的每条路径，必须包括相同数目的黑节点(空节点为黑色)
节点类:

package org.jf.alg.tree;

public class RBNode <T extends Comparable>{

	public static int COLOR_RED = 1;
	public static int COLOR_BLACK = 2;
	private RBNode left;
	private RBNode right;
	private RBNode parent;
	private int color = COLOR_RED;//实际上是父节点指向子节点链的颜色
	
	private T data;
	
	public RBNode(T data)
	{
		this.data = data;
	}
	
	public RBNode(int color,T data)
	{
		this.color = color;
		this.data = data;
	}
	
	
	public T value()
	{
		return this.data;
	}
	
	public void setParent(RBNode parent)
	{
		this.parent=parent;
	}
	
	public RBNode parent()
	{
		return this.parent;
	}
	
	public void setLeft(RBNode left)
	{
		this.left = left;
	}
	public RBNode left()
	{
		return this.left;
	}
	
	public void setRight(RBNode right)
	{
		this.right = right;
	}
	
	public RBNode right()
	{
		return this.right;
	}
	
//	public void setRed()
//	{
//		color=COLOR_RED;
//	}
	
	public void setColor(int color)
	{
		this.color = color;
	}
	
//	public void setBlack()
//	{
//		color=COLOR_BLACK;
//	}
	
	public boolean isRed()
	{
		return color==COLOR_RED;
	}
	
	public boolean isBlack()
	{
		return color==COLOR_BLACK;
	}
	

}

红黑树类:

package org.jf.alg.tree;

/**
 * 
 * 红黑树
 * 
 * @author junfeng.chen
 *
 * @param <T>
 */
public class RBTree <T extends Comparable>
{
	/**
	 * 
	 * 红黑树 规则
	 * 1.每个节点不是红色就是黑色
	 * 2.根总是黑色
	 * 3.如果节点是红色，则它的两个子节点必须是黑色(反之则不一定)
	 * 4.从根到叶节点或空子节点的每条路径，必须包括相同数目的黑节点(空节点为黑色)
	 * 
	 * 
	 * 
	 */
	
	private RBNode root;

	private int count;
	
	public RBTree()
	{
		
	}
	
	public void addData(T data)
	{
		if(data==null)
			return;
		if(root==null)
		{
			root = new RBNode(data);
			root.setColor(RBNode.COLOR_BLACK);
			count++;
			return;
		}
		else
		{
			RBNode node = new RBNode(data);
			RBNode<Comparable> pnode = findParent(root,data);
			if(pnode.value().compareTo(data)>0)//data<pnode -->left
			{
				pnode.setLeft(node);
			
			}
			else
			{
				pnode.setRight(node);
				
			}
			node.setParent(pnode);
			node.setColor(RBNode.COLOR_RED);
			this.fixAfterInsertion(node);
		}
		count++;
	}
	
	
	/**
	 * 
	 * 
	 * 
	 * 
	 * @param x  当前插入的节点
	 * @param parent 父节点
	 */
	private void fixAfterInsertion(RBNode x)
	{
		/**
		 * 以 x p g 分别表示当前插入的节点  x的父节点  和 x的祖父节点(即 p 的父节点)
		 * 
		 * 
		 * 调整节点保持红黑树性质，分三大类情况
		 * 1.p是黑色的  ， 不用调整
		 * 2.p是红色的，x是g的一个外侧子孙
		 * 只要一次旋转和一些颜色变化
		 * {
		 * (1)改变g的颜色
		 * (2)改变p的颜色
		 * (3)以x的祖父节点g为顶点旋转(向x上升的方向旋转)
		 * {
		 * (3-1)若x是g外侧子孙节点，且为p的左子节点，右旋
		 * (3-2)若x是g的外侧子孙节点，且为p的右子节点，左旋
		 * }
		 * 
		 * }
		 * 
		 * 3.p是红色的，x是g的一个内存子孙
		 * 需要2次旋转和一些颜色变化
		 * {
		 * (1)改变x和g的颜色
		 * (2)以x的父节点p为顶点旋转(向着x上升的方向)
		 *    (2-1)若x是p的左子节点，右旋
		 *    (2-2)若x是p的右子节点，左旋
		 * (3)再以x的祖父节点为顶旋转(向x上升的方向)
		 *    
		 * 
		 * }
		 * 
		 * 
		 */
		RBNode p=x.parent();
		//case1
		if(p==null||p.isBlack())
			return;
		RBNode g=p.parent();
		int flag=0;//left +1 right -1  if(flag=0) 内侧 else 外侧
		if(p==g.left())
		{	flag+=1;
			if(x==p.left())
				flag+=1;
			else
				flag+=-1;
		}else
		{
			flag+=-1;
			if(x==p.left())
				flag+=1;
			else
				flag+=-1;
		}
		
		//case2
		if(flag!=0)//
		{
			if(g.isBlack())
				g.setColor(RBNode.COLOR_RED);
			else g.setColor(RBNode.COLOR_BLACK);
			
			p.setColor(RBNode.COLOR_BLACK);
			
			if(x==p.left())
				this.rotateRight(g);
			else
				this.rotateLeft(g);
		}
		else
		{
			boolean right = false;
			if(p==g.right())
				right=true;
			x.setColor(RBNode.COLOR_BLACK);
			if(g.isBlack())
				g.setColor(RBNode.COLOR_RED);
			else
				g.setColor(RBNode.COLOR_BLACK);
			if(x==p.left())
				this.rotateRight(p);
			else
				this.rotateLeft(p);
			
			if(right)
				this.rotateLeft(g);
			else
				this.rotateRight(g);
		}
		
		
		//x 是g的外侧子孙
		//x 是g的内侧子孙
	}
	
	/**
	 * 
	 * 参考算法导论
	 * 右旋
	 *    x y y.right
	 *    旋转支点为x  其左子节点为y，左子节点的由子节点为r
	 *    y成为新的根(取代p的位置)
	 *    x成为y的右孩子
	 *    y的左孩子的右孩子成为x的左孩子
	 *   
	 *   y=x.left
	 *   x.left=y.right
	 *   y.right.parent=x
	 *   y.parent=x.parent
	 *   
	 *   if x.parent is null // x is root
	 *    then root = y
	 *   else if x==x.parent.left
	 *   then x.parent.left=y
	 *   else x.parent.right=y
	 *   y.right=x;
	 *   x.parent=y;
	 * 
	 * @param p
	 */
	private void rotateRight(RBNode x)
	{
		
		RBNode y=x.left(); 
		x.setLeft(y.right());
		if(y.right()!=null)
		y.right().setParent(x);
	    y.setParent(x.parent());
	    
	    if(x.parent()==null)
	    	root=y;
	    else if(x==x.parent().left())
	    	x.parent().setLeft(y);
	    else
	    	x.parent().setRight(y);
	    y.setRight(x);
	    x.setParent(y);
	}
	
	/**
	 * 左旋
	 * x y y.left
	 * 旋转支点为x 其右子节点为y 右子节点的左子节点为left
	 * 
	 * y成为新的根
	 * x成为y的左孩子
	 * y的左孩子成为x的右孩子
	 * 
	 * 
	 * y=x.right
	 * x.right=y.left
	 * y.left.parent=x
	 * y.parent=x.parent
	 * 
	 * if x.parent is null // x is tree root
	 * then root=y
	 * else if x=x.parent.left 
	 *      then x.parent.left=y
	 * else x.parent.right=y
	 * y.left=x;
	 * x.parent=y
	 * 
	 * 
	 * @param p
	 */
	private void rotateLeft(RBNode x)
	{
		RBNode y=x.right();
		x.setRight(y.left());
		if(y.left()!=null)
		y.left().setParent(x);
		y.setParent(x.parent());
		
		if(x.parent()==null)
			root=y;
		else if(x==x.parent().left())
			x.parent().setLeft(y);
		else x.parent().setRight(y);
		y.setLeft(x);
		x.setParent(y);
		
	}
	
	private RBNode findParent(RBNode<Comparable> root,Comparable data)
	{
		/**
		 * 与根比较 
		 * if data>=root
		 * 则查看右子树 如果右子树不存在 则返回根
		 *                     否则 在右子树中查找
		 *else
		 * 则查找左子树  如果左子树存在 则返回根
		 *                      否则 在左子树中查找                    
		 */
		RBNode left = root.left();
		RBNode right = root.right();
		Comparable value_root = root.value();
		if(data.compareTo(value_root)>=0)//右子树
		{
			if(right==null)
				return root;
			else
			{
				return findParent(right, data);
			}
		}
		else//左子树
		{
			if(left==null)
				return root;
			else
				return findParent(left,data);	
		}
		
	}
	
	public boolean contains(T data)
	{
		return false;
	}
	
	public int getCount()
	{
		return this.count;
	}
	
	
	public static void main(String args[])
	{
		RBTree rbTree = new RBTree();
		for(int i=0;i<10;i++)
		{
			rbTree.addData(i);
		}
		
	}
	
	
}