# 红黑树


## 自顶向下的 2-3-4 树

### 插入结点

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

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065747.png)

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

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

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

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

```cpp
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](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065749.jpg)

红黑树中**黑色结点**的个数 = **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` 的兄弟结点是红色；对父结点进行旋转，使它变成兄弟结点是黑色，父结点是红色的情况。


## 总结

这个基于 2-3-4 树的红黑树手写实现，后面有空再写吧。。。主要是联系 2-3-4 树，来思考红黑树的插入与删除操作的平衡调整的本质。

## 参考

[红黑树 - OI Wiki](https://oi-wiki.org/ds/rbtree/)

[【喵的算法课】红黑树 删除【12期】](https://www.bilibili.com/video/BV1Ce4y1Q76H/)