发明轮子之“红黑树 二”

下面是红黑树类的实现：
由于本人的java水平有限，写得不是很好，希望大牛们指点
RedBlackTree.java

package datastruct;

import static java.lang.System.out;

import java.util.Stack;

import common.Color;
import common.TreeNode;
/**
 * 
 * @Author   changzhi
 * @Email    [e-mail]
 * @Date     Oct 27, 2009
 * @File     RedBlackTree.java
 * @Project	 tree
 */
public class RedBlackTree<T extends Comparable<T>> {
	/**
	 * 树根
	 */
	private TreeNode<T> root;
	/**
	 * 哨兵节点
	 * can't use static var
	 */
	private TreeNode<T> nil;
	
	public RedBlackTree()
	{
		nil = new TreeNode<T>(Color.BALCK,null,null,null,null);
		this.root=nil;
	}
	public RedBlackTree(TreeNode<T> root)
	{
		nil = new TreeNode<T>(Color.BALCK,null,null,null,null);
		this.root=root;
		root.setParent(nil);
		root.setLeft(nil);
		root.setRight(nil);
	}
	/**
	 * 
	 * @param key
	 * @return int
	 * 增加一个节点，初始其颜色为红色，这样将会导致不满足红黑树的性质，故
	 * 在这之后还需要对此树进行调整。
	 * 返回0添加成功
	 * 返回1有相同的key,添加失败
	 * 返回-1添加失败
	 */
	public int addNode(T key)
	{
		TreeNode<T> x = root;
		TreeNode<T> y = nil ;
		//空树
		if(root == nil)
		{
			root = new TreeNode<T>(Color.BALCK,key,nil,nil,nil);
			return 0;
		}
		//不是空树，引用y即指向插入节点的父节点
		else
		{
			while(x != nil)
			{
				y = x;
				if(x.getKey().compareTo(key) == 0)
					return 1;
				else if(x.getKey().compareTo(key) > 0)
					x = x.getLeft();
				else
					x = x.getRight();
			}
		}
		TreeNode<T> c = new TreeNode<T>(Color.RED,key,nil,nil,y);
		if(y.getKey().compareTo(key) > 0)
			y.setLeft(c);//成为左子树
		else
			y.setRight(c);//成为右子树
		c.setLeft(nil );
		c.setRight(nil);
		insert_fixup(c);//调整
		return 1;//插入成功
	}
	/**
	 * @param c
	 * 插入一个红节点后，为了维持红黑树的性质不变
	 * 定制的修复程序
	 */
	private void insert_fixup(TreeNode<T> c)
	{
		TreeNode<T> u = null;
		while(c.getParent().getColor() == Color.RED)//父节点是红色，才需要调整
		{
			if(c.getParent() == c.getParent().getParent().getLeft())//考虑是祖父的左孩子时
			{
				u = c.getParent().getParent().getRight();//叔父节点
				if(u.getColor() == Color.RED)            //情况一
				{
					/* 如果叔父节点是红色的，而且父节点也是红色的，那么
					 * 只需要把叔父和父亲节的置为黑色，然后把祖父节点置为红色
					 * 这样就顺利的把需要调整的节点上移至祖父节点进行下一步调整
					 */
					c.getParent().setColor(Color.BALCK);
					c.getParent().getParent().setColor(Color.RED);
					u.setColor(Color.BALCK);
					c = c.getParent().getParent();
				}
				else //情况二和情况三
				{
					if(c == c.getParent().getRight())   //情况二
					{
						/* 如果是父亲的右孩子，就需要左旋转，将情况二变成情况三,
						 * 旋转的节点是其父亲节点
						 */
						c = c.getParent();
						left_rotate(c);
					}
					/* 下面的处理是针对情况三，即叔父节点为黑色，父亲节点为红色，
					 * 而且是父亲的左孩子，此时需要改变父亲和祖父的颜色，然后对
					 * 祖父节点进行右旋
					 */
					c.getParent().setColor(Color.BALCK);
					c.getParent().getParent().setColor(Color.RED);
					right_rotate(c.getParent().getParent());
				}
			}
			else//考虑是祖父的右孩子时
			{
				/* 这种情况与上面的是完全对称的，故这此不在详叙
				*/
				u = c.getParent().getParent().getLeft();//right tree
				if(u.getColor() == Color.RED)
				{
					c.getParent().setColor(Color.BALCK);
					c.getParent().getParent().setColor(Color.RED);
					u.setColor(Color.BALCK);
					c = c.getParent().getParent();
				}
				else
				{
					if(c == c.getParent().getLeft())
					{
						c = c.getParent();
						right_rotate(c);
					}
					c.getParent().setColor(Color.BALCK);
					c.getParent().getParent().setColor(Color.RED);
					left_rotate(c.getParent().getParent());
				}
			}
		}
		root.setColor(Color.BALCK);
	}
	/**
	 * @param node 此节点即是需要下移的节点
	 * @方法  左旋
	 */
	private void left_rotate(TreeNode<T> node)
	{	
		/* 保存右子树的引用
		*/
		TreeNode<T> y = node.getRight();
		/* 将node的右子树设置为y的左子树，如果y的左子树不空
		 * 则将其的父亲节点设置为node
		 * */
		node.setRight(y.getLeft());
		if(y.getLeft() != nil)
			y.getLeft().setParent(node);
		/* 将y节点上调，自然node节点就下调，成为y的子树
		 * */
		y.setParent(node.getParent());
		if(node.getParent() == nil)
			root=y;
		else
		{
			/*判断node节点是左子树还是右子树*/
			if(node == node.getParent().getLeft())
				node.getParent().setLeft(y);
			else
				node.getParent().setRight(y);
		}
		y.setLeft(node);
		node.setParent(y);
	}
	/**
	 * @param node 此节点即是需要下移的节点
	 * @方法  右旋
	 */
	private void right_rotate(TreeNode<T> node)
	{
		/*此处右旋又和左旋对称，故不详叙*/
		TreeNode<T> y = node.getLeft();
		node.setLeft(y.getRight());
		if(y.getRight() != nil)
			y.getRight().setParent(node);
		y.setParent(node.getParent());
		if(node.getParent() == nil)
			root=y;
		else
		{
			if(node == node.getParent().getRight())
				node.getParent().setRight(y);
			else
				node.getParent().setLeft(y);
		}
		y.setRight(node);
		node.setParent(y);
	}
	/**
	 * @param key
	 * @return 删除成功与否
	 * @方法   删除数据为key的节点
	 */
	public boolean deleteNode(T key)
	{
		TreeNode<T> y = nil;
		TreeNode<T> x = root;
		/**
		 * 存取查找需要删除的节点的引用
		 */
		TreeNode<T> target;
		/**
		 * 下面是查找过程，暂存于x中
		 */
		while(x != nil)
		{
			if(x.getKey().compareTo(key) == 0)
				break;
			else if(x.getKey().compareTo(key) > 0)
				x = x.getLeft();
			else
				x = x.getRight();
		}
		/**
		 * 未找到，返回false
		 */
		if(x == nil)
			return false;
		/**
		 * 重新存到target中，因为后面要用x
		 */
		target = x;
		/**
		 * 如果x最多只用一颗子树，则直接赋值
		 * 否则，需要找到x的第一个前驱节点，赋值给y
		 */
		if(x.getLeft() == nil || x.getRight() == nil)
			y = x;
		else
			y = findFront(x);
		/**
		 * 如果y的左子树不空
		 */
		if(y.getLeft() != nil)
			x = y.getLeft();
		else
			x = y.getRight();
		/**
		 * 设置x的父亲节的，即为以前y的父亲节的
		 */
		x.setParent(y.getParent());
		/**
		 * 如果y是根节点，则x成为了根节点
		 * 否则，将x设置为y的父亲节的的子树
		 */
		if(y.getParent() == nil)
			root = x;
		else
		{
			if(y == y.getParent().getLeft())
				y.getParent().setLeft(x);
			else
				y.getParent().setRight(x);
		}
		if(y != target)
		{//copy y's data into target
			target.setKey(y.getKey());
		}
		if(y.getColor() == Color.BALCK)
			delete_fixup(x);
		return true;
	}
	
