红黑树

红黑树基本讲解

1、基本概念

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:

1.1 性质

• 性质1: 每个节点要么是黑色，要么是红色。
• 性质2: 根节点是黑色。
• 性质3: 每个叶子节点(NIL) 是黑色。
• 性质4: 每个红色节点的两个子节点一定都是黑色。
• 性质5: 任意节点到每个叶子节 点的路径都包含数量相同的黑结点。从性质5又可以推出:
  性质5.1:如果一个节点存在黑子节点， 那么该结点肯定有两个子节点

如图所示：

红黑树 并不是一个完美平衡二叉查找树，从图上可以看到，根结点100 的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每 个叶子结点的路径都包含数量相同的黑结点(性质5)。
所以我们叫红黑树这种平衡为黑色完美平衡。

1.2 自平衡操作

• 变色 : 结点的颜色由红变黑或由黑变红
• **左旋 **: 以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变
• 右旋 : 以某个结点作为支点(旋转结点), 其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

红黑树右旋操作如下所示：

红黑树左旋 操作

1.3 红黑树的查找

红黑树的查找和二叉树的查找操作类似

1.4 红黑树的插入

插入操作包括两部分：1.查找要插入节点的父节点 2.插入后进行树的平衡操作

注意: 插入节点,必须为红色，理由很简单,红色的父节点(如果存在)为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1,必须做自平衡。

2.红黑树的插入情景分析

情景1：插入的节点为空树

直接把插入的节点作为根节点就可以了，并且把根节点变成黑色

情景2：插入节点的Key已存在

处理：更新当前节点的值，为插入节点的值

情景3 插入结点的父结点为黑结点

由于插入的结点是红色的，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。如图所示：

情景4：插入节点的父节点为红色

红黑树的性质2: 根结点是黑色，如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。

分为两种情况，如下图所示

• 一种是爸爸节点为红色，叔叔节点也是红色
• 一种是爸爸节点为红色，叔叔节点为黑色或者不存在

情景4.1 叔叔结点存在并且为红结点

依据红黑树性质4 可知，红色节点不能相连==>祖父结点肯定为黑结点。因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为:红黑红
处理:
1 将爸爸节点(P)和叔叔节点(U)节点改为黑色
2 将爷爷PP改为红色
3 将爷爷PP设置为当前节点，进行后续处理

如下图所示：

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理;但如果PP的父结点是红色，则违反了红黑树的性质.所以需要将PP设置为当前节点，继续做插入操作自平衡处理，真到平衡为为止.

插入情景4.2 叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

注意:单纯从插入前来看，叔叔节点非红即空(NIL节点) ，否则的话破坏了红黑树性质5,此路径会比其它路径多-一个黑色节点。

新插入节点，可能为P节点的左子节点，也可能是P节点的右子节点,所以分为两种情况分别处理

4.2.1 新插入节点，为其父节点的左子节点(LL红色情况)

处理:

1. 变颜色:将P设置 为黑色，将PP设置为红色 ，然后以爷爷节点为当前节点
2. 对PP节点进行右旋

处理结果如下图所示：

4.2.2:新插入节点，为其父节点的右子节点(LR红色情况)


处理:

1. 对P进行左旋
2. 将P设置为当前节点，得到LL红色情况
3. 按照LL红色情况处理(1.变颜色2.右旋PP)

操作过程如下图所示：

第一步


第二步

情况4.3 叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

和上述操作4.2 相反图，如下所示：

4.3.1 新插入节点，为其父节点的右子节点(RR红色情况)

处理操作：
1.变颜色: 将P设置为黑色，将PP设置为红色

2.对PP节点进行左旋

旋转过程如下图所示：

4.3.2 新插入节点，为其父节点的左子节点(RL红色情况)

如下图所示：


处理:
1.对P进行右旋
2.将P设置为当前节点，得到RR红色情况
3.按照RR红色情况处理(1.变颜色2.左旋PP)

第一步对P节点进行右旋操作 如下图所示：

第二步：变色+旋转，如下图所示

3.红黑树代码演示

3.1 左右旋参考示意图

3.2 代码演示

RBTree.java

/**
 * 红黑树
 */
public class RBTree<K extends Comparable<K>, V> {

    private static final boolean RED = true;

    private static final boolean BLACK = false;

    private   RBNode root;

    public RBNode getRoot() {
        return root;
    }

    /**
     * 获取当前节点的父节点
     *
     * @param node
     * @return
     */
    private RBNode parentOf(RBNode node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }

