目录

具体代码在 : RBTree, 欢迎star

• 一、红黑树（Red Black Tree）

  • 1、初识红黑树
  • 2、红黑树的等价变化
  • 3、红黑树 vs 2-3-4树
  • 4、红黑树节点关系

• 二、红黑树的实现

  • 1、构造方法

  • 2、添加

    • 2.1 parent为BLACK

      • 2.2 parent为RED（Double Red）
      • 2.2.1 添加-修复性质4-LL\RR
      • 2.2.2 添加-修复性质4-LR\RL
      • 2.2.3 添加-修复性质4-上溢-LL
      • 2.2.4 添加-修复性质4-上溢-RR
      • 2.2.5 添加-修复性质4-上溢-LR
      • 2.2.6 添加-修复性质4-上溢-RL
    • 2.3 添加总结
    • 2.4 添加实现

  • 3、删除

    • 3.1 删除拥有1个RED子节点的BLACK节点

    • 3.2 删除 - BLACK叶子节点 - sibling为BLACK

      • 3.2.1 sibling至少有1个RED子节点
      • 3.2.2 sibling没有RED子节点
      • 3.2.3 sibling为RED
    • 3.3 删除实现
• 三、红黑树的平衡
• 四、红黑树的时间复杂度
• 五、AVL树 VS 红黑树

一、平衡二叉搜索树（Balance Binary Search Tree）

跳转到目录

1、初识红黑树

• 红黑树也是一种自平衡的二叉搜索树，也曾叫做平衡二叉B树。
• 红黑树必须满足以下5条性质：
  
• 在添加和删除节点之后，让树依然满足以上5条性质，就可以保证平衡。

2、红黑树与4阶B树的等价变换

跳转到目录

• 红黑树
  
• 将红黑树的红色节点上移靠近它的黑色父节点。
  
• 红黑树和4阶B树具有等价性。
• BLACK节点与它的RED子节点融合在一起，形成1个B树节点。
• 红黑树的BLACK节点数与4阶B树的节点总个数相等。

注意:

• 1、所以,后面我们对红黑树的添加、删除操作,都需要使用到B树的一些性质,和站在B树的角度来思考!
• 2、红黑树转B树, 向上合并, 必然是红色节点向其黑父节点靠拢,且中间结点一定是黑色,两边为红色结点, 因为红黑树的BLACK节点数,就是4阶B树的节点数
• 3、红黑树只能和4阶B树进行等价变换,后面的代码和所有的操作,都针对于4阶B树等价的红黑树进行操作的

3、红黑树 VS 2-3-4树

跳转到目录

• 如果上图最底层的BLACK节点不存在，那么整颗B树只有一个节点，而且是超级节点。

4、红黑树节点关系

跳转到目录

• 父节点（parent）

  • 55是38和80的父节点，38是25和46的父节点。

• 兄弟节点（sibling）

  • 25和46是兄弟节点，76和88是兄弟节点。

• 叔父节点（uncle: parent的兄弟节点）

  • 25和46的叔父节点是80。

• 祖父节点（grand: parent的父节点）

  • 25的祖父节点是55。

二、红黑树的实现

跳转到目录

• 由于RBTree需要对节点进行旋转操作; 此时就需要使用到AVLTree中的旋转代码,因为AVLTree和RBTree都是平衡二叉搜索树(BalanceBinarySearchTree),BBST在BST的基础上增加了旋转功能; 为了程序的拓展性, 我们在创建一个BBST 继承 BST, AVLTree和RBTree 继承 BBST。
• BBST中主要抽取的是AVLTree和RBTree中的通用的旋转方法

1、红黑树的一些辅助方法, 还有add, remove方法(还未实现)

