（转帖）红黑树算法

package algorithms.tree;

/**
 * R-B Tree has following four rules:
 * 1)every node is either red or black
 * 2)root and empty node (external leaf node) are always black.
 * 3)the red node's parent node must be black
 * 4)every simple path start from node X to its descendant contains same number of black node
 * 
 * 
 * @author yovn
 *
 */
public class RBTree<E extends Comparable<E>> extends DefaultBSTree<E> implements BSTree<E> {

    
    
    public static class RBPrinter<E extends Comparable<E>> implements DefaultBSTree.NodeVisitor<E>
    {

        @Override
        public void visit(E ele) {
            
            
        }

        @Override
        public void visitNode(algorithms.tree.DefaultBSTree.BSTNode<E> node) {
            RBNode<E> n=(RBNode<E>)node;
            if(!n.isNull())
            System.out.print(n.key+"("+(n.color==RBNode.RED?"RED":"BLACK")+"),");
            
        }
        
    }
    static class RBNode<E extends Comparable<E>> extends BSTNode<E>
    {



        static final boolean RED=false;
        static final boolean BLACK=true;
        
        
        
        RBNode<E> parent;
        boolean color;//red or black
        
        
        RBNode(RBNode<E> p,E key,boolean color) {
            super(key);
            this.color=color;
            this.parent=p;
            
        }
        
        
        
        final boolean isNull(){return key==null;}
        
    }
    
    
        
    @Override
    public final boolean delete(E ele) {
        RBNode<E> cur;
        
        int cmp;
        if(root==null)return false;
        cur=(RBNode<E>)root;
        while(!cur.isNull()&&(cmp=ele.compareTo(cur.key))!=0)
        {
            if(cmp<0)cur=(RBNode<E>)cur.left;
            else cur=(RBNode<E>)cur.right;
                
        }
        if(cur.isNull())
        {
            //can't find specified key
            return false;
        }
        if(!((RBNode<E>)cur.left).isNull()&&!((RBNode<E>)cur.right).isNull())
        {
            RBNode<E> prev=(RBNode<E>)cur.left;
        
            while(!((RBNode<E>)prev.right).isNull())
            {
                
                prev=(RBNode<E>)prev.right;
            }
            cur.key=prev.key;
            cur=prev;
        
        }
        if(!((RBNode<E>)cur.left).isNull())
        {
            if (cur == root) {
                root = cur.left;
                ((RBNode<E>)root).color=RBNode.BLACK;
                return true;
            }
            
            if(cur.parent.left==cur)
            {
                cur.parent.left=cur.left;
                ((RBNode<E>)cur.left).parent=cur.parent;
            }
            else
            {
                cur.parent.right=cur.left;
                ((RBNode<E>)cur.left).parent=cur.parent;
            }
            if(cur.color==RBNode.BLACK)
            {
                ((RBNode<E>)cur.left).color=RBNode.BLACK;
            }
        }
        else if(!((RBNode<E>)cur.right).isNull())
        {
            if (cur == root) {
                root = cur.right;
                ((RBNode<E>)root).color=RBNode.BLACK;
                return true;
            }
            
            if(cur.parent.left==cur)
            {
                cur.parent.left=cur.right;
                ((RBNode<E>)cur.right).parent=cur.parent;
            }
            else
            {
                cur.parent.right=cur.right;
                ((RBNode<E>)cur.right).parent=cur.parent;
            }
            if(cur.color==RBNode.BLACK)
            {
                ((RBNode<E>)cur.right).color=RBNode.BLACK;
            }
        }
        else
        {
            if(cur==root)
            {
                root=null;
                return true;
            }
            RBNode<E> todo;
            if(cur.parent.left==cur)
            {
                todo=newNullNode(cur.parent);
                cur.parent.left=todo;
            }
            
            else
            {
                todo=newNullNode(cur.parent);
                cur.parent.right=todo;
            }
            if(cur.color==RBNode.BLACK)
            {
                //now todo is a double black node, we will eliminate the double black
                fixup_double_black(todo);
            }
            
        }
        
        return true;
    }

    @Override
    public E findMax() {
        if(isEmpty())return null;
        BSTNode<E> node=root;
        while(!((RBNode<E>)node.right).isNull())
        {
            node=node.right;
        }
        return node.key;
    }