	/**
	 * @param node
	 * 用于删除节点后，为了维持红黑树的性质
	 * 来定制的修复程序
	 */
	private void delete_fixup(TreeNode<T> node)
	{
		/*用于保存兄弟节点*/
		TreeNode<T> w = null;
		/*保证需要调整的节点是黑色的且不是根*/
		while(node != root && node.getColor() == Color.BALCK)
		{
			/*一、考虑是左子树的情况*/
			if(node == node.getParent().getLeft())
			{
				w = node.getParent().getRight();
				/* 情况一：兄弟的颜色是红色的，此种情况需要其变成以下的情况二、三和四
				 * 因此需要将这个红色兄弟节点从右边移到左边去
				 * 于是将w的颜色变黑，其父节点变红，然后其父节点左旋
				 * 最后把w重新指向兄弟节点*/
				if(w.getColor() == Color.RED)
				{
					w.setColor(Color.BALCK);
					node.getParent().setColor(Color.RED);
					left_rotate(node.getParent());
					w = node.getParent().getRight();//new w
				}
				/* 情况二：兄弟节点为黑色而且连个孩子均为黑色，这种情况比较好办
				 * 因为左边少一个黑节点，而右边接连有两个，于是在右边减少一个，
				 * 然后把node指向其父节点，即将黑节点的需求上移
				 * */
				if(w.getLeft().getColor() == Color.BALCK && w.getRight().getColor() == Color.BALCK)
				{
					w.setColor(Color.RED);
					node = node.getParent();
				}
				/* 情况三：兄弟节点为黑色，兄弟的右孩子是黑色的，左孩子是红色的
				 * 情况四：兄弟节点为黑色，兄弟的右孩子是红色的
				 * */
				else 
				{
					/* 这个判断用于情况三，此时需要将w的左孩子颜色变为黑色，w变为
					 * 红色，然后右旋，w重新赋值
					 * 由此一来就将情况三变为情况四*/
					if(w.getRight().getColor() == Color.BALCK)
					{
						w.getLeft().setColor(Color.BALCK);
						w.setColor(Color.RED);
						right_rotate(w);
						w = node.getParent().getRight();
					}
					/* 以下是针对情况四的处理
					 * 可以将node的父亲的节点设置为黑色，w设置为原来node的
					 * 父亲节点的颜色，而且w的右孩子的颜色设置为黑色
					 * 然后左旋，即可将左边的黑高度加一，而右边的黑高度不变*/
					w.setColor(node.getParent().getColor());
					node.getParent().setColor(Color.BALCK);
					w.getRight().setColor(Color.BALCK);
					left_rotate(node.getParent());
					node = root;//finished
				}
			}
			/* 二、考虑是右子树的情况
			 * 此处跟上面的左子树情况完全对称，不详叙*/
			else
			{
				w = node.getParent().getLeft();
				if(w.getColor() == Color.RED)
				{
					w.setColor(Color.BALCK);
					node.getParent().setColor(Color.BALCK);
					right_rotate(node.getParent());
					w = node.getParent().getLeft();//new w
				}
				if(w.getLeft().getColor() == Color.BALCK && w.getRight().getColor() == Color.BALCK)
				{
					w.setColor(Color.RED);
					node = node.getParent();
				}
				else
				{
					if(w.getLeft().getColor() == Color.BALCK)
					{
						w.getRight().setColor(Color.BALCK);
						w.setColor(Color.RED);
						left_rotate(w);
						w = node.getParent().getLeft();
					}
					w.setColor(node.getParent().getColor());
					node.getParent().setColor(Color.BALCK);
					w.getLeft().setColor(Color.BALCK);
					right_rotate(node.getParent());
					node = root;//finished
				}
			}
		}
		node.setColor(Color.BALCK);
	}
	