public class RBTree<E> extends BBST<E> { 
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    public RBTree() { 
        this(null);
    }
    public RBTree(Comparator<E> comparator) { 
        super(comparator);
    }
    @Override
    protected void afterAdd(Node<E> node) { 
    }
    @Override
    protected void afterRemove(Node<E> node, Node<E> replacement) { 
    }
    /** * 将node染成color色 * * @param node 需要染色的节点 * @param color 染成的颜色 * @return 返回染色的节点 */
    private Node<E> color(Node<E> node, boolean color) { 
        if (node == null) return node;
        ((RBNode<E>) node).color = color;
        return node;
    }
    /** * 传进来的节点染成黑色 * * @param node * @return */
    private Node<E> black(Node<E> node) { 
        return color(node, BLACK);
    }
    /** * 传进来的节点染成红色 * * @param node * @return */
    private Node<E> red(Node<E> node) { 
        return color(node, RED);
    }
    /** * 返回当前节点的颜色 * * @param node * @return 如果传入的节点为空, 默认为黑色 */
    private boolean colorOf(Node<E> node) { 
        return node == null ? BLACK : ((RBNode<E>) node).color;
    }
    /** * 节点是否为黑色 * * @param node * @return */
    private boolean isBlack(Node<E> node) { 
        return colorOf(node) == BLACK;
    }
    /** * 节点是否为红色 * * @param node * @return */
    private boolean isRed(Node<E> node) { 
        return colorOf(node) == RED;
    }
    @Override
    protected Node<E> createNode(E element, Node<E> parent) { 
        return new RBNode<>(element, parent);
    }
    // 红黑树的RBNode
    private static class RBNode<E> extends Node<E> { 
        boolean color;
        public RBNode(E element, Node<E> parent) { 
            super(element, parent);
        }
        @Override
        public String toString() { 
            String str = "";
            // 红色加 R_, 默认黑色
            if (color == RED) { 
                str = "R_";
            }
            return str + element.toString();
        }
    }

2、添加节点

跳转到目录

• 通过学习B树, 得知 :

  • B树中，新元素必定是添加到叶子节点中。
  • 4阶B树所有节点的元素个数x，都符合1 <= x <= 3。(B树的性质)
• 建议新添加的节点默认为RED，这样能够让红黑树的性质尽快满足（初识红黑树中的5条性质，除了性质4不一定满足）。
• 如果添加的是根节点，染成BLACK即可。

• 因为新元素必定是添加到叶子节点中，所以红黑树的添加一共有12种情况，分为17的左右，33的左右，46的左，50的左右，72的左右，76的右，88的左右。
• 其中4种是parent为BLACK的情况，有8种是parent为RED的情况。

2.1、parent为BLACK

跳转到目录

• 有4种情况满足红黑树的性质4：parent为BLACK。
• 并且同样也满足4阶B树的性质，因此不用做任何额外处理。
  

2.2、parent为RED（Double Red）

• 下图这8种情况需要在添加之后修复红黑树。
• 其中前4种(10,20,30,36)属于B树节点上溢的情况。

因为当在17, 33节点的左右, 添加节点的时候, eg: 在17的left添加10, 此时在B树节点的角度上, 该节点就有4个元素了, 显然不符合4阶B树的性质: 1 <= 节点元素数量 <= 3, 所以就会发生 上溢。

2.2.1、 添加-修复性质4-LL\RR

跳转到目录

• 首先当添加52和60，这两种情况分别属于RR和LL。

  • 对46进行左旋转, 50的left就指向46
  • 对76进行右旋转, 72的right就指向76

• 判定条件：uncle不是RED

  • 这个条件是针对于当添加10,20,30,36这些情况, 因为10,20的uncle为33(红色), 30,36的uncle为17(红色); 52,60它们的uncle都是黑色节点; 所以以这个为判定条件。

• 操作步骤 (恢复红黑树的性质)：

  • parent染成BLACK，grand染成RED。
  • grand进行单旋操作。
    

2.2.2、 添加-修复性质4-LR\RL

• 当添加48和74，这两种情况属于RL和LR。
• 判定条件：uncle不是RED。

• 操作步骤：

  • 自己染成BLACK，grand染成RED。

• 进行双旋操作。

  • 如果是RL，parent(50)右旋转，grand(46)左旋转。
  • 如果是LR，parent(72)左旋转，grand(76)右旋转。

2.2.3、 添加-修复性质4-上溢-LL

跳转到目录

• 现在我们来添加10，10添加之后会导致上溢，这种情况属于LL。
• 判定条件：uncle是RED。

• 操作步骤：

