导语

• 红黑树的难点主要是何时为红色，何时为黑色，每次增删都可能对应着树的颜色发生变化
• 为什么存在红黑树，红黑树具体有哪些优势，和平衡二叉树的区别
• 笔者也会介绍2-3树，是为了更好地理解红黑树，若对红黑树性质有一些了解可直接跳过2-3树部分
• 本文的目的是为了更好的了解红黑树的机制和特性，结合所学资料，仅介绍添加方法时，红黑树发生的变化

1. 2-3树

1. 2-3树定义

2-3树是一种简单的由二节点和三结点组成的绝对平衡的B型树。
 二结点：即该结点有一个元素，有两个空子结点
 三结点：即该结点有两个元素，有三个空子结点
 绝对平衡：类似满二叉树，但是有些结点可以存在两个元素

2-3树基础

2. 2-3树的添加操作

• 基础操作

1. 对于一个空树来说，会构建成一个二节点(后续二节点都是拆分得到)
2. 对于一个二节点，在添加一个元素后会变成(融合成)三结点
3. 对于一个三结点，在添加一个元素后会暂时变成(融合成)四结点，之后对其进行拆分，拆分成一个父二节点拥有两个子二节点，若父二节点非根结点，再和其父节点进行向上融合

• 举例构建一个2-3树，依次添加元素{50，36，78，25，45，16，8}

  1.向一个空2-3树添加元素50，此时会构建一个二结点

  
  1.png

  2.再添加元素36，此时会和已有值为50的二节点融合成三结点

  
  2.png

  3.再添加元素78，此时会先融合成四节点，再拆分，而拆分后的父结点为根结点，无需向上融合。

  
  3.png

  4.再依次添加元素25，45
    添加元素25会和值为36的二节点融合成三结点；
    再添加元素45后,此三结点会先融合成四结点，再拆分，拆分后的值为36的父二结点向上融合，与值为50的结点构成三结点

  
  4.png

  5.再依次添加元素16，8
    添加元素16会和值为25的二节点融合成三结点；
    再添加元素8后,此三结点会先融合成四结点，再拆分，拆分后的值为16的父二结点向上融合，与值为(36，50)的三结点构成四结点，再次拆分，直到拆分的父节点向上融合到根结点(即变成二结点)或与其父结点融合成为三结点

  
  5.png

---

Ⅱ. (左倾)红黑树

左倾的意思？

• 红黑树分成左倾红黑树和右倾红黑树，只是人为约定的，即一个黑结点不可能同时拥有两个红色子结点，因为此时红黑树需要进行颜色反转处理，后续会介绍，为什么不能同时存在，且什么是颜色反转。左倾的意思是，一个黑结点若其子结点为红色，必然出现在左孩子上，右孩子必然是黑色结点(若红结点在右孩子上，则进行左旋)

1. 红黑树性质

• 1.每个结点或为黑色，或为红色
• 2.根结点为黑色
• 3.每个叶子节点为黑色的(红黑树中叶子结点指空结点)
• 4.如果一个结点是红色的，那他的左右孩子结点为黑色
• 5.从任意一个结点到叶子结点，经过的黑色结点是一样的

2. 红黑树与2-3树的关系

• 2-3树可以等价的转换成红黑树，由于红黑树是黑绝对平衡二叉树，所以相当于红色的左子结点与黑父亲结点是一个2-3树中的三结点。

• 2-3树中二结点 == 红黑树中某黑结点，左右孩子皆为黑结点的情况

• 2-3树中三结点 == 红黑树种某黑节点的左孩子为红节点的情况(右孩子必为黑色)

• 2-3树中新增结点需要融合已有叶子节点 == 红黑树中添加一个红色结点，所以红黑树中添加的新结点默认为红色

• 2-3树中结点拆分，向上融合 == 红黑树中颜色转换，拆分为孩子的结点为黑结点，拆分为双亲的结点需要上向融合，所以为红节点

  
  2-3树与红黑树关系.png

3. 以2-3树解读红黑树定义性质

• 第一条：每个结点或为黑色，或为红色

如2-3树与红黑树关系图：
 1.黑色结点代表(双子为黑色)二结点或三结点中的右结点
 2.红色结点可以看作三结点中的左结点

• 第二条：根结点为黑色

根据第一条解释，不管根结点相当于2-3树中的二结点或是三结点中的右结点，都是黑色的

• 第三条：每个叶子节点为黑色的(红黑树中叶子结点指空结点)

1.若叶子结点不为黑色，而不为空的叶子结点为红色(关系图)，则会出现相当于2-3树中四节点的情况，因为红色结点永远与父亲结点融合
2.如上面关系图中红色叶子结点16，其父亲右结点为空，若空结点为红色，则不满足左倾的性质，因为双结点为红色结点需要进行颜色反转

• 第四条：如果一个结点是红色的，那他的左右孩子结点为黑色

若一个结点为红色，相当于为2-3树中的三结点的左结点；
而三结点有两种类型的孩子，二结点和三结点，二结点准换成红黑树为黑色结点，而三结点转换为红黑树，相当于连接的为三结点的右结点，右结点也必为黑色，因此红色结点的双子必为黑色，如关系图中值为(36-50)三结点和其二结点，三结点孩子，转换成的样子。

