红黑树

红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST),树上的每个节点都遵循下面的规则:

  1. 每个节点要么是黑色,要么是红色。
  2. 根节点是黑色。
  3. 每个叶子节点(NIL)是黑色。
  4. 每个红色结点的两个子结点一定都是黑色。
  5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树能自平衡,它靠的是什么?三种操作:左旋、右旋和变色

image

1 旋转操作

1.1 概念讲解

左旋:以某个节点作为旋转点,其右子节点变为旋转节点的父节点,右子节点的左子节点变为旋转节点的右子节点,左子节点保持不变。

image
image

右旋:以某!个节点作为旋转点,其左子节点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子节点,右子节点保持不变。

image
image

1.2 代码实现

先进行类结构定义

package com.bobo.util.treemap;

public class BRTree {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

    public void setRoot(RBNode root) {
        this.root = root;
    }

    /**
     * 表示 节点
     * @param <K>
     * @param <V>
     */
    static class RBNode<K extends Comparable<K>,V>{
        // 节点是双向的
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode() {
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

左旋代码实现

    /**
     * 围绕p左旋
     *     p               pr(r)
     *    / |             / \
     *   pl  pr(r) =>    p   rr
     *      / \         / \
     *     rl  rr     pl  rl
     *
     *  左旋的时候
     *  p-pl 和 pr-rr的关系不变
     *  pr-rl 要变为 p-rl
     *      也就是 rl要变为 p的右子节点
     *      同时 p要成为 rl 的父节点
     *  还有就是要判断  p 是否有父节点
     *  如果没有
     *     r 变为 root 节点
     *  如果有
     *     r.parent = p.parent
     *     还要设置 r为 p.parent 的子节点(可能左也可能右)
     *     如果 p.parent.left == p
     *        p.parent.left = r;
     *     否则
     *        p.parent.right = r;
     *    最后
     *       p.parent = r;
     *       r.left = p;
     * @param p
     */
    private void leftRotate(RBNode p){
        if(p != null){
            RBNode r = p.right;
            // 1.设置 pr-rl 要变为 p-rl
            // 把rl设置到p的右子节点
            p.right = r.left;
            if(r.left != null){
                // 设置rl的父节点为p
                r.left.parent = p;
            }
            // 2.判断p的父节点情况
            r.parent = p.parent; // 不管 p是否有父节点,都把这个父节点设置为 r的父节点
            if(p.parent == null){
                root = r; // p没有父节点 则r为root节点
            }else if(p.parent.left == p){
                p.parent.left = r; // 如果p为 p.parent的左子节点 则 r 也为 p.parent的左子节点
            }else{
                p.parent.right = r; // 反之设置 r 为 p.parent的右子节点
            }
            // 最后 设置 p 为 r 的左子节点
            r.left = p;
            p.parent = r;
        }
    }

右旋实现:

    /**
     * 围绕p右旋
     * @param p
     */
    public void rightRotate(RBNode p){
        if(p != null){
            RBNode r = p.left;
            p.left = r.right;
            if(r.right != null){
                r.right.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.right = p;
            p.parent = r;
        }
    }

2-3-4树中结点添加需要遵守以下规则:

  • 插入都是向最下面一层插入
  • 升元:将插入结点由 2-结点升级成 3-结点,或由 3-结点升级成 4-结点;
  • 向 4-结点插入元素后,需要将中间元素提到父结点升元,原结点变成两个 2-结点,再把元素插入2-结点中,如果父结点也是 4-结点,则递归向上层升元,至到根结点后将树高加1;

而将这些规则对应到红黑树里,就是:

  • 新插入的结点颜色为 红色 ,这样才可能不会对红黑树的高度产生影响。
  • 2-结点对应红黑树中的单个黑色结点,插入时直接成功(对应 2-结点升元)。
  • 3-结点对应红黑树中的 黑+红 子树,插入后将其修复成 红+黑+红 子树(对应 3-结点升元);
  • 4-结点对应红黑树中的 红+黑+红 子树,插入后将其修复成 红色祖父+黑色父叔+红色孩子 子树,然后再把祖父结点当成新插入的红色结点递归向上层修复,直至修复成功或遇到 root 结点;

公式:红黑树+新增一个节点(红色)=对等的2-3-4树+新增一个节点

2.1 新增节点示例

我们通过新增2-3-4树的过程来映射对应的红黑树的节点新增

image

2-3-4树的新增(全部在叶子节点完成)

1.新增一个节点,2 节点

image

2.新增一个节点,与2节点合并,直接合并

image

3.新增一个节点,与3节点合并,直接合并

image

插入的值的位置会有3种情况

对应的红黑树为:

image

4.新增一个节点,与4节点合并,此时需要分裂、

image

插入值的位置可能是

image

对应的红黑树的结构为

image

2.2 新增代码实现

红黑树的新增规则我们理清楚了,接下来就可以通过Java代码来具体的实现了。

先实现插入节点,这就是一个普通的二叉树的插入

 /**
     * 新增节点
     * @param key
     * @param value
     */
    public void put(K key , V value){
        RBNode t = this.root;
        if(t == null){
            // 说明之前没有元素,现在插入的元素是第一个
            root = new RBNode<>(key , value == null ? key : value,null);
            return ;
        }
        int cmp ;
        // 寻找插入位置
        // 定义一个双亲指针
        RBNode parent;
        if(key == null){
            throw new NullPointerException();
        }
        // 沿着跟节点找插入位置
        do{
            parent = t;
            cmp = key.compareTo((K)t.key);
            if(cmp < 0){
                // 左侧找
                t = t.left;
            }else if(cmp > 0){
                // 右侧找
                t = t.right;
            }else{
                // 插入节点的值==比较的节点。值替换
                t.setValue(value==null?key:value);
                return;
            }
        }while (t != null);
        // 找到了插入的位置  parent指向 t 的父节点  t为null
        // 创建要插入的节点
        RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);
        // 然后判断要插入的位置 是 parent的 左侧还是右侧
        if(cmp < 0){
            parent.left = e;
        }else{
            parent.right = e;
        }
        // 调整  变色 旋转
        fixAfterPut(e);
    }

然后再根据红黑树的特点来实现调整(旋转,变色)

private boolean colorOf(RBNode node){
        return node == null ? BLACK:node.color;
    }

    private RBNode parentOf(RBNode node){
        return node != null ? node.parent:null;
    }

    private RBNode leftOf(RBNode node){
        return node != null ? node.left:null;
    }

    private RBNode rightOf(RBNode node){
        return node != null ? node.right:null;
    }

    private void setColor(RBNode node ,boolean color){
        if(node != null){
            node.setColor(color);
        }
    }

    /**
     * 插入节点后的调整处理
     * 1\. 2-3-4树 新增元素 2节点添加一个元素将变为3节点 直接合并,节点中有两个元素
     *      红黑树:新增一个红色节点,这个红色节点会添加在黑色节点下(2节点) --- 这种情况不需要调整
     * 2\. 2-3-4树 新增元素 3节点添加一个元素变为4节点合并 节点中有3个元素
     *      这里有6中情况,( 根左左 根左右  根右右 根右左)这四种要调整  (左中右的两种)不需要调整
     *      红黑树:新增红色节点 会添加到 上黑下红的节点中 = 排序后中间节点是黑色,两边节点是红色
     *
     *  3\. 2-3-4树:新增一个元素 4节点添加一个元素需要裂变:中间元素升级为父节点,新增元素与剩下的其中一个合并
     *      红黑树:新增节点是红色+爷爷节点是黑色,父亲节点和叔叔节点为红色 调整为
     *              爷爷节点变红色,父亲和叔叔节点变为黑色,如果爷爷节点为root节点则调整为黑色
     * @param x
     */
    private void fixAfterPut(RBNode<K, Object> x) {
        x.color = RED;
        // 本质上就是父节点是黑色的就不需要调整,对应的 2 3的情况
        while(x != null && x != root && x.parent.color == RED){
            // 1\. x 的父节点是爷爷的 左孩子
            if(parentOf(x) == parentOf(parentOf(x)).left){
                // 获取当前节点的叔叔节点
                RBNode y = rightOf(parentOf(parentOf(x)));
                // 情况3
                if(colorOf(y) == RED){
                    // 说明是 上3的情况  变色处理
                    // 父亲节点和叔叔节点设置为黑色
                    setColor(parentOf(x),BLACK);
                    setColor(y,BLACK);
                    // 爷爷节点设置为 红色
                    setColor(parentOf(parentOf(x)),RED);
                    // 递归处理
                    x = parentOf(parentOf(x));
                }else{
                    // 情况 2
                    if(x == parentOf(x).right){
                        // 如果x是父节点的右节点那么我们需要先根据 父节点 左旋
                        x = parentOf(x);
                        leftRotate(x);
                    }
                    // 叔叔节点为空  对应于 上面的情况2
                    // 将父节点变为黑色
                    setColor(parentOf(x),BLACK);
                    // 将爷爷节点变为红色
                    setColor(parentOf(parentOf(x)),RED);
                    // 右旋转  根据爷爷节点右旋转
                    rightRotate(parentOf(parentOf(x)));

                }
            }else{
                // x 的父节点是爷爷是右孩子
                // 获取父亲的叔叔节点
                RBNode y = leftOf(parentOf(parentOf(x)));
                if(colorOf(y) == RED){
                    // 情况3
                    setColor(parentOf(x),BLACK);
                    setColor(y,BLACK);
                    setColor(parentOf(parentOf(x)),RED);
                    x = parentOf(parentOf(x));
                }else{
                    // 情况2
                    if( x == parentOf(x).left){
                        x = parentOf(x);
                        rightRotate(x);
                    }
                    setColor(parentOf(x),BLACK);
                    setColor(parentOf(parentOf(x)),RED);
                    leftRotate(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

2.3 插入节点

不通过2-3-4树来实现添加节点的分析,看大家是否能理解哦

image

插入的场景

image

插入场景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行,但注意,根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。
处理:把插入结点作为根结点,并把结点设置为黑色。

image

插入场景2:插入结点的父结点为黑结点
由于插入的结点是红色的,且父节点为黑色节点,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。
处理:直接插入。

image

插入场景3:插入结点的父结点为红结点
再次回想下红黑树的性质2:根结点是黑色。如果插入的父结点为红结点,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这点很重要,因为后续的旋转操作肯定需要祖父结点的参与。

插入场景3.1:叔叔结点存在并且为红结点
从红黑树性质4可以,祖父结点肯定为黑结点,因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为:红黑红。

image

实际案例:

祖父节点为根节点:红黑黑

image
image

祖父节点不为根节点:

image
image

插入场景3.2**:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点

单纯从插入前来看,也即不算情景3.1自底向上处理时的情况,叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点,而父结点为红结点,那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了,这不满足红黑树的性质5。后续情景同样如此,不再多做说明了。

前文说了,需要旋转操作时,肯定一边子树的结点多了或少了,需要租或借给另一边。插入显然是多的情况,那么把多的结点租给另一边子树就可以了。

插入场景3.2.1:插入结点是其父结点的左子结点

image
image
image

插入场景3.2.2:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的右子结点

image
image
image