    @Override
    public E findMin() {
        if(isEmpty())return null;
        BSTNode<E> node=root;
        while(!((RBNode<E>)node.left).isNull())
        {
            node=node.left;
        }
        return node.key;
    }

    private final RBNode<E> newNullNode(RBNode<E> p)
    {
        return new RBNode<E>(p,null,RBNode.BLACK);
    }
    
    private final RBNode<E> newNormalNode(RBNode<E> p,E key, boolean color)
    {
        RBNode<E> node= new RBNode<E>(p,key,color);
        node.left=newNullNode(node);
        node.right=newNullNode(node);
        return node;
    }

    private final void fixup_double_black(RBNode<E> cur) {
        
        RBNode<E> sibling;
        RBNode<E> p;
    
        while(cur!=root)//until its parent,parent maybe double black 
        {
            p=cur.parent;
            if(p.left==cur)
            {
                sibling=(RBNode<E>)p.right;
                if(sibling.color==RBNode.RED)
                {
                    rotate_from_right(p);
                    p.color=RBNode.RED;
                    sibling.color=RBNode.BLACK;//actually, p.parent==sibling, remember we have done one rotation
                    //this case  transformed to another case handled in other place
                }
                else 
                {
                    if(((RBNode<E>)sibling.right).color==RBNode.RED)
                    {
                        rotate_from_right(p);
                        sibling.color=p.color;//also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
                        p.color=RBNode.BLACK;
                        ((RBNode<E>)sibling.right).color=RBNode.BLACK;
                        //ok done!
                        return;
                        
                    }
                    else if(((RBNode<E>)sibling.left).color==RBNode.RED)
                    {
                        rotate_from_left(sibling);
                        sibling.color=RBNode.RED;
                        sibling.parent.color=RBNode.BLACK;//its parent was previously be its left child, remember we have done a left rotation from sibling
                        
                        // now transformed to previous case, double black 's sibling(black) have right child colored red
                        
                    }
                    else //  sibling's two children are both black
                    {
                        //re-coloring the sibling and parent
                        sibling.color=RBNode.RED;
                        if(p.color==RBNode.BLACK)
                        {
                            cur=p;
                            //now the cur node was not double black node ,but p was a double black
                        }
                        else
                        {
                            p.color=RBNode.BLACK;//eliminated the double black node 
                            return;
                        }
                    }
                }
            }
            else
            {
                sibling=(RBNode<E>)p.left;
                if(sibling.color==RBNode.RED)
                {
                    rotate_from_left(p);
                    p.color=RBNode.RED;
                    sibling.color=RBNode.BLACK;//actually, p.parent==sibling, remember we have done one rotation
                    //this case  transformed to another case handled in other place
                }
                else 
                {
                    if(((RBNode<E>)sibling.left).color==RBNode.RED)
                    {
                        rotate_from_left(p);
                        sibling.color=p.color;//also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
                        p.color=RBNode.BLACK;
                        ((RBNode<E>)sibling.left).color=RBNode.BLACK;
                        //ok done!
                        return;
                        
                    }
                    else if(((RBNode<E>)sibling.right).color==RBNode.RED)
                    {
                        rotate_from_right(sibling);
                        sibling.color=RBNode.RED;
                        sibling.parent.color=RBNode.BLACK;//its parent was previously be its right child, remember we have done a left rotation from sibling
                    
                        // now transformed to previous case, double black 's sibling(black) have right child colored red
                        
                    }
                    else //  sibling's two children are both black
                    {
                        //re-coloring the sibling and parent
                        sibling.color=RBNode.RED;
                        if(p.color==RBNode.BLACK)
                        {
                            cur=p;
                            //now the cur node was not double black node ,but p was a double black
                        }
                        else
                        {
                            p.color=RBNode.BLACK;//eliminated the double black node 
                            return;
                        }
                    }
                }
            }
        }
        
    }

    