• 第五条：从任意一个结点到叶子结点，经过的黑色结点是一样的

因为红黑树只看黑节点即为黑平衡满二叉树，而满二叉树必然经过的结点数目是一样的。

4. 红黑树的添加的所有情况

• 向一个空的红黑树中添加一个元素

  
  情况A

• 向以值为12的根结点的红黑树中添加元素(值<12)

  
  情况B-1

• 向以值为12的根结点的红黑树中添加元素(值>12)

  
  情况B-2

• 向拥有值为6的左儿子结点的值为12的结点中添加元素(值>12)

  
  情况C-1

• 向拥有值为6的左儿子结点的值为12的结点中添加元素(值<6)

  
  情况C-2

• 向拥有值为6的左儿子结点的值为12的结点中添加元素(6<值<12)

  
  情况C-3

5. 红黑树的添加操作及其实现

• 举例结合代码实现添加操作,构建一个红黑树，依次添加依次添加元素{50，36，78，90，95，48，40}

5.1. 红黑树也是基于二分搜索树，因此可以复用二分搜索树的实现，而红黑树比二分搜索树多出了颜色标识，因此增加一个boolean元素，默认规定red = true,black = false

  public class RedBlackTree<K extends Comparable<K>,V> {

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

    private class Node{
        public K key;
        public V value;
        public Node left;
        public Node right;
        public boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            //默认添加的新结点为红色
            color = RED;
        }
    }

    private Node root;
    private int size;

    public RedBlackTree() {
        root = null;
        size = 0;
    }
 }

5.2. 空结点我们默认为黑色，在程序中增加一个私有方法，来判断当前结点是否为红色结点

     /**
     * 判断结点node的颜色
     * @return
     */
    private boolean isRed(Node node){
        if(node == null){
            return BLACK;
        }
        return node.color ;
    }

5.3. 添加元素的操作和二分搜索树的过程过程是一致的，在回溯到过程中维护红黑树的性质，而在每次维护某结点后，会回溯维护其父结点，此时如同2-3树中的向上融合，因此其父结点变为红色，以此回溯维护，最差会维护到根结点，此时根则为红色，而红黑树性质根结点为黑色，因此再回溯维护完整颗红黑树后，维护一次根结点为黑色

 /**
     * 向红黑树中添加一个元素
     * @param key :
     * @param value :
     */
    public void add(K key,V value){
        root = add(root,key,value);
        //回溯整颗红黑树后，根结点维护为黑结点
        root.color = BLACK;
    }

5.4. 上述准备工作已完成，接下来根据例子来实现代码的添加操作

1. 先往空红黑树中添加第一个元素50，即情况A

   
   1.png

此时结点并不需要在代码进行任何操作，因为相当于一个2-3树中二结点

2. 再添加元素36，即情况B-1

   
   2.png

此时结点并不需要在代码进行任何操作，因为相当于一个2-3树中的三结点

3. 再添加元素78，即情况C-1

   
   3.png

此时结点需要代码进行颜色反转操作，即情况C-1
此操作相当于2-3树中对一个三结点再融合一个元素
此时需要拆分成一个父二结点和两个子二结点，其中子二结点为黑色，父二结点需要向上融合，因此为红色
代码如下：
 /**
  * 颜色反转
 */
 private void flipColors(Node node){
     node.color = RED;
     node.left.color = node.right.color = BLACK;
 }

4. 再添加元素90，此操作即情况B-2(只是父节点非根结点，并不影响)

   
   4.png

此操作相当于2-3树中对一个结点进行融合，但是我们规定红黑树为左倾的，只支持添加新元素从左边融合结点，所以进行左旋操作
后继结点维持此结点的颜色不变：后继结点继承此结点颜色
而旋转后并没有改变子结点融合父节点的步骤，因此此时的新叶子结点需要融合新父亲结点(后继结点)，所以新叶子结点变成红色，相当于本次添加实际上新添加78这个元素

代码实现：
 /**
     *           node                                x
     *          /  \                               /   \
     *        T4    x          向左旋转(y)       node    Z
     *            /   \      --------------->   /  \
     *          T3     Z                       T4  T3
     *
     * 左旋转
     * @param node：
     * @return ：
     */
    private Node leftRotate(Node node){
        //后继结点为该结点的右儿子
        Node successor = node.right;

        //旋转
        //node结点的右儿子变成后继结点的左子树
        node.right = successor.left;
        //后继结点的左子树为node结点
        successor.left = node;

        //重新上色
        //后继结点颜色继承此结点
        successor.color = node.color;
        //新的叶子结点为红色
        node.color = RED;

        return successor;
    }

5. 再添加元素95，即 情况C-1 和 情况B-2

   
   5.png

此过程相当于上述添加78和90的结合,，因此两种变换方式并非是互斥的，是满足条件即触发

6. 再添加元素48，即 情况B-2

   
   6.png

此操作与情况B-2一样

