红黑树的Java实现-技术开发专区

红黑树的Java实现

作者：佚名编辑：李宁 2007-12-21 00:00

【IT168 技术文档】

红黑树可能是要考虑情况最多的BST树了，它有自己的规则（见代码的注释），通过这些规则可以保证花费较小的代价来达到相对平衡。
注意，红黑树仍然不是平衡树，但是统计性能要好于AVL树。
要保持红黑树的规则，主要通过两类操作，一类是换色，一类还是旋转。
红黑树插入主要要解决红-红冲突，而删除主要则解决“双黑”

同样，红黑树的删除节点实现是最复杂的，不过，复杂也就在于考虑的情况多，掌握了这几种情况实现还是不困难。
其实，红黑树其实是一颗扩充的二叉树，所以也是满二叉树，其空节点可以看做是扩充的叶节点。但是红黑树的扩充叶节点是有特殊意义的。

下面是代码：

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;
    }

关注我们