    @Override
    public final void insert(E ele) {
        if(root==null)
        {
            root=newNormalNode(null,ele,RBNode.BLACK);//now root's black-height(bh) is 1
            return;
        }
        RBNode<E> ret=_insert((RBNode<E>)root,ele);//first insert it
        _insert_fixup(ret);//fix-up the R-B tree from node cur;
    }
    
    
    private final void _insert_fixup(RBNode<E> cur) {
        
        RBNode<E> p,g;
    
        //we should fix until it is black colored
        while(cur!=root&&cur.color==RBNode.RED)
        {
            p=cur.parent;
            if(p.color==RBNode.BLACK)
            {
                //that's fine, the insertion will not change any black height, and will not violate any rule.
                return;
            }
            g=p.parent;//we can assume the p is not null now.
            
            if(p==g.left)
            {
                RBNode<E> uncle=(RBNode<E> )g.right;
                if(uncle.color==RBNode.RED)
                {
                    //re-coloring
                    g.color=RBNode.RED;
                    uncle.color=p.color=RBNode.BLACK;
                    
                    //now the g maybe conflict with its parent;
                    cur=g;
                }
                else
                {
                    if(cur==p.right)
                    {
                        //this case we should do left rotation, and then it will transform to next case
                        cur=rotate_from_right(p);
                        cur=(RBNode<E>)cur.left;
                        //transformed to next case    
                    }
                    
                    cur=rotate_from_left(g);
                    cur.color=RBNode.BLACK;
                    ((RBNode<E>)cur.left).color=((RBNode<E>)cur.right).color=RBNode.RED;
                                    
                
                }
                
            }
            else
            {
                RBNode<E> uncle=(RBNode<E> )g.left;
                if(uncle.color==RBNode.RED)
                {
                    //re-coloring
                    g.color=RBNode.RED;
                    uncle.color=p.color=RBNode.BLACK;
                    
                    //now the g maybe conflict with its parent;
                    cur=g;
                }
                else
                {
                    if(cur==p.left)
                    {
                        //this case we should do right rotation, and then it will transform to next case
                        cur=rotate_from_left(p);
                        cur=(RBNode<E>)cur.right;
                        //transformed to next case    
                    }
                    
                    cur=rotate_from_right(g);
                    cur.color=RBNode.BLACK;
                    ((RBNode<E>)cur.left).color=((RBNode<E>)cur.right).color=RBNode.RED;
                                    
                
                }
            }
                
        }
        ((RBNode<E>)root).color=RBNode.BLACK;
        
        
    }




    private final RBNode<E> rotate_from_right(RBNode<E> p) {
        
        RBNode<E> g=p.parent;
        RBNode<E> cur=(RBNode<E>)p.right;
        
        p.right=cur.left;
        if(cur.left!=null)((RBNode<E>)cur.left).parent=p;
        
        cur.left=p;
        p.parent=cur;
        
        
        if(g!=null)
        {
            if(g.left==p)g.left=cur;
            else g.right=cur;
        }
        else root=cur;
        
        cur.parent=g;
        return cur;
        
    
    }




    private final RBNode<E> rotate_from_left(RBNode<E> p) {
        RBNode<E> g=p.parent;
        RBNode<E> cur=(RBNode<E>)p.left;
        
        p.left=cur.right;
        if(cur.right!=null)((RBNode<E>)cur.right).parent=p;
        
        cur.right=p;
        p.parent=cur;
        
        
        if(g!=null)
        {
            if(g.left==p)g.left=cur;
            else g.right=cur;
        }
        else root=cur;
        
        cur.parent=g;
        return cur;
    }




    private final RBNode<E> _insert(RBNode<E> cur,E ele)
    {
        
        RBNode<E> parent=null;
        int cmp;
        boolean left=false;
        while(!cur.isNull()&&(cmp=ele.compareTo(cur.key))!=0)
        {
            parent=cur;
            if(cmp<0)
            {
                cur=(RBNode<E>)cur.left;
                left=true;
                
            }
            else {cur=(RBNode<E>)cur.right;left=false;}
            
        }
        if(!cur.isNull())throw new IllegalArgumentException("can't insert duplicate key!");
        cur=newNormalNode(parent,ele,RBNode.RED);
        if(left)parent.left=cur;
        else parent.right=cur;
        return cur;
    }




    /**
     * 
     */
    public RBTree() {
            root=null;
    }

}

 

 

链接地址：http://www.blogjava.net/javacap/archive/2010/07/25/169120.html#327076