数据结构之查找（五）红黑树

一、相关的

 

       数据结构之查找（一）基本内容

       数据结构之查找（二）二叉查找树

       数据结构之查找（三）平衡二叉树

 

二、红黑树的疑惑 参考阅读

     

      1.红黑树的目的

        =》当然也是为了保证查找树的最坏情况也也有O(log N)的查找效率 

 

      2.那么这里还有个问题红黑树和AVL树的优缺点

        =》因为他们的目的是相同的等看完这部分了再说吧

 

      3.我自己的疑惑红黑树的颜色干什么用的

         =》我很惊奇数据怎么分颜色了，作用是什么

 

      4.这些查找的用途是什么那？

         =》我只是知道有这么个数据结构，那么用于什么方面哪？

         =》其实这个自问很白痴，肯定是查找，但是实际接触的应用场景哪？（知道了补充）

         =》系统中的内存管理好象用的是红黑树

         =》B树在数据库、搜索上用

 

三、红黑树 参考维基百科

      

        1.约束

          （1）节点是红色或黑色

          （2）根是黑色

          （3）所有叶子都是黑色（叶子是NIL节点=》结束标志）

          （4）红色的两个子节点都是黑市（从每个叶子到根的所有路径上不能有两个连续的红色节点）

          （5）从任一节点到其每个叶子节点所有的路径都包含相同数目的黑色节点

            =》（4）（5）确定了路径只差在两倍的范围之内

      

           

           2.实现

              =》本质上红黑书还是查询树的性质

           2.1插入

                首先插入的节点是用红色的？

                =》如果设置为黑色那么这棵树就该是满二叉树符合要求吧

  

//可能出现的情况
//插入过程中如果是根节点
 =》那么把颜色改为黑色

 

//可能出现的情况2
//父节点时黑色的
 =》因为插入的是红色的
 =》路径黑色数目没有改变
 =》黑色子节点是红色还是定的

 

//可能出现的情况3
//父节点出入的是红色的并且父节点的兄弟节点也是红色
=》处理办法把父节点和它的兄弟节点改为红色
=》祖父节点改为红色（因为路径上的黑色数目不改变）
=》改变之后又和可能出现的问题是祖父的节点情况跟当前一样   

 

 
  

//可能出现的情况4
//父节点时红色但是父节点的兄弟节点是黑色或者缺少
=》处理办法进行一次左旋转
//然后按照情形5处理

 

 

//可能出现情形5
//当前节点时父节点的左子树，父节点也是左子树
=》针对祖父节点G进行右旋转
=》然后改变下父节点和祖父节点的颜色

 

 

//综合上述，插入情况的1和2都是不要考虑情况的
//问题就变成如下：
               //父节点是在左边还是在右边
                 //叔叔节点时红色，还是其他情况

 

/*
 *参考：http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
 *     http://blog.csdn.net/v_JULY_v/article/details/6114226
 **/
enum Colors {
	RED, BLACK
}

public class RedBlackTree {
	public static void main(String[] args) {
		Node head = null;
		Scanner scanner = new Scanner(System.in);

		while (true) {
			int data = scanner.nextInt();
			if (data == -1)
				break;

			head = insertNode(head, data);
		}

		inorderReserve(head);
	}

	/*
	 * Insert the nodeDefault the color is redReturn the
	 */
	public static Node insertNode(Node head, int num) {

		Node temp = null;
		Node node = searchNode(head, num);

		if (node != null && node.getNum() == num)
			return node; // if exist return this

		temp = new Node(num);// insert node

		if (node != null) {
			temp.setParent(node);// set the insert node parent
			if (node.getNum() > num)
				node.setLeftChild(temp);
			else
				node.setRightChild(temp);
		} else {// head is null
			head = temp;
		}

		return insertReBalance(temp, head);// 传递head的目的是保证root一直可以得到
	}