	/*
	 * 寻找node的前驱节点，并返回其引用*/
	private TreeNode<T> findFront(TreeNode<T> node)
	{
		TreeNode<T> y = node;
		TreeNode<T> x = node.getLeft();
		while(x != nil)
		{
			y = x;
			x = x.getRight();
		}
		return y;
	}
	/**
	 * @param key
	 * @return Object
	 */
	public boolean findByKey(T key)
	{
		return find(root,key)!=null;
	}
	private T find(TreeNode<T> node, T key)
	{
		/**
		 * 1，没有节点
		 * 2，此节点为叶子节点，则其指向nil节点，判断nil节点只需左子树或右子树为空即可
		 * 如果是以上情况，直接返回null，即找不到该关键字
		 */
		if(node == null || node == nil)// || node.getRight() == null) 
			return null;
		/**
		 * 找到相等关键字，返回
		 */
		if(node.getKey().compareTo(key) == 0)
			return node.getKey();
		/**
		 * 在左子树上找
		 */
		T left = find(node.getLeft(),key);
		if(left != null)
			return left;
		/**
		 * 在右子树上找
		 */
		T right = find(node.getRight(),key);
		if(right != null)
			return right;
		return null;
	}
	/**
	 * 
	 * @param order 
	 * order = 1 先序
	 * order = 0 中序
	 * order = -1 后序
	 */
	public void travelTree(int order)
	{
		if(order == 0)
			midTravel(root);//中序
		else if(order == -1)
			afterTravel(root);//后序
		else
			preTravel(root);//先序
		
	}
	/**
	 * 先序遍历
	 * @param node
	 */
	private void preTravel(TreeNode<T> node)
	{
		if( node == null || node == nil)
			return ;
		out.println("[ key = "+node.getKey()+" ],[ color = "+node.getColor()+" ]");
		midTravel(node.getLeft());
		midTravel(node.getRight());
	}
	/**
	 * 中序遍历
	 * @param node
	 */
	private void midTravel(TreeNode<T> node)
	{
		if( node == null || node == nil)
			return ;
		midTravel(node.getLeft());
		out.println("[ key = "+node.getKey()+" ],[ color = "+node.getColor()+" ]");
		midTravel(node.getRight());
	}
	/**
	 * 后序遍历 非递归实现
	 * @param node
	 */
	private void afterTravel(TreeNode<T> node)
	{
		Stack< TreeNode <T> > stack = new Stack< TreeNode<T> >();
		TreeNode<T> p = null;
		/**
		 * 记录上一个访问节点的引用，用于判断其父节点是否访问过
		 */
		TreeNode<T> pre = node;
		while(node != nil)
		{
			stack.push(node);
			node = node.getLeft();
		}
		while(stack.size() > 0)
		{
			p = stack.peek();
			if(p.getRight() != nil && p.getRight() != pre)
			{
				TreeNode<T> temp = p.getRight();
				while(temp != nil)
				{
					stack.push(temp);
					temp = temp.getLeft();
				}
			}
			else
			{
				p = stack.pop();
				out.println("[ key = "+p.getKey()+" ],[ color = "+p.getColor()+" ]");
				pre = p;
			}
		}
	}
	public String toString()
	{
		out.println("order is :");
		travelTree(0);
		return "end.";
	}
}