数据结构与算法（第一季）：红黑树

一、红黑树（Red Black Tree）

1、初识红黑树

image

• 红黑树也是一种自平衡的二叉搜索树，也曾叫做平衡二叉B树。
• 红黑树必须满足以下5条性质：
  • 节点是RED或者BLACK
  • 根节点是BLACK
  • 叶子节点（外部节点，空节点）都是BLACK
  • RED节点的子节点都是BLACK
    • RED节点的parent都是BLACK
    • 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
  • 从任意节点到叶子节点的所有路径都包含相同数目的BLACK节点。
• 在添加和删除节点之后，让树依然满足以上5条性质，就可以保证平衡。

2、红黑树的等价变化

image

• 我们将红黑树的红色节点上移靠近父节点。

image

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

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

image

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

4、红黑树节点关系

image

• 父节点（parent）
  • 55是38和80的父节点，38是25和46的父节点。
• 兄弟节点（sibling）
  • 25和46是兄弟节点，76和88是兄弟节点。
• 叔父节点（parent的兄弟节点）
  • 25和46的叔父节点是80。
• 祖父节点（parent的父节点）
  • 25的祖父节点是55。

二、红黑树的实现

1、构造方法

• 除了构造函数，还提供一些辅助函数，在之后会使用。

// 红黑树继承于二叉平衡搜索树，这里只列出红黑树特有的属性。
public class RBTree<E> extends BBST<E> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element, parent);
    }

    // 构造一个红黑节点，默认为红色
    private static class RBNode<E> extends Node<E> {
        boolean color = RED; //
        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }
    }

    // 节点染色
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return node;
        ((RBNode<E>)node).color = color;
        return node;
    }

    // 将节点染为红色
    private Node<E> red(Node<E> node) {
        return color(node, RED);
    }

    // 将节点染为黑色
    private Node<E> black(Node<E> node) {
        return color(node, BLACK);
    }

    // 节点的颜色
    private boolean colorOf(Node<E> node) {
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    // 是否为黑色节点
    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    // 是否为红色节点
    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    public boolean isLeftChild() {
        return parent != null && this == parent.left;
    }

    public boolean isRightChild() {
        return parent != null && this == parent.right;
    }

    // 获取兄弟节点   
    public Node<E> sibling() {
        if (isLeftChild()) {
            return parent.right;
        }

        if (isRightChild()) {
            return parent.left;
        }
        return null;
    }
}
复制代码

2、添加

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

image

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

2.1 parent为BLACK

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

image

2.2 parent为RED（Double Red）

• 这8种情况需要在添加之后修复红黑树。
• 其中前4种属于B树节点上溢的情况。

image

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

image

• 首先看52和60，这两种情况分别属于RR和LL。
• 判定条件：uncle不是RED。
• 操作步骤：
  1. parent染成BLACK，grand染成RED。
  2. grand进行单旋操作。

image

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

image

• 看48和74，这两种情况属于LR和RL。
• 判定条件：uncle不是RED。
• 操作步骤：
  1. 自己染成BLACK，grand染成RED。
  2. 进行双旋操作。
  3. 如果是LR，parent左旋转，grand右旋转。
  4. 如果是RL，parent右旋转，grand左旋转。

image

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

image

• 现在我们来添加10，10添加之后会导致上溢，这种情况属于LL。
• 判定条件：uncle是RED。
• 操作步骤：
  1. parent，uncle染成BLACK，成为独立节点。
  2. grand向上合并，染成RED，当作是新添加的节点进行处理。
  3. grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK。
• LL的情况不需要旋转，只需要染色。

image

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

image

• 判定条件：uncle是RED。
• 操作步骤：
  1. parent，uncle染成BLACK，成为独立节点。
  2. grand向上合并，染成RED，当作是新添加的节点进行处理。

image

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

image

• 判定条件：uncle是RED。
• 操作步骤：
  1. parent，uncle染成BLACK，成为独立节点。
  2. grand向上合并，染成RED，当作是新添加的节点进行处理。

image

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

image

• 判定条件：uncle是RED。
• 操作步骤：
  1. parent，uncle染成BLACK，成为独立节点。
  2. grand向上合并，染成RED，当作是新添加的节点进行处理。

image

2.3 添加总结

• 添加一共有12种情况。
• 其中有4种情况，添加之后父节点为黑色，添加之后不用做处理。依然满足性质4。
• 另外8种情况，添加之后父节点为红色，不满足性质4，需要进行双红修复处理。
• 修复分为两种情况：
  • uncle不是RED：
    • LL\RR，让祖父节点进行单旋转，染成红色，让父节点成为中心，并染成黑色。
    • LR\RL，让祖父节点和父节点进行旋转，让新添加成员成为中心节点，染成黑色，祖父节点染成红色。
  • uncle是RED：
    • 父节点，叔父节点染成黑色。
    • 祖父节点染成红色，并上溢。

2.4 添加实现

• rotateLeft，rotateRight函数实现请查看平衡二叉搜索树（AVL）

protected void afterAdd(Node<E> node) {
    Node<E> parent = node.parent;
    // 添加的是根节点 或者 上溢到达了根节点
    if (parent == null) {
        black(node);
        return;
    }
    // 如果父节点是黑色，直接返回
    if (isBlack(parent)) return;

    // 叔父节点
    Node<E> uncle = parent.sibling();
    // 祖父节点
    Node<E> grand = red(parent.parent);
    if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
        black(parent);
        black(uncle);
        // 把祖父节点当做是新添加的节点
        afterAdd(grand);
        return;
    }

    // 叔父节点不是红色
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            black(parent);
        } else { // LR
            black(node);
            rotateLeft(parent);
        }
        rotateRight(grand);
    } else { // R
        if (node.isLeftChild()) { // RL
            black(node);
            rotateRight(parent);
        } else { // RR
            black(parent);
        }
        rotateLeft(grand);
    }
}
复制代码

3、删除

• B树中，最后真正被删除的元素都在叶子节点上。

image

• 删除分为删除RED节点和删除BLACK节点两种情况。
• 删除RED节点，直接删除即可，不用做任何调整。

image

• 删除BLACK节点分为3种情况。
  • 拥有2个RED子节点的BLACK节点，例如25。
    • 不可能被直接删除，因为会找它的前驱或后继子节点替代删除，因此不用考虑这种情况。
  • 拥有1个RED子节点的BLACK节点，例如46，76。
  • BLACK叶子节点，例如88。

image

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

• 判定条件：删除指定节点后，用以代替的子节点是RED。
• 将替代的子节点染成BLACK即可保持红黑树的性质。
• 例如删除50和72。

image

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

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

3.2.1 sibling至少有1个RED子节点

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

image

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

image

3.2.2 sibling没有RED子节点

• 如果sibling没有1个RED子节点：
  • 将sibling染成RED，parent染成BLACK即可修复红黑树性质。

image

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

image

3.2.3 sibling为RED

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

image