  • parent，uncle染成BLACK，成为独立节点;(只能是BLACK才能成为独立节点; 这里parent必然要染黑,不然会出现两个连续的红色节点)。
  • grand向上合并，染成RED，当作是新添加的节点进行处理。(只有RED节点才能向上合并, 这里当做新添加的节点处理, 也是需要染成红色,因为我们添加的就是RED节点)
  • grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK。
• LL的情况不需要旋转，只需要染色。

如下图, 我们完成了修复, 25也变红色向上合并了; 但是 25 38 55显然不符合红黑树的性质4, 不能出现连续的两个红色结点;

重要: 正常思路就是: 将38变为黑色, 25, 55变为红色即可; 但是我们发现了一个规律, 25染成红色向上合并的过程, 和我们刚才添加10到17的过程完全一致; 这里可以复用添加10节点的操作, 递归来完成, 25向上合并的操作, 可以看作25是38新添加的节点,这样就可以了

2.2.4、 添加-修复性质4-上溢-RR

• 判定条件：uncle是RED。

• 操作步骤：

  • parent，uncle染成BLACK，成为独立节点。
  • grand向上合并，染成RED，当作是新添加的节点进行处理。
    

2.2.5、 添加-修复性质4-上溢-LR

• 判定条件：uncle是RED。

• 操作步骤：

  • parent，uncle染成BLACK，成为独立节点,(parent染黑,表明红黑树不能出现连续的RED节点; uncle染黑表示,只有黑色节点才可以成为独立节点,因为红黑树黑色节点个数,对应B树的结点数量)。
  • grand向上合并，染成RED，当作是新添加的节点进行处理。
    

2.2.6、 添加-修复性质4-上溢-RL

• 判定条件：uncle是RED。

• 操作步骤：

  • parent，uncle染成BLACK，成为独立节点。
  • grand向上合并，染成RED，当作是新添加的节点进行处理。
    

2.3、 添加总结

跳转到目录

• 添加一共有12种情况。
• 其中有4种情况，添加之后父节点为黑色，添加之后不用做处理, 依然满足性质4。
• 另外8种情况，添加之后父节点为红色，不满足性质4，需要进行双红修复处理。

• 修复分为两种情况：

  • uncle不是RED：

    • LL\RR，让祖父节点进行单旋转，染成红色，让父节点成为中心，并染成黑色。
    • LR\RL，让祖父节点和父节点进行旋转，让新添加成员成为中心节点，染成黑色，祖父节点染成红色。

  • uncle是RED：

    • 父节点，叔父节点染成黑色。
    • 祖父节点染成红色，并上溢(递归复用代码)。

2.4、添加节点代码实现

跳转到目录

• rotateLeft，rotateRight方法实现, 请查看《恋上数据结构与算法》笔记（十一）：平衡二叉搜索树 (AVL树), 因为在RBTree中也用到了AVLTree的旋转操作, 所以为了复用旋转操作的代码, 我们又抽取了BBST (Balance Binary Search Tree)类 extends BST类, BBST类主要封装了旋转操作的代码, 供RBTree,AVLTree使用

• afterAdd 和 afterRemove方法, 和AVLTree中的一样, 这两个方法都是在BST类中定义的, 然后子类RBTree,AVLTree去重写这两个方法, 这两个平衡二叉树,在执行afterAdd,afterRemove的时候, 是在BST中add,remove方法执行之后再处理的; 也就是说, 添加删除操作都是一样的, 只是针对不同性质的树, 当添加删除之后, 可以会对红黑树, AVL树的性质发生改变, 所以我们才会在after的方法里面进行恢复操作!

