红黑树java简单实现

public class RBTree{
    TreeNode root;

    //建立红黑树
    public void create(int[] list){
        for(int i = 0; i < list.length; i++){
            this.insert(list);
        }
    }

    //插入一个元素
    public void insert(int elem){//为新元素开辟一个空间
        TreeNode s = new TreeNode();
        s.data = elem;
        s.color = "red";
        s.lchild = null;
        s.rchild = null;

        //判断根是否为空,如果为空,则将root指向新元素.否则,进入循环
        if(root == null){
            root = s;
            root.color = "black";
            return ;
        }else{
            //定义四个指针,分别指向祖先,祖,父,自身
            TreeNode p = root,q;
            TreeNode parent = root;
            TreeNode grand = root;
            TreeNode ancestor = root;
            while(p != null){
                //如果P的左右孩子均不为空且颜色均为红色,则执行颜色转换并进行调整
                if(p.lchild != null && p.rchild != null){
                    if(p.lchild.color==("red") && p.rchild.color==("red")){
                        convertColor(p);
                        adjust(ancestor,grand,parent,p);
                    }
                }

                if(elem == p.data){
                    return;
                }

                q = p; //指针依次向后移动
                ancestor = grand;
                grand = parent;
                parent = p;

                //如果,元素小于P
                if(elem < q.data){ //P的左孩子为空
                    if(q.lchild == null){
                        //将P的左孩子指向新建元素
                        q.lchild = s;
                        p = s; //调整
                        adjust(ancestor,grand,parent,p);
                        return;
                    }else{//P的左孩子不为空
                        //P向左下移动
                        p = p.lchild;
                    }
                } else{//如果,元素大于P
                    if(elem > q.data){ //P的右孩子为空
                        if(q.rchild == null){
                            //将P的右孩子指向新建元素
                            q.rchild = s;
                            p = s;//调整
                            adjust(ancestor,grand,parent,p);
                            return;
                        }else{//P的右孩子不为空
                            //P向右下移动
                            p = p.rchild;
                        }
                    }
                }
            }
        }
    }

    //调整颜色的方法
    public void convertColor(TreeNode p){
        //将P的左右孩子的颜色均置为黑
        p.lchild.color = "black";
        p.rchild.color = "black";
        //若P为根结点,则颜色仍为黑,否则颜色置为红
        if(!(p.equals(root))){
            p.color = "red";
            return;
        }
        if(p.equals(root)){
            p.color = "black";
        }
    }

    public void adjust(TreeNode ancestor,TreeNode grand,TreeNode parent,TreeNode x){//是否存在红红冲突
        if(!(parent.color == "red" && x.color == "red")){
            return;
        }
        //符合一次调整的,将调用一次调整
        if((grand.lchild == parent && parent.lchild == x) ||(grand.rchild == parent && parent.rchild == x )){
            onceAdjust(ancestor,grand,parent,x);
            return;
        }
        //符合二次调整的,将调用二次调整
        if((grand.lchild == parent && parent.rchild == x ) || (grand.rchild == parent && parent.lchild == x )){
            twiceAdjust(ancestor,grand,parent,x);
            return;
        }
    }

    private void onceAdjust(TreeNode ancestor,TreeNode grand,TreeNode parent,TreeNode x){ //调整父结点和祖结点的颜色
        this.exchangeColor(grand);
        this.exchangeColor(parent);
        //将祖先结点指向父结点
        if(ancestor ==  grand && ancestor == this.root ){
            this.root = parent;
            ancestor = parent;
        }else{
            if(ancestor.lchild == grand){
                ancestor.lchild = parent;
            }else if(ancestor.rchild == grand){
                ancestor.rchild = parent;
            }
        }

        //左左型调整
        if(grand.lchild == parent && parent.lchild == x ){
            grand.lchild = parent.rchild;
            parent.rchild = grand;
            return;
        }

        //右右型调整
        if(grand.rchild == parent && parent.rchild == x ){
            grand.rchild = parent.rchild;
            parent.lchild = grand;
            return;
        }
    }
   
    private void twiceAdjust(TreeNode ancestor,TreeNode grand,TreeNode parent,TreeNode x){ //调整自身结点和祖结点的颜色
        this.exchangeColor(grand);
        this.exchangeColor(x);
        //将祖先结点指向自身结点
        if(ancestor == grand && ancestor == root){
            root = x;
            ancestor = x;
        }else{
            if(ancestor.lchild == grand){
                ancestor.lchild = x;
            }else if(ancestor.rchild == grand){
                ancestor.rchild = x;
            }else if(ancestor == root){
                ancestor = x;
                root = x;
            }
        }

        //左右型调整
        if(grand.lchild == parent && parent.rchild == x ){
            grand.lchild = x.rchild;
            parent.rchild = x.lchild;
            x.lchild = parent;
            x.rchild = grand;
            return;
        }

        //右左型调整
        if(grand.rchild == parent && parent.lchild == x){
            grand.rchild = x.lchild;
            parent.lchild = x.rchild;
            x.lchild = grand;
            x.rchild = parent;
            return;
        }
    }

    //变换颜色的方法
    private void exchangeColor(TreeNode p){
        if(p.color.equals("red")){
            p.color = "black";
        }else{
            p.color = "red";
        }
    }

    public void inorder(){
        inorder(root);
    }
   
    //中序遍历
    private void inorder(TreeNode root){
        if(root != null){
            inorder(root.lchild);
            System.out.println(root.data+"  "+root.color);
            inorder(root.rchild);
        }
    }
}

class TreeNode{
    public int data;
    public String color;
    public TreeNode lchild;
    public TreeNode rchild;
}