7. 再添加元素40,即情况C-3转换成情况C-2(转换的过程即情况B-2，父节点为黑是二结点添加，为红则是三结点添加，本质是一样的)，最后成为情况C-1

   
   7.png

在本过程中，颜色转换和左旋之前介绍过，右旋和左旋同理，右旋相当于2-3树中对一个三结点融合一个元素，需要拆分成三个二结点，其中父二结点可能和其父亲结点再次发生融合
   /**
     * 右旋转：
     *         node                              x
     *        /  \                            /     \
     *       x    T4      向右旋转(y)         Z     node
     *     /   \        --------------->           /   \
     *    Z    T3                                 T3   T4
     * @param node :
     * @return :
     */
    private Node rightRotate(Node node){
        Node successor = node.left;

        //旋转
        node.left = successor.right;
        successor.right = node;

        //重新上色
        successor.color = node.color;
        node.color = RED;

        return successor;
    }

5.5. 添加操作总结

• 由上述添加过程发现，
  1：我们在添加元素后回溯过程中，对同一个结点(此结点可能经过旋转由后继结点变成该结点，所以同一个结点指同一个位置的结点)可能需要采用多种方式来完成红黑树的性质；
  2：所有对红黑树的的操作，都可以归结于三种，左旋，右旋，颜色转换，三种操作非互斥，而是满足条件即触发

在新增结点A为红色结点，空结点为黑色结点的前提下，设新增的结点A的值为a,且与结点F,值为f有位置添加关系，且F若存在非空左儿子，则为C，值为c

红黑树操作	添加位置	处理情况	对F来说的情况	对应2-3树添加关系
左旋	A结点为F结点的右儿子，即a > f	父节点任意颜色，但左孩子为黑色	A = red && C = balck	对一个二结点融合新元素，将其转换成左边融合(左倾红黑树，不允许融合的元素大于二结点的值)
右旋	A结点为C结点的左儿子时，即a < c	新增结点的父节点为红色	A = red && C = red(C为A的父亲)	即对一个三结点融合新元素，暂时成为一个四结点
颜色反转	A结点为F结点的右儿子，即a > f	父节点为黑色，但左孩子为红色	A = red && C = red (A，C为兄弟)	对一个添加新结点的三结点暂时融合的四节点，进行拆分，拆分成三个二结点

三种操作维护时机和关系(图来源于慕课网数据结构讲解)：

三种操作维护时机与关系

 /**
     * 向以node为根的红黑树中添加一个元素，
     * 并返回插入新结点后，红黑树的根
     * @param node ：
     * @param key ：
     * @param value ：
     */
    private Node add(Node node, K key, V value) {

        if(node == null){
            size++;
            //默认插入红色结点
            return new Node(key,value);
        }

        if(key.compareTo(node.key) < 0){
            node.left = add(node.left,key,value);
        }else if (key.compareTo(node.key) > 0){
            node.right = add(node.right,key,value);
        }else {
            node.value = value;
        }

        //维护红黑树性质

        //1.当前结点右孩子是否为红色，且左孩子不为红色 --> 左旋转
        if(isRed(node.right) && !isRed(node.left)){
            node = leftRotate(node);
        }

        //2.当前结点的左孩子为红结点，左孩子的左孩子为红结点 --> 右旋转
        if(isRed(node.left) && isRed(node.left.left)){
            node = rightRotate(node);
        }

        //3.如果当前结点的左孩子和右孩子都是红色结点 ---> 反转颜色
        if(isRed(node.right) && isRed(node.left)){
            flipColors(node);
        }

        return node;
    }

6. 测试

• 测试红黑树，我们以上述举例添加的元素来做测试，看看结果是否与图中一样
  因此我们需要在代码中增加一下红黑树的结构显示
• 思路：重写toString方法，以根结点深度为0，每增加一个深度在输出元素前添加一个字符串“---”，且再输出元素前判断结点的颜色，以"B-value"或"C-value"代表元素及其颜色

 /**
     * 输出红黑树形状：
     *      以中序遍历形式输出红黑树
     *      以根结点为深度0，其子结点深度+1
     *      红结点以 R-结点值  形式
     *      黑结点以 B-结点值  形式
     *
     * @return ：
     */
    @Override
    public String toString() {

        StringBuilder str  = new StringBuilder();
        getRBTreeStructure(root,str,0);
        return str.toString();
    }

    /**
     *  中序遍历以node为根结点的红黑树，描述红黑树形状和颜色
     * @param node: 根结点
     * @param str :
     * @param depth : 结点深度
     * @return :
     */
    private void getRBTreeStructure(Node node, StringBuilder str, int depth) {
        if(node == null){
            return;
        }
        getRBTreeStructure(node.left,str,depth + 1);
        str.append(getRBTreeValue(node,depth)+"\n");
        getRBTreeStructure(node.right,str,depth + 1);
    }

    private String getRBTreeValue(Node node, int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("— — —");
        }
        if(isRed(node)){
            sb.append("R+");
        }else {
            sb.append("B+");
        }
        sb.append(node.key);
        return sb.toString();
    }

• 测试结果

  
  测试结果.png