  @Override
  protected void afterAdd(Node node) {

  Node<E> parent = node.parent;
  // 添加的是根节点(染成黑色)
  if (parent == null) { 
      black(node);
      return;
  }
  // ------------- 一共 12 种情况--------------
  // 不需要处理的4种情况: 如果父节点是黑色, 直接返回
  if (isBlack(parent)) return;
  // 根据uncle节点的颜色来判断其他的各4种情况
  Node<E> uncle = parent.sibling();
  // 祖父节点
  Node<E> grand = parent.parent;
  // 需要处理的4种情况: 叔父节点是红色
  if (isRed(uncle)) { 
      black(parent);
      black(uncle);
      // 把祖父节点染成红色, 当做新添加的节点处理(递归调用afterAdd)
      afterAdd(red(grand));
      return;
  }
  /* 因为这4种情况, RBTree需要对节点进行旋转操作; 此时就需要使用到AVLTree中的旋转代码, 因为AVLTree和RBTree都是平衡二叉搜索树(BalanceBinarySearchTree),BBST在BST的基础上增加了旋转功能; 为了程序的拓展性, 我们在创建一个BBST 继承 BST, AVLTree和RBTree再 继承 BBST */
  // 需要处理的4种情况: 叔父节点不是红色(叔父节点为空)
  if (parent.isLeftChild()) {  // L
      // LL,LR, grand都要染成红色
      red(grand);
      if (node.isLeftChild()) {  // LL
          black(parent);
      } else {  // LR
          black(node);
          rotateLeft(parent);
      }
      // LL,LR, grand最后都要右旋转
      rotateRight(grand);
  } else {  // R
      red(grand);
      if (node.isLeftChild()) {  // RL
          black(node);
          rotateRight(parent);
      } else {  // RR
          black(parent);
      }
      rotateLeft(grand);
  }
  /*if (parent.isLeftChild()) { // L if (node.isLeftChild()) { // LL black(parent); red(grand); rotateRight(grand); } else { // LR black(node); red(grand); rotateLeft(parent); rotateRight(grand); } } else { // R if (node.isLeftChild()) { // RL black(node); red(grand); rotateRight(parent); rotateLeft(grand); } else { // RR black(parent); red(grand); rotateLeft(grand); } }*/

  }

3、删除节点

跳转到目录

• B树中，最后真正被删除的元素都在叶子节点上。
  
• 删除分为删除RED节点和删除BLACK节点两种情况。
• 删除RED节点，直接删除即可，不用做任何调整。
  

• 删除BLACK节点分为3种情况。

  • 1、拥有2个RED子节点的BLACK节点，例如25。

    • 不可能被直接删除，因为会找它的前驱或后继子节点替代删除，因此不用考虑这种情况。(在BST的remove中已经处理过了)
  • 2、拥有1个RED子节点的BLACK节点，例如46，76。
  • 3、BLACK叶子节点，例如88。

3.1、 删除拥有1个RED子节点的BLACK节点

跳转到目录

• 判定条件：删除指定节点(46)后，用以代替的子节点(50)是RED。

  • (这里的判断条件, 用以替代46的结点是RED结点(50), 也就是说当删除46, 76后, 替代它们的节点是50, 72, 都是红色的; 用来区别删除88的情况)
• 将替代的子节点染成BLACK即可保持红黑树的性质。
• 例如删除46和76。

3.2、 删除 - BLACK叶子节点 - sibling为BLACK

跳转到目录

• BLACK叶子节点被删除后，会导致B树节点下溢（比如删除88）。

3.2.1、 sibling至少有1个RED子节点

• 如果sibling至少有1个RED子节点：

  • 进行旋转操作。
  • 旋转之后的中心节点继承parent的颜色。
  • 旋转之后的左右节点染为BLACK。
    如果sibling有2个RED子节点，那么可以选择删除其左子节点或右子节点，删除左子节点少做一次旋转。

举例：图1

• 删除88。
• 76左旋转，80右旋转。
• 中心节点(78)继承parent的颜色(80)。
• 80旋转下去之后，染成BLACK, 成为独立的节点。

后面两个图也是类似的操作!

3.2.2、 sibling没有RED子节点

跳转到目录

• 如果被删除节点的sibling没有1个RED子节点：

  • 将sibling染成RED，parent染成BLACK即可修复红黑树性质。
    

• 如果parent是BLACK

  • 会导致parent也下溢。
  • 这时只需要把parent当作被删除的节点处理即可，相当于递归调用afterremove。

3.2.3、 sibling为RED

跳转到目录

• 如果sibling是RED：