    /**
     * 节点是否为红色
     *
     * @param node
     * @return
     */
    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }

    /**
     * 节点是否为黑色
     *
     * @param node
     * @return
     */
    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return false;
    }


    /**
     * 设置节点为红色
     *
     * @param node
     */
    private void setRed(RBNode node) {
        if (node != null) {
            node.color = RED;
        }
    }

    /**
     * 设置节点颜色为黑色
     *
     * @param node
     */
    private void setBlack(RBNode node) {
        if (node != null) {
            node.color = BLACK;
        }
    }

    public void inOrderPrint() {
        inOrderPrint(this.root);
    }

    private void inOrderPrint(RBNode node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.println(" key: " + node.key + "  ,value:" + node.value);
            inOrderPrint(node.right);
        }
    }

    /**
     * 左旋示意图
     */

    private void leftRotate(RBNode x) {
        RBNode y = x.right;
        x.right = y.left;
        // 1.将x的右子节点指定y的左子节点（ly) ,将y的左子节点的父节点更新为x
        if (y.left != null) {
            y.left.parent = x;
        }

        // 2.当x的父节点(不为空时) ,更新y的父节点为x的父节点 ，并将x的父节点的 子树（当前x的指数位置）指定为y
        if (x.parent != null) {
            // 如果x节点原来为其父节点的左节点，左旋时，就需要把y节点也放在左节点的位置
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                // 如果x节点原来为其父节点的右节点，左旋时，就需要把y节点也放在左节点的位置
                x.parent.right = y;
            }
        } else {
            // 说民x节点为根节点 故所以更新y节点为根节点
            this.root = y;
            this.root.parent = null;
        }

        // 3.将x的父节点更新为y ,并将y的左子节点更新为x
        x.parent = y;
        y.left = x;
    }


    /**
     * 右旋操作
     *
     *
     * @param y
     */
    private void rightRotate(RBNode y) {
        RBNode x = y.left;
        // 1.将y的左子节点更新为x的右子节点，并且更新x的右子节点的父节点为y
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }

        // 2.当y的父节点不为空时，更新x的父节点为y的父节点。更新y的父节点的指定子节点为x
        if (y.parent != null) {
            x.parent = y.parent;
            // 此时不知道原先y是在其父节点的左侧还是右侧，所以要先判断
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        } else {
            // 没有父节点
            this.root = x;
            this.root.parent = null;
        }

        // 3.更新y的节点为x,并且更新x的节点为y
        y.parent = x;
        x.right = y;
    }

    /**
     * 插入方法
     *
     * @param key   插入key
     * @param value 值
     */
    public void insertNode(K key, V value) {
        RBNode rbNode = new RBNode();
        rbNode.setKey(key);
        rbNode.setValue(value);
        rbNode.setColor(RED);
        insert(rbNode);
    }

    /**
     * 插入红黑树节点
     *
     * @param node 节点
     */
    private void insert(RBNode node) {
        // 1.查找当前节点的父节点
        RBNode parent = null;
        // 获取根节点，开始寻找
        RBNode x = this.root;

        while (x != null) {
            parent = x;
            int result = node.key.compareTo(x.key);
            if (result > 0) {
                // 说明当前节点应该放在x节点的右子树
                x = x.right;
            } else if (result < 0) {
                // 说明当前节点应该放在左子树上
                x = x.left;
            } else {
                // 如果key值相等，需要进行值的替换
                x.setValue(node.getValue());
                return;
            }
        }
        // 记录父节点
        node.parent = parent;
        if (parent != null) {
            // 判断当前节点和父节点的key值大小，从而确定新插入的节点应该放在父节点的左侧还是右侧
            int result = node.key.compareTo(parent.key);
            if (result > 0) {
                parent.right = node;
            } else {
                parent.left = node;
            }
        } else {
            // 如果没有父亲节点,当前节点就是根节点
            this.root = node;
        }

        // 红黑树插入新节点后，需要进行平衡操作，也就是左旋或者右旋操作
        balanceInsertion(node);

    }

    /**
     * 红黑树插入节点后，需要进行平衡操作
     *       情景1： 红黑树为空树时,将根节点染成黑色
     *       情景2： 插入的节点在红黑树已经存在,不需要处理
     *       情景3： 插入节点的父节点为黑色，因为所插入的路径，黑色节点没有发生变化，所以红黑树依然平衡，所以不需要处理
     *       情景4： 插入节点的父节点为红色
     *              情景4.1  叔叔节点存在,并且为红色(父和叔  都是红色节点) 根据红黑树性质4.红色节点不能直接相连，由此可知必然存在爷爷节点,且爷爷节点必定为黑节点
     *                          由此可以 a.将爸爸和叔叔节点变成黑色  b.将爷爷节点变成红色  c.并且将爷爷节点当成当前节点,进行下一轮的处理
     *              情景4.2  叔叔节点不存在或者为黑色节点，父节点为爷爷节点的左子树
     *                      情景4.2.1 插入节点为其父节点的左子节点(LL情况) a.将爸爸节点染成黑色 b.将爷爷染成红色 c.然后已爷爷节点进行右旋操作
     *                      情景4.2.2 插入节点为其父节点的右子节点(LR情况) a.已爸爸为节点进行一次左旋操作,得到(LL双红的情况 4.2.1) 然后指定爸爸节点为当前节点,执行下一轮的操作
     *              情景4.3  叔叔节点不存在,或者为黑色节点,父节点为爷爷节点的右子树
     *                      情景4.3.1 插入节点为其父节点的右子节点(RR情况) a.将爸爸染成黑色节点  b.将爷爷染成红色 c.然后已爷爷节点进行左旋操作
     *                      情景4.3.2 插入节点为其父节点的左子节点(RL情况) a.以爸爸节点进行一次右旋,得到RR双红的场景( RR情况 4.3.1).然后指定爸爸节点为当前节点,进行下一轮的操作
     * @param node
     */
    private void balanceInsertion(RBNode node) {
        this.root.setColor(BLACK);
        // 1.获取父节点和爷爷节点
        RBNode parent = parentOf(node);
        RBNode gparent = parentOf(parent);
        // 情景3 : 插入节点的父节点为黑色,不需要处理
        // 情景4： 插入节点的父节点为红色
        if (parent != null && isRed(parent)) {
            // 叔叔节点
            RBNode uncle = null;
            // 如果爸爸是爷爷的左孩子，那么叔叔必然是爷爷的右孩子,反之一样
            if (parent == gparent.left) {
                uncle = gparent.right;
                // 情景4.1  叔叔节点存在,并且为红色(父和叔  都是红色节点)
                if (uncle != null && isRed(uncle)) {
                    // a.将爸爸和叔叔节点变成黑色  b.将爷爷节点变成红色  c.并且将爷爷节点当成当前节点,进行下一轮的处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    balanceInsertion(gparent);
                    return;
                }
                // 情景4.2  叔叔节点不存在或者为黑色节点，父节点为爷爷节点的左子树
                if (uncle == null || isBlack(uncle)) {
                    // 情景4.2.1 插入节点为其父节点的左子节点(LL情况)
                    if (node == parent.left) {
                        // a.将爸爸节点染成黑色 b.将爷爷染成红色 c.然后已爷爷节点进行右旋操作
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);
                        return;
                    }
                    // 情景4.2.2 插入节点为其父节点的右子节点(LR情况)
                    if (node == parent.right) {
                        // a.已爸爸为节点进行一次左旋操作,得到(LL双红的情况 4.2.1) 然后指定爸爸节点为当前节点,执行下一轮的操作
                        leftRotate(parent);
                        balanceInsertion(parent);
                        return;
                    }
                }
            } else {
                // 父节点为爷爷节点的右子树,则叔叔节点就是爷爷节点的左子树
                uncle = gparent.left;
                // 情景4.1  叔叔节点存在,并且为红色(父和叔  都是红色节点)
                if (uncle != null && isRed(uncle)) {
                    // a.将爸爸和叔叔节点变成黑色  b.将爷爷节点变成红色  c.并且将爷爷节点当成当前节点,进行下一轮的处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    balanceInsertion(gparent);
                    return;
                }

                // 情景4.3  叔叔节点不存在,或者为黑色节点,父节点为爷爷节点的右子树
                if (uncle == null || isBlack(uncle)) {
                    // 情景4.3.1 插入节点为其父节点的右子节点(RR情况) a.将爸爸染成黑色节点  b.将爷爷染成红色 c.然后已爷爷节点进行左旋操作
                    if (node == parent.right) {
                        setBlack(parent);
                        setRed(gparent);
                        leftRotate(gparent);
                        return;
                    }

                    // 情景4.3.2 插入节点为其父节点的左子节点(RL情况)
                    if (node == parent.left) {
                        // a.以爸爸节点进行一次右旋,得到RR双红的场景( RR情况 4.3.1).然后指定爸爸节点为当前节点,进行下一轮的操作
                        rightRotate(parent);
                        balanceInsertion(parent);
                        return;
                    }

                }
            }
        }
    }

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

3.3 运行结果演示

没做类型处理，插入的都是字符串比较，按照字符串的ASICC进行排序和平衡，颜色就是区分显示，不表示红黑色

4.红黑树学习地址

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html