算法导论学习笔记——红黑树

/**
 * 红黑树的5个性质：
 * 1）每个结点要么是红的，要么是黑的。
 * 2）根结点是黑的。
 * 3）每个叶结点，即空结点（NIL）是黑的。
 * 4）如果一个结点是红的，那么它的俩个儿子都是黑的。
 * 5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
 */
public class RBTree {

	/**
	 * 当在某个结点nodeX上，做左旋操作时，我们假设它的右孩子nodeY不是NIL[T]，nodeX可以为树内任意右孩子不是NIL[T]的结点。
	 * 左旋以nodeX到nodeY之间的链为“支轴”进行，它使nodeY成为该孩子树新的根，而nodeY的左孩子b则成为nodeX的右孩子。
	 * 对nodeX做左旋也就是使nodeX成为其右孩子nodeY的左孩子，而nodeY原来的左孩子调整为nodeX的右孩子，这样才能保证左旋后的树仍然是一棵查找树
	 * @param tree
	 * @param nodeX
	 */
	public void leftRoate(Node tree,Node nodeX){
		Node nodeY = nodeX.getRight();
		//调整nodeY的左孩子为nodeX的右孩子。调整nodeX的right指向nodeY的左孩子；调整nodeY的左孩子的parent指向nodeX；
		nodeX.setRight(nodeY.getLeft());
		if(null!=nodeY.getLeft())
			nodeY.getLeft().setParent(nodeX);
		//使nodeY成为该孩子树的新根。调整nodeY的parent指向nodeX的parent；
		//根据nodeX是其parent的右孩子还是右孩子设置相应的left或right指向nodeY
		nodeY.setParent(nodeX.getParent());
		if(null==nodeX.getParent())
			tree = nodeY;
		else{
			if(nodeX.equals(nodeX.getParent().getLeft()))
				nodeX.getParent().setLeft(nodeY);
			else
				nodeX.getParent().setRight(nodeY);
		//建立nodeX与nodeY之间的新关系。调整nodeY的left指向nodeX；调整nodeX的parent指向nodeY
		nodeY.setLeft(nodeX);
		nodeX.setParent(nodeY);
		}	
	}
	/**
	 * 当在某个结点nodeX上，做右旋操作时，我们假设它的左孩子nodeY不是NIL[T]，nodeX可以为树内任意左孩子不是NIL[T]的结点。
	 * 右旋以nodeX到nodeY之间的链为“支轴”进行，它使nodeY成为该孩子树新的根，而nodeY的右孩子b则成为nodeX的左孩子。
	 * @param tree
	 * @param nodeX
	 */
	public void rightRoate(Node tree,Node nodeX){
		Node nodeY = nodeX.getLeft();
		//调整nodeY的右孩子为nodeX的左孩子。调整nodeX的left指向nodeY的右孩子；调整nodeY的右孩子的parent指向nodeX；
		nodeX.setLeft(nodeY.getRight());
		if(null!=nodeY.getRight())
			nodeY.getRight().setParent(nodeX);
		//使nodeY成为该孩子树的新根。调整nodeY的parent指向nodeX的parent；
		//根据nodeX是其parent的右孩子还是右孩子设置相应的left或right指向nodeY
		nodeY.setParent(nodeX.getParent());
		if(null==nodeX.getParent())
			tree = nodeY;
		else{
			if(nodeX.equals(nodeX.getParent().getLeft()))
				nodeX.getParent().setLeft(nodeY);
			else
				nodeX.getParent().setRight(nodeY);
		//建立nodeX与nodeY之间的新关系。调整nodeY的right指向nodeX；调整nodeX的parent指向nodeY
		nodeY.setRight(nodeX);
		nodeX.setParent(nodeY);
		}	
	}
	/**
	 * 这里的插入操作类似二叉查找树中的过程，只是在最后把新插入结点的color置为red，
	 * 然后调用insertFixup方法来对结点重新着色并旋转
	 * @param tree
	 * @param node
	 */
	public void insertRB(Node tree,Node node){
		Node tempNode = tree;
		Node parentNode = null;
		while(null!=tempNode){
			parentNode = tempNode;
			if(node.getKey()<tempNode.getKey())
				tempNode = tempNode.getLeft();
			else
				tempNode = tempNode.getRight();
		}
		if(parentNode!=null)
			node.setParent(parentNode);
		if(parentNode==null)
			tree = node;
		else
			if(node.getKey()<parentNode.getKey())
				parentNode.setLeft(node);
			else
				parentNode.setRight(node);
		node.setLeft(null);
		node.setRight(null);
		//置为红色，调用insertFixup重新调整为一棵红黑树
		node.setColor("red");
		insertFixup(tree,node);		
	}
	/**
	 * 插入一个红色结点只会破坏性质2或性质4。策略：把出现违背红黑树性质的结点向上移，如果能移到根结点，
	 * 那么很容易就能通过直接修改根结点来恢复红黑树的性质,直接通过修改根结点来恢复红黑树应满足的性质。
	 * nodeX为当前要调整的结点(最开始为刚插入的结点)，它总是为红色，当他的父结点为红色时就需要进行调整，如果为黑色则调整结束。
	 * 调整算法会涉及三代，即当前节点，父节点和祖父结点，由于当前结点和父结点都是红色而祖父结点为黑色(如果祖父结点为红色，那么父结点必须为黑色，否则违背性质4)，
	 * 只有叔叔结点的颜色是未知的，所以根据叔叔结点的颜色不同可以分为两种情况(以父结点是祖父结点的左孩子为例)：
	 * 1、当叔叔结点是红色时，策略：将当前节点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，重新开始算法。
	 * 2、当叔叔结点为黑色时，策略为旋转，根据当前结点是左孩子还是右孩子又可分为两种情况：
	 *    (1)、当前结点是父结点的右孩子时，策略为：当前结点的父结点为新的当前结点，以当前结点为支点左旋。
	 *    (2)、当前结点是父结点的左孩子时，策略为：父结点变为黑色，祖父结点变为红色，以祖父结点为支点右旋（由于旋转后父结点成了原祖父结点的父结点且为黑色，所以调整结束）。
	 * @param tree
	 * @param nodeX
	 */
	public void insertFixup(Node tree,Node nodeX){
		Node nodeY = null;
		//当父结点为red时才进行调整
		while(nodeX.getParent().getColor().equals("red")){
			//以父结点是祖父结点的左孩子，父结点是祖父结点的左孩子还是右孩子关系到叔叔结点怎么获取以及不同情况下是左旋还是右旋的问题
			if(nodeX.getParent().equals(nodeX.getParent().getParent().getLeft())){
				nodeY = nodeX.getParent().getParent().getRight();
				//第1种情况，当叔叔结点为红色时
				if(nodeY.getColor().equals("red")){
					nodeX.getParent().setColor("black");
					nodeY.setColor("black");
					nodeX = nodeX.getParent().getParent();
				//第2种情况中的(1)，叔叔结点为黑色且当前结点为父结点的右孩子
				}else if(nodeX.equals(nodeX.getParent().getRight())){
					nodeX = nodeX.getParent();
					leftRoate(tree,nodeX);
				//第2种情况中的(2)，叔叔结点为黑色且当前结点为父结点的左孩子
				}else{
					nodeX.getParent().setColor("black");
					nodeX.getParent().getParent().setColor("red");
					rightRoate(tree,nodeX.getParent().getParent());
				}
			//以父结点是祖父结点的右孩子
			}else{
				nodeY = nodeX.getParent().getParent().getLeft();
				//
				if(nodeY.getColor().equals("red")){
					nodeX.getParent().setColor("black");
					nodeY.setColor("black");
					nodeX = nodeX.getParent().getParent();
				//
				}else if(nodeX.equals(nodeX.getParent().getLeft())){
					nodeX = nodeX.getParent();
					rightRoate(tree,nodeX);
				//
				}else{
					nodeX.getParent().setColor("black");
					nodeX.getParent().getParent().setColor("red");
					leftRoate(tree,nodeX.getParent().getParent());
				}
			}
			//最后把要结点置为黑色
			tree.setColor("black");
		}
	}
	/**
	 * 后继结点：与前趋结点相反，它是在中序遍历顺序下的后一个结点。
	 * 如果给定查询结点的右子树不为空，则它的后继结点是右子树中的最小关键字结点；
	 * 如果右子树为空，需要向上判断每一个父结点，直到父结点为空或者遍历结点是父结点的左子结点时，则该父结点即为查询结点的后继。
	 * @param node
	 * @return
	 */
	public static Node treeSuccessor(Node node){
		Node preNode = null;
		Node tempNode = null;
		if(node.getRight()!=null){
			Node temp = node.getRight();
			while(null!=temp.getLeft()){
				temp = temp.getLeft();
			}
			return temp;
		}
		preNode = node.getParent();
		tempNode = node;
		while(preNode!=null&&preNode.getLeft()!=tempNode){
			tempNode = preNode;
			preNode = preNode.getParent();
		}
		return preNode;
	}
	/**
	 * 这里的删除操作类似二叉查找树中的过程，只是如果删除的结点color为balck要重新调整为红黑树，
	 * 然后调用insertFixup方法来对结点重新着色并旋转
	 * @param tree
	 * @param node
	 */
	public void deleteRB(Node tree,Node node){
		Node tempNode = null;
		Node childNode = null;
		//
		if(null==node.getLeft()||null==node.getRight())
			tempNode = node;
		else
			tempNode = treeSuccessor(node);
		//
		if(null!=tempNode.getLeft())
			childNode = tempNode.getLeft();
		else
			childNode = tempNode.getRight();
		//
		if(null!=childNode)
			childNode.setParent(tempNode.getParent());
		if(null==tempNode.getParent())
			tree = childNode;
		else
			if(tempNode.equals(tempNode.getLeft()))
				tempNode.getParent().setLeft(childNode);
			else
				tempNode.getParent().setRight(childNode);
		//
		if(tempNode!=node)
			node.setKey(tempNode.getKey());
		//如果tempNode是红色，红黑性质仍然保持，因为：1）树中各结点的黑高度没有变化2）不存在两个相邻的红结点（即父结点与子结点不可能同时为红）3）tempNode不可能为根
		if(tempNode.getColor().equals("black"))
			deleteFixup(tree,childNode);			
	}
    /**
     * 删除算法的思想是：将被删除结点的孩子记为nodeX(只有一个孩子或者为nil[T])。
     * 需要调整nodeX的父结点为根的树，使得其左右子树的黑高度相同，但是这样父结点这棵树的黑高度可能会降低，所以要继续向上调整。
     * 直到nodeX为红色时，直接将其变黑，结束。
     * 算法导论中的思想：由于被删除的结点(记为nodeY)是黑色的，会产生三个问题：（1）如果nodeY原来是根结点，而nodeX是红色时，nodeX成为新根，违反性质2
     * （2）如果nodeX和其父结点都是红色，违反性质4（3）由于nodeY是黑色，因此会导致包含该删除结点的任何路径上黑结点的个数少1，性质5被破坏，
     * 这时把nodeX视为还有一重颜色，即nodeX为双重黑色或红黑，那么性质5将会被保持。但是现在nodeX由于不再是黑色或红色，所以违反了性质1。
     * 下面的函数就是来恢复性质1、2、4，首先如果nodeX结点为红色，直接将其置黑就可以结束调整，否则就要进入while循环，其的目的是将额外的黑色沿树上移，直到：
     * 1）nodeX指向一个红黑结点，此时在最后一行中，将nodeX着为黑色
     * 2）nodeX指向根，这时可以简单的消除那个额外的黑色
     * 3）非上面两种情况则需要分别按下列四种情况做相应的旋转和颜色修改
     * @param tree
     * @param node
     */
    public void deleteFixup(Node tree,Node nodeX){
        Node nodeW = null;
        while(nodeX!=tree&&nodeX.getColor().equals("black")){
            if(nodeX.equals(nodeX.getParent().getLeft())){
                nodeW = nodeX.getParent().getRight();
                //情况1：x的兄弟w是红色的。
                //对策：改变nodeW、nodeX的父结点的颜色，再对nodeX的父结点做一次左旋，红黑性质得以继续保持。
                //nodeX的新兄弟是旋转之前nodeW的某个孩子，为黑色。所以，情况1转化成情况2或3、4。
                if(nodeW.getColor().equals("red")){
                    nodeW.setColor("black");
                    nodeX.getParent().setColor("red");
                    leftRoate(tree,nodeX.getParent());
                    nodeW = nodeX.getParent().getRight();
                }else {
                    //情况2：nodeX的兄弟nodeW是黑色的，且nodeW的两个孩子都是黑色的。
                    //对策：把nodeX和nodeW中得去掉一黑色，最后，nodeW变为红。
                    //nodeX的父结点为新的nodeX，继续while循环
                    if(nodeW.getLeft().getColor().equals("balck")
                       &&nodeW.getRight().getColor().equals("black")){
                        nodeW.setColor("red");
                        nodeX = nodeX.getParent();
                    //情况3：nodeX的兄弟nodeW是黑色的，nodeW的左孩子是红色，nodeW的右孩子是黑色。
                    //对策：交换nodeW和其左孩子的颜色。并对nodeW进行右旋，而红黑性质仍然得以保持。
                    //现在nodeX的新兄弟nodeW是一个有红色右孩子的黑结点，于是将情况3转化为情况4
                    }else if(nodeW.getRight().getColor().equals("black")){
                        nodeW.getLeft().setColor("black");
                        nodeW.setColor("red");
                        rightRoate(tree,nodeW);
                        nodeW = nodeX.getParent().getRight();
                    //情况4：nodeX的兄弟nodeW是黑色的，且nodeW的右孩子时红色的。
                    //对策：做颜色修改，并对nodeX的父结点做一次旋转，可以去掉nodeX的额外黑色，来把nodeX变成单独的黑色，此举不破坏红黑性质。
                    //将nodeX置为根后，循环结束。
                    }else{
                        nodeW.setColor(nodeX.getParent().getColor());
                        nodeX.getParent().setColor("black");
                        nodeW.getRight().setColor("black");
                        leftRoate(tree,nodeX.getParent());
                        nodeX = tree;
                    }
                }
            }else{
                //与nodeX是父结点左孩子的情况对称
            }
        }
        //nodeX为红黑时，直接置为黑色
        nodeX.setColor("black");
    }
}

//Node类

public class Node {

	private int key;
	private String color;
	private Node left;
	private Node right;
	private Node parent;
	
	public Node(int key,String color){
		this(key, color, null, null, null);
	}
	public Node(int key,String color,Node left,Node right,Node parent){
		this.key = key;
		this.color = color;
		this.left = left;
		this.right = right;
		this.parent = parent;
	}
	public int getKey() {
		return key;
	}
	public void setKey(int key) {
		this.key = key;
	}
	public String getColor() {
		return color;
	}
	public void setColor(String color) {
		this.color = color;
	}
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left = left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right = right;
	}
	public Node getParent() {
		return parent;
	}
	public void setParent(Node parent) {
		this.parent = parent;
	}
	
}