红黑树（一）

水深无声 2022-07-12 05:46 174阅读 0赞

昨天已经写了一个二叉树，不过那个是一个非平衡二叉树，对于插入乱序的数据那是有一定的优势的，不过当插入的数据都是有序的（顺序或者是逆序）那执行的效果就不怎么好了。那有没有办法去解决这个问题，有，那就是今天要讲得红黑树，也就是平衡二叉树。

#### 红黑树的特征： ####

1.  节点都有颜色
2.  在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则

#### 红黑规则 ####

当插入（或者删除）一个新节点时，必须要遵循的一定规则，下面介绍一下这些规则：

*  每个节点不是红色的就是黑色的。
 *  根节点总是黑色的。
 *  如果节点时红色的，则它的子节点必须是黑色的（反之倒不一定必须为真）
 *  从根倒叶节点或空节点的每条路径，必须包含相同数量的黑色节点。

了解了上面的规则，现在我们就开始去写代码吧。(由于之前没有学好红黑树哪些规则，所以后面的删除我就省略了，下一次博客在写红黑树的删除，今天就写红黑树的添加元素)

/** * 节点树的接口 * @author chenjingbin * * @param <E> 可以比较的类 */
    public interface Tree<E extends Comparable<E>> {
        /** * 查找是否有这个元素 * @param e * @return */
        boolean search(E e);
        /** * 插入一个元素 * @param e * @return */
        boolean insert(E e);
        /** * 删除一个元素 * @param e * @return */
        boolean delete(E e);
        /** *中序遍历 */
        void inorder();
        /** * 前序遍历 */
        void preorder();
        /** * 后序遍历 */
        void postorder();
        /** * 有多少个节点 * @return */
        int getSize();
        /** * 判断是否为空 * @return */
        boolean isEmpty();
        /** * 清空树 * @return */
        boolean clear();
    }
    //拿上一次定义好的接口去使用那就可以了
    
    
    /** * 红黑树RABTree * @author chenjingbin *红黑树是平衡二叉树，比较复杂的操作那就是在插入和删除，会使用到左旋转和右旋转 * @param <E> */
    public class RABTree<E extends Comparable<E>> implements Tree<E> { 
        public static final boolean RED = false;
        public static final boolean BLACK = true;
        public RABNode<E> root;
        public int size ;
        @Override
        public boolean search(E e) {
            // TODO Auto-generated method stub
            RABNode<E> current = root;
            while (current != null) {
                if(e.compareTo(current.element)<0)
                    current = current.left;
                else if(e.compareTo(current.element)>0){
                    current = current.right;
                }else {
                    return true;
                }
            }
            return false;
        }
    
        @Override
        public boolean insert(E e) {
            // TODO Auto-generated method stu
            RABNode<E> t=root;
            if(t==null){
                root = new RABNode<E>(e, null);
                size++;
                return true;
            }else {
                RABNode<E> parent = null;
                RABNode<E> current = root;
                while(current !=null){
                    if(e.compareTo(current.element)<0){
                        parent = current;
                        current = current.left;
                    }else if(e.compareTo(current.element)>0){
                        parent = current;
                        current = current.right;
                    }else 
                        //这里面相同的元素那就不用插入，直接返回false
                        return false;
                }
                RABNode<E> node = new RABNode<E>(e, parent);
                if(e.compareTo(parent.element)<0)
                    parent.left = node;
                else 
                    parent.right =node;
                //上面的代码和昨天的一样，不一样的地方是后面这个函数，因为插入一个节点那就需要去修改使得这棵树平衡
                fixAfterInsertion(node);
                size++;
                return true;
            }
        }
            /** * case1:当前节点的父结点是红色，且当前 节点的祖父节点的另一个子节点（叔叔节点）也是红色 * 处理策略：（1）将父结点设为黑色（2）将叔叔节点设置为黑色（3）将祖父节点设置为红色（4）将祖父节点设置为“当前节点”（红色节点）：即，之后继续对当前节点进行操作。 * case2：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子 * 处理策略：（1）将父结点作为新的当前节点（2）以新的当前节点为支点进行左旋转 * case3：当前节点的父结点是红色，叔叔节点是黑色，且当前节点是其父结点的左孩子 * 处理策略：（1）将父结点设置为黑色（2）将祖父节点设置为红色（3）以祖父节点为支点进行右旋转 */
        private void fixAfterInsertion(RABNode<E> x){
            x.color = RED ;
            while(x!= null && x!=root &&x.parent.color ==RED){
                if(parentOf(x) == leftOf(parentOf(parentOf(x)))){
                    RABNode<E> y = rightOf(parentOf(parentOf(x)));
                    if(colorOf(y)==RED){
                        setColor(parentOf(x), BLACK);
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    }else{
                        if(x==rightOf(parentOf(x))){
                            x = parentOf(x);
                            rotateLeft(x);
                        }
                            setColor(parentOf(x), BLACK);
                            setColor(parentOf(parentOf(x)), RED);
                            rotateRight(parentOf(parentOf(x)));
                    }
                }else{
                    RABNode<E> y = leftOf(parentOf(parentOf(x)));
                    if(colorOf(y) == RED){
                        setColor(parentOf(x), BLACK);
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    }else{
                        if(x == leftOf(parentOf(x))){
                            x= parentOf(x);
                            rotateRight(x);
                        }setColor(parentOf(x), BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        rotateLeft(parentOf(parentOf(x)));
                    }
                }
            }
            root.color = BLACK ;
        }
        @Override
        public boolean delete(E e) {
            // TODO Auto-generated method stub
            /** * 第一步：将红黑树当做一颗二叉查找树，将节点删除 * 这里面有三种情况：1被删除节点没有孩子，即为叶子节点，那么直接删除 * 2被删除节点只有一个儿子，那么，直接删除该节点，并用该节点的唯一子节点去替换他的位置 * 3被删除节点有两个孩子，那么先找出他的后继节点，然后把后继节点的内容复制给该节点的内容 * 第二步：通过旋转和重新着色等一系列来修正该树，使之重新成为一颗红黑树 */
            //没有写完，后面再写
            return false;
        }
        //这个方法是拿到比t大一点的节点方法
        private  RABNode<E> successor(RABNode<E> t){
            if(t== null){
                return null;
            }else if(t.right!=null){
                //说明t的右边有节点
                RABNode<E> p = t.right;
                while(p.left!=null){
                    p= p.left;  
                }
                return p;
            }else{
                RABNode<E> p = t.parent;
                RABNode<E> ch=t;
                while(p!=null&&p.left==ch){
                    ch = p;
                    p=p.parent;
                }
                return p;
            }
        }
            /** * case1:x是黑+黑节点，x 的兄弟节点是红色（此时x的父结点和x的兄弟节点的子节点都是黑色） * 处理策略： *1将x的兄弟节点设置为黑色2将x的父结点设置为红色3对x的父结点进行左旋转4左旋转后，重新设置x的兄弟节点 *case2：x是黑+黑节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。 *处理策略：1将x的兄弟节点设置为红色2设置x的父结点为新的x节点 *case3:x是黑+黑节点，x的兄弟节点是黑色，x的兄弟节点的左孩子是红色，右孩子是黑色 *处理策略：1将x兄弟节点的左孩子设置为黑色，2将x的兄弟节点设置为红色3对x的兄弟节点进行右旋转4右旋后重新设置x的兄弟节点 *case4：x是黑+黑节点，x的兄弟节点是黑色，x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色 *处理策略：1将x的父结点颜色赋值给x的兄弟节点2将x父结点设置为黑色3将x兄弟节点的右子节点设置为黑色4对x的父结点进行左旋转5设置x为根节点 */
        private void fixAfterDeletion(RABNode<E> p){
            //没有写完，后面再写
        }
        @Override
        public void inorder() {
            // TODO Auto-generated method stub
            inorder(root);
        }
        private void inorder(RABNode<E> root) {
            // TODO Auto-generated method stub
            if(root== null)return;
            else{
                inorder(root.left);
                System.out.println(root.element+"");
                inorder(root.right);
            }
        }
        @Override
        public void preorder() {
            // TODO Auto-generated method stub
            preorder(root);
        }
    
        private void preorder(RABNode<E> root) {
            // TODO Auto-generated method stub
            if(root== null)return;
            else{
                System.out.println(root.element+"");
                inorder(root.left);
                inorder(root.right);
            }
        }
    
        @Override
        public void postorder() {
            // TODO Auto-generated method stub
            postorder(root);
        }
    
        private void postorder(RABNode<E> root2) {
            // TODO Auto-generated method stub
            if(root== null)return;
            else{
                inorder(root.left);
                inorder(root.right);
                System.out.println(root.element+"");
            }
        }
    
        @Override
        public int getSize() {
            // TODO Auto-generated method stub
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            // TODO Auto-generated method stub
            return size == 0;
        }
    
        @Override
        public boolean clear() {
            // TODO Auto-generated method stub
            size = 0;
            root = null;
            return true;
        }
        /** * 根据e去得到节点 * @param e * @return */
        public RABNode<E> getNode(E e){
            RABNode<E> current = root;
            while (current != null) {
                if(e.compareTo(current.element)<0)
                    current = current.left;
                else if(e.compareTo(current.element)>0){
                    current = current.right;
                }else {
                    return current;
                }
            }
            return null;
        }
        //向下执行的时候会执行颜色变换，也就是黑色节点有两个红色节点时需要执行颜色变换。
        /** * 得到颜色 * @param p * @return */
        private  boolean colorOf(RABNode<E> p){
            return p==null?BLACK:p.color;
        }
        /** * 获取父结点 * @param p * @return */
        private   RABNode<E> parentOf(RABNode<E> p){
            return p==null?null:p.parent;
        }
        /** * 获得左节点 * @param p * @return */
        private  RABNode<E> leftOf(RABNode<E> p){
            return p==null?null:p.left;
        }
        /** * 获得右节点 * @param p * @return */
        private  RABNode<E> rightOf(RABNode<E> p){
            return p==null?null:p.right;
        }
        /** * 设置颜色 * @param p * @param c */
        private  void setColor(RABNode<E> p ,boolean c){
            if(p!=null)
                p.color = c;
        }
        /** * 左旋转 * @param p */
    
        private  void  rotateLeft( RABNode<E> p){
            if( p != null  ){
                RABNode<E> r = p.right;
                p.right = r.left;
                if(r.left != null){
                    r.left.parent = p;
                }
                r.parent = p.parent;
                if(p.parent == null){
                    root = r;
                }else if(p.parent.left ==p)
                    p.parent.left = r;
                else 
                    p.parent.right = r;
                r.left = p;
                p.parent = r ;
            }
        }
        /** * 右旋转 * @param p */
        private void rotateRight(RABNode<E> p){
            if( p != null){
                RABNode<E> l = p.left;
                p.left =l.right;
                if(l.right!= null)
                    l.right.parent = p;
                l.parent = p.parent;
                if(p.parent == null)
                    root = l;
                else if(p.parent .left ==p)
                    p.parent .left = l ;
                else 
                    p.parent .right = l;
                l.right = p;
                p.parent = l;
            }
        }
        /** * 定义红黑树节点类 * @author chenjingbin * * @param <E> */
         static class RABNode<E extends Comparable<E>>{ 
            E element;
            RABNode<E> right = null;
            RABNode<E> left = null;
            RABNode<E> parent;
            boolean color = BLACK;
            public RABNode(E e,RABNode<E> parent){
                element = e;
                this.parent =parent;
            }
        }
    }

上面的代码，删除部分没有写，因为还有点搞不懂，那过几天才去写，后面一定会补上删除代码的部分。在插入节点之前那是跟二叉查找树一样的，不同的是在插入之后需要去修改红黑树的平衡。下面是介绍如何去处理插入后的修护问题

*  case1:当前节点的父结点是红色，且当前 节点的祖父节点的另一个子节点（叔叔节点）也是红色  
    处理策略：（1）将父结点设为黑色（2）将叔叔节点设置为黑色（3）将祖父节点设置为红色（4）将祖父节点设置为“当前节点”（红色节点）：即，之后继续对当前节点进行操作。
 *  case2：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子  
    处理策略：（1）将父结点作为新的当前节点（2）以新的当前节点为支点进行左旋转
 *  case3：当前节点的父结点是红色，叔叔节点是黑色，且当前节点是其父结点的左孩子  
    处理策略：（1）将父结点设置为黑色（2）将祖父节点设置为红色（3）以祖父节点为支点进行右旋转

再上面的代码中还有比较经典的函数，那就是左旋转和右旋转。因为那比较常用到。大家可以好好体会的。