  • sibling染成BLACK，parent染成RED，进行旋转。
  • 于是又回到sibling是BLACK的情况。

旋转的目的: 将76作为80的左子节点; 所以染完色之后, 46,55,80是LL型, 所以对80进行右旋转, 这样就变为下图2了

3.3、删除节点的实现

跳转到目录

@Override
protected void afterRemove(Node<E> node, Node<E> replacement) { 
    // 删除的节点, 都是叶子节点
    // 如果删除的节点为红色,则不需要处理
    if (isRed(node)) return;
    // 用于取代node的节点replacement为红色
    if (isRed(replacement)) { 
        // 将替代节点染为黑色
        black(replacement);
        return;
    }
    // 删除的是根节点
    Node<E> parent = node.parent;
    if (parent == null) return;
    // 删除黑色的叶子节点(肯定会下溢)
    // 判断被删除的node是左还是右(如果直接通过sibling()方法,拿到的不准确,因为在remove方法中已经将node置为null了,然后才调用的afterRemove
    boolean left = parent.left == null || node.isLeftChild();
    Node<E> sibling = left ? parent.right : parent.left;
    if (left) {  // 被删除的节点在左边, 兄弟节点在右边
        if (isRed(sibling)) { 
            black(sibling);
            red(parent);
            rotateLeft(parent);
            sibling = parent.right;
        }
        // 兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) { 
                afterRemove(parent, null);
            }
        } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
            if (isBlack(sibling.right)) { 
                rotateRight(sibling);
                sibling = parent.right;
            }
            color(sibling, colorOf(parent));
            black(sibling.right);
            black(parent);
            rotateLeft(parent);
        }
    } else {  // 被删除节点在右边, 兄弟节点在左边
        if (isRed(sibling)) {  // 兄弟节点是红色
            black(sibling);
            red(parent);
            rotateRight(parent); // 旋转之后,改变兄弟节点,然后node的兄弟节点就为黑色了
            // 更换兄弟节点
            sibling = parent.left;
        }
        // 兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
            // 兄弟节点没有一个红色子节点(不能借一个节点给你), 父节点要向下跟node的兄弟节点合并
            /* 首先这里要判断父节点parent的颜色(如果为parent为红色,则根据B树红色节点向其黑色父节点合并原则,parent向下合并,肯定不会 发生下溢; 如果parent为黑色,则说明parent向下合并后,必然也会发生下溢,这里我们当作移除一个叶子结点处理,复用afterRemove */
            boolean parentBlack = isBlack(parent);
            // 下面两行染色的代码,是说明parent为红色的情况
            black(parent);
            red(sibling);
            if (parentBlack) { 
                afterRemove(parent, null);
            }
        } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
            // 兄弟节点的左边是黑色, 先将兄弟节点左旋转; 旋转完之后和后面两种的处理方式相同,都是再对父节点进行右旋转
            if (isBlack(sibling.left)) { 
                rotateLeft(sibling);
                sibling = parent.left; // 因为旋转之后,要更改node的sibling,才能复用下面的染色代码.不然出现bug
            }
            // 旋转之后的中心节点继承parent的颜色; 旋转之后的左右节点染为黑色
            // 先染色,再旋转: 肯定要先对node的sibling先染色
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(parent);
            rotateRight(parent);
        }
    }
}

三、红黑树的平衡

跳转到目录

• 最初遗留的困惑：为何那5条性质，就能保证红黑树是平衡的？
• 那5条性质, 可以保证红黑树等价于4阶B树

• 相比AVL树, 红黑树的平衡标准比较宽松

  • 没有一条路径会大于其他路径的2倍 (最长路径最多是最短路径的2倍)
• 红黑树是一种弱平衡、黑色节点高度的平衡。

红黑树的最大高度是 2 ∗ log2(n + 1) ，依然是 O(logn)级别

四、红黑树的平均时间复杂度

跳转到目录

• 搜索 : O(logn)
• 添加 : O(logn), 添加操作造成的旋转是 O(1)
• 删除 : O(logn), 删除操作造成的旋转是 O(1)

五、AVL树 VS 红黑树

跳转到目录

• AVL树

  • 平衡标准比较严格：每个左右子树的高度差不超过1
  • 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28）
  • 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需O(1)次旋转调整、删除最多需要 O(logn)次旋转调整

• 红黑树

  • 平衡标准比较宽松：没有一条路径会大于其他路径的2倍
  • 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40）
  • 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整

◼ 搜索的次数远远大于插入和删除, 选择AVL树

◼ 搜索、插入、删除次数几乎差不多, 选择红黑树

◼ 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树; 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树