红黑树 · 翼仔的博客

自顶向下的 2-3-4 树链接到标题

插入结点链接到标题

2-3-4 树的插入算法，简而言之，就是在往下查找应该将待插入的 new_key 插入到何处的时候，一旦碰到 4- 结点，就将 4- 结点中间的 key 上溢，剩下的两个 key 作为两个 2- 结点，这个上溢的过程也是递归的，可以理解为向原先 4- 结点的父结点插入 4- 结点中间的这个 key，4- 结点剩下的部分作为两个 2- 结点。我们的这个分解算法，保证了4- 结点的父结点不会是 4- 结点。（这里可以用数学归纳法给出证明）

这样处理到最后，我们的 new_key 要插入的结点一定是 2- 结点或者 3- 结点，因此，我们可以直接插入。

要实现这个插入算法，我们需要：

将 4- 结点表示为由三个 2- 结点组成的一个平衡的子树，根结点和两个子结点都用 red link 连接；
在向下的过程中分解所有 4- 结点并进行颜色转换；
和插入操作一样，在向上的过程中用旋转将 4- 结点配平；

但实际上，我们只要移动 put 方法中的三行代码就能由 2-3 树对应的红黑树操作转移到 2-3-4 树对应的红黑树操作；即将 FlipColors 语句（以及 if 判断）移动到 nullptr 测试之后，递归调用之前，如下：

void Put(int key, int val) {
    root_ = Put(key, val, root_);
    root_->color_ = kBlack; // 根结点的颜色一定是黑色！
}
auto Put(int key, int val, Node *h) -> Node * { // h 表示我们往以 h 为根结点的树中插入结点
    if (h == nullptr) {
        return new Node(key, val, 1, kRed);
    }
    if (isRed(h->left_) && isRed(h->right_)) {
        // 左右子结点都是红色，翻转颜色
        // 即碰到 4- 结点就分解成两个 2- 结点
        FlipColors(h);
    }
    if (key < h->key_) {
        h->left_ = Put(key, val, h->left_);
    } else if (key > h->key_) {
        h->right_ = Put(key, val, h->right_);
    } else {
        h->val_ = val;
    }

    if (!isRed(h->left_) && isRed(h->right_)) {
        // 只有右子结点是红色
        h = RotateLeft(h);
    }
    if (isRed(h->left_) && isRed(h->left_->left_)) {
        // 左子结点和左子结点的左子结点都是红色
        h = RotateRight(h->right_);
    }
    h->cnt_ = h->left_->cnt_ + h->right_->cnt_ + 1;
    return h;
}

红黑树链接到标题

性质链接到标题

红黑树可以说是由 2-3-4 树衍生而来，一棵合法的红黑树必须遵循以下四条性质：

结点为红色或者黑色；
null 结点（叶子结点的子结点）为黑色；
红色结点的子结点为黑色（即不存在两个连续的红色结点）；
从根结点到 null 结点的每条路径上的黑色结点相同；
根结点一定是黑色；
- 这条性质要求完成插入操作后若根节点为红色则将其染黑，但由于将根节点染黑的操作也可以延迟至删除操作时进行，因此，该条性质并非必须满足。

红黑树的这几条性质从 2-3-4树的角度是很好理解的：红黑树的黑色结点和它的红色子结点构成了 2-3-4 树中的 3- 结点或者 4- 结点，如果黑色结点的两个子结点都是黑色结点，那么该结点对应 2-3-4 树中的 2- 结点。

7SRAMLndBOgvTpH

红黑树中黑色结点的个数 = 2-3-4 树的结点数。

插入结点链接到标题

红黑树的插入过程还是可以从上述的 2-3-4 树去理解，首先，我们必定是把要插入的结点先标记为红色，这样有不小可能不会影响红黑树对应的 2-3-4 树的平衡。

case 1. 如果要插入的结点是作为根结点的，那么我们将它染为黑色；
case 2. 如果要插入的结点是作为 3- 结点的子结点：
- case 2.1. 作为黑色结点的子结点插入，那么不会破坏红黑树的平衡性，直接插入即可；
- case 2.2. 如果作为红色结点的子结点插入，即父结点是红色，祖父结点是黑色，并且祖父结点只有一个红色子结点，那么，又可以分为 LL 型、LR 型、RL 型、 RR 型；
  - 类似 AVL 树，LL 型需要一次右旋，RR 型需要一次左旋，LR 型需要一次左旋（对 h->left_），一次右旋（对 h），RL 型需要一次右旋（对 h->right_），然后一次左旋（对 h）
case 3. 如果要插入的结点是作为 4- 结点的子结点，即父结点是红色结点，祖父结点是黑色结点，并且祖父结点有两个红色子结点；
- 整体上来说，是需要做一个 FlipColors 的操作，即将祖父结点、祖父结点的两个子结点这三个结点的颜色翻转，翻转之后，相当于祖父结点的祖父结点被插入了一个红色结点，因此，可以再次转换到 case 1 或者 case 2 或者 case 3，通过递归操作进行处理。

删除结点链接到标题

红黑树的删除过程还是可以从 2-3-4 树去理解。B 树中如果要删除结点，那么都是转换成对它的前驱或者后继结点的删除，即将待删除结点的 h 的 key-value 修改为它的前驱或者后继结点的 key-value。

因此，我们只需要讨论叶子结点就好了，并且我们只讨论后继结点。这里的叶子结点，是指存在子结点为 null 结点的结点。

如果当前结点没有后继结点，那么对当前结点执行右旋即可。

那么，对叶子结点的删除，可以分为对红色结点的删除和对黑色结点的删除两种情况：

删除红色叶子结点 h，可以直接删除，不影响平衡；

删除黑色叶子结点 h：（作为后继结点的 h 不会存在黑色子结点）

case 1. 有两个红色子结点的黑色结点，与后继结点的定义矛盾，转换为 case 1；
case 2. 有一个红色子结点的黑色结点（另一个子结点是 null 结点）；
- case 2.1. 如果右子结点是红色，对 h 执行左旋，然后删除 h；
- case 2.2. 如果左子结点是红色，对 h 执行右旋，然后删除 h；
- case 2.3. 如果 h 是黑色结点并且没有红色子结点：
  - a. h 是根结点，那么直接删除；
  - b. h 的兄弟结点是黑色；
    - 1）兄弟结点有红色子结点，删除之后对 h 的父结点进行旋转操作，即可满足平衡；（其实也有 LL，LR，RL，RR）的区分；
    - 2）兄弟结点没有红色子结点，如果父结点是红色，这个好处理，父结点向下与 h 的兄弟结点合并成一个 3- 结点；否则就需要执行递归下溢。
  - c. h 的兄弟结点是红色；对父结点进行旋转，使它变成兄弟结点是黑色，父结点是红色的情况。