	/*
	 * Accoding to the current satate of the node to detemine the change;
	 * 1.插入的是根节点
	 * 2.插入的父节点时黑色因为红色不影响路径里的黑色个数，所以不会破坏任何条件
	 * 3.父节点红色和叔父节点都是红色   
	 * 4.父节点红色和叔叔节点不是红色是LR情况
	 * 5.父节点红色和叔叔节点不是红色是LL情况=》对于1，2两种情况不用处理的
	 * =》如果对于父节点时红色肯定有祖父节点
	 */
	public static Node insertReBalance(Node node, Node head) {
		// avaliable variable
		Node parent, uncle, grandParent,temp;

		while ((parent = node.getParent()) != null
				&& (parent.getColor() == Colors.RED)) { // parent is not null
														// and color is red
			grandParent = parent.getParent();
			if (parent == grandParent.getLeftChild()) {
				uncle = grandParent.getRightChild();
				if (uncle != null && uncle.getColor() == Colors.RED) // 情景3
				{
					uncle.setColor(Colors.BLACK); // uncle and parent become black
					parent.setColor(Colors.BLACK);
					grandParent.setColor(Colors.RED); // grandgetParent() become red

					node = grandParent; // grandgetParent() become node to
										// determine the 1
				} else { // 叔父节点不为红色
					if (parent.getRightChild() == node) { // node 在父节点的右边
						head=RR(parent,head); 		      // 因为LR的操作是要先RR=》LL
						temp=parent;
						parent=node;
						node=temp;
					}
					// LL情况
					parent.setColor(Colors.BLACK);
					grandParent.setColor(Colors.RED);
                    head=LL(grandParent,head);
				}
			} else {
				uncle = grandParent.getLeftChild();
				if (uncle != null && uncle.getColor() == Colors.RED) // 情景3
				{
					uncle.setColor(Colors.BLACK); // uncle and parent become black
					parent.setColor(Colors.BLACK);
					grandParent.setColor(Colors.RED); // grandgetParent() become red

					node = grandParent; // grandgetParent() become node to
										// determine the 1
				} else { // 叔父节点不为红色
					if (parent.getLeftChild() == node) {
						head=LL(parent,head);           //RL=>LL=>RR
						temp=parent;
						parent=node;
						node=temp;
					} 
                        parent.setColor(Colors.BLACK);
                        grandParent.setColor(Colors.RED);
                        head=RR(grandParent,head);
    
                       // inorderReserve(head);
				}
			}

		}

		head.setColor(Colors.BLACK); // root is always black;
		return head;
	}
	
	/*
     *       a                  b
     *      /                  / \
     *     b      =>         c    a
     *    /
     *   c
     *   here node=a
     **/
	public static Node LL(Node node, Node head) {
		Node b = node.getLeftChild();

		if(node.getParent()!=null){         //如果node不是根节点
			node.getParent().setLeftChild(b);
		}else{
			head=b;
		}
		
		node.setLeftChild(b.getRightChild());// 子节点转换
		b.setRightChild(node);

		b.setParent(node.getParent()); // 父节点转换
		node.setParent(b);

		return head;
	}

	/*
     *  a                      b
     *   \                    / \
     *     b      =>         a    c
     *      \
     *       c
     *   here node=b
     **/
	public static Node RR(Node node, Node head) {

		Node b = node.getRightChild();

		if(node.getParent()!=null){         //如果node不是根节点
			node.getParent().setRightChild(b);
		}else{
			head=b;
		}
		
		node.setRightChild(b.getLeftChild());
		b.setLeftChild(node);

		b.setParent(node.getParent()); // 父节点转换
		node.setParent(b);

		return head;
	}

	/*
     *       a            a
     *      /            /
     *     b      =>    c   =>LL
     *      \          /
     *       c        b
     *   here node=a
     **/
	public static Node LR(Node node, Node head) {
		node = RR(node.getLeftChild(), head);
		return LL(node, head);
	}

	 /*
     *   a         a
     *    \         \
     *     b    =>    c   =>RR
     *     /           \
     *   c              b
     *   here node=a
     **/

	public static Node RL(Node node, Node head) {
		node = LL(node.getRightChild(), head);
		return RR(node, head);
	}

	/*
	 * Detemine whether there is keyBut didn't change the headIf exist return
	 * the NodeIf not exist return the insert positionSo must detemine it again
	 */
	public static Node searchNode(Node head, int key) {
		Node temp = null;
		int num;

		while (head != null) {
			num = head.getNum();
			temp = head;
			if (num < key)
				head = head.getRightChild();
			else if (num > key)
				head = head.getLeftChild();
			else
				return head;
		}

		return temp;// if not exist return the parent!
	}

	public static void inorderReserve(Node head) {

		if (head != null) {
			inorderReserve(head.getLeftChild());    
			System.out.println(head.getNum()+"  Color:"+head.getColor());
			inorderReserve(head.getRightChild());
		}
	}
}

 

class Node {

	private int num;
	private Colors color;// 0-red 1-black
	private Node leftChild;
	private Node rightChild;
	private Node parent;

	public Node(int num) {
		// init the num
		this.num = num;
		// default the color
		this.color = Colors.RED;
		this.leftChild = this.rightChild = this.parent = null;
	}
}

 

 

       2.删除

  

//X的兄弟是红色的-1
//对X的父节点做一次左旋
//X的父节点和兄弟改变颜色

     

//X的兄弟是黑色的-2
//X的兄弟的孩子都是黑色的
//X的兄弟节点变为红色
//X父节点为新的节点X

 

//X的兄弟是黑色的-3
//X的兄弟左孩子是红色，右孩子是黑色
//交换X兄弟和它左孩子的颜色
//然后对它兄弟进行右转
//变成问题4

 

//X的兄弟是黑色的-4
//X的兄弟的右孩子是红色的
//颜色修改
//X的父节点做旋转