红黑树

红黑树的引入

二叉搜索树（BST）

二叉搜索树（BST）具备以下特性（规则）：

1. 左子树上所有结点的值均小于或等于它的根结点的值。
2. 右子树上所有结点的值均大于或等于它的根结点的值。
3. 左、右子树也分别为二叉搜索树。

在BST中最大比较次数为树的高度，树的高度范围为 $[log(n), n]$。

当树中每个结点左、右子树高度大致相同时，树高为 $\text{log}(n)$ ，则平均查找长度与 $\text{log}(n)$ 成正比，查找的平均时间复杂度在 $O(\text{log}n)$ 数量级上。

当树形结构为一个单子树时，此时树高 $n$ ，则平均查找长度为 $(n+1)/2$ ，查找的平均时间复杂度在 $O(n)$ 数量级上。

相同序列构成的不同二叉搜索树：不同的二叉搜索树 - 力扣（LeetCode）

平衡二叉搜索树（AVL）

平衡二叉查找树的出现，主要是为了解决当二叉树查找树形态结构变成一个链条结构的时候，查找效率变低的问题，算法由Adel'son-Vel'skii和Landis发明，同时也称AVL树，特性（规则）如下：

1. 它的左子树和右子树都是平衡二叉树；

2. 且它的左子树和右子树的深度之差的绝对值（平衡因子 ） 不超过1。

AVL是严格平衡的BST（平衡因子不超过1）。查找过程与BST一样，只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好，最坏情况都是 $O(\text{log}n)$ 。

$$
balance\ factor = height\ of\ left\ subtree - height\ of\ right\ subtree \
bf = {-1, 0, 1} \
|bf| = |hl - hr| \le 1 \
$$

AVL 的旋转：

1. LL-imbalance：由于在左子树的左子树插入或删除而导致的不平衡，进行LL-Rotation；
2. LR-imbalance：由于在左子树的右子树插入或删除而导致的不平衡，进行LR-Rotation；
3. RR-imbalance：由于在右子树的右子树插入或删除而导致的不平衡，进行RR-Rotation；
4. RL-imbalance：由于在右子树的左子树插入或删除而导致的不平衡，进行RL-Rotation。

在插入、删除树节点的时候，AVL树会自动进行调整。也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。AVL在每次插入节点时对树进行检查和调整，AVL的旋转每次只涉及以imbalance节点为根节点的3个节点（如下图）：

以 LL-Rotation 和 LR-Rotation 为例（假设图中节点A为第一个 $|bf| \neq 1$ 的节点）：

给定节点数为 $n$ 的AVL树，最大高度为 $\text{log}(2n)$ ，而不是 $n$。

平衡二叉搜索树解决二叉搜索树的问题，保证了不会成为线性的链表。
左结点小于根节点，右结点大于根节点，并且还规定了左子树和右子树的高度差不得超过1。

但其仍然存在问题：

1. 由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。
2. 每一个节点只能存放一个元素，每个节点只有两个子节点，所以查找时，需要多次磁盘IO（如果数据存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。）

B 树

视频：10.2 B Trees and B+ Trees. How they are useful in Databases - YouTube

B 树的基本思想：多级索引

一个m阶的B树的规则：

1. 根结点至少有两个子树（1个索引）；
2. 每个中间节点都包含 $k-1$ 个元素和 $k$ 个孩子，其中 $m/2 \le k \le m$ ；
3. 每一个叶子节点都包含 $k-1$ 个元素，其中 $m/2 \le k \le m$ ；
4. 所有的叶子结点都位于同一层；
5. 每个节点中的元素从小到大排列，节点当中 $k-1$ 个元素正好是 $k$ 个孩子包含的元素的值域分划。

4阶B树，例子：

2-3-4 树

2-3-4 树 是 四阶 B树，它是一种多路查找树，其结构有以下限制：

1. 所有叶子节点具有相同的深度；
2. 节点只能是2-节点、3-节点和4-节点之一：
   • 2-节点：包含1个元素的节点，有2个子树；
   • 3-节点：包含2个元素的节点，有3个子树；
   • 4-节点：包含3个元素的节点，有4个子树。
3. 所有节点必须至少包含一个元素；
4. 元素始终保持排序顺序 ，整体上保持二叉搜索树的性质，即父节点的值大于左子树所有节点，小于右子树所有节点；
5. 节点有多个元素时，每个元素必须大于它左边的和左子树中的元素。

例：

2-3-4树的实现在一些编程语言中较为困难，一般使用其等同的红黑树。

红黑树

视频：【完整版】最全最新红黑树讲解，数组、链表、二叉树、AVL树、红黑树哔哩哔哩_bilibili

2-3-4 树和红黑树的等价关系

2-3-4 树和红黑树的等价关系：

1. 2-节点对应RB-Tree黑节点；

2. 3-节点对应RB-Tree上黑下红（分为左倾和右倾两种）；

3. 4-节点对应RB-Tree上黑下红。

2-3-4 树到红黑树的转换：

平衡二叉查找树通过严格平衡策略，以牺牲建立查找结构的代价换来了稳定的查找时间复杂度。但是相对来说，在删除方面，时间复杂度稍大。而红黑树不严格控制左、右子树高度或节点数之差小于等于1。

红黑树的特点

红黑树是自平衡（不严格限制）的二叉搜索树， 红黑树的5条规则：

1. 节点要么是黑色要么是红色；
2. 根节点是黑色；
3. 每个叶子节点都是黑色的空节点（NIL节点）；
4. 每个红色节点的两个子节点都是黑色（也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点）；
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其他路径长出2倍，因而，红黑树是相对的接近平衡的二叉树，但是相比平衡二叉树而言，尤其是删除的时间复杂度，有所降低）。

分析：

1. 第2条特性：从 2-3-4 树到红黑树的转换中，根节点要么是2-节点（黑色），要么是3-节点或4-节点分裂出的（上黑）；
2. 第5条特性：从 2-3-4 树到红黑树的转换中，可以看出2-3-4 树的每个节点中有且仅有一个黑色元素，由于B树中所有的叶子结点都位于同一层，所以从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（2-3-4树的高度+1）。

红黑树在查找方面和AVL树操作几乎相同。牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。任何不平衡都会在三次旋转之内解决。
确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证 $O(\text{log}n)$ 。

红黑树的通过旋转和染色来自平衡。

红黑树的查找

红黑树的查找与二叉树搜索树的查找一样。

红黑树的插入

参考资料：红黑树的原理 (插入+ 删除) 案例分析 - 知乎 (zhihu.com)

向红黑树中插入新的结点。具体做法是：

1. 将新结点的 color 赋为红色，然后以二叉排序树的插入方法插入到红黑树中去。之所以将新插入的结点的颜色赋为红色，是因为：如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这个是很难调整的。
2. 通过颜色调换和树旋转来调整可能会出现两个连续红色节点的冲突。

插入不同的情况：

1. 插入根节点；
2. 插入节点的父节点为黑色；
3. 插入节点的父节点为红色，叔节点也为红色；
4. 插入节点的父节点是红色，叔节点是黑色：
   1. 左左插入
   2. 左右插入
   3. 右右插入
   4. 右左插入

具体操作：

1. 插入根结点：直接染黑。

2. 插入节点的父节点为黑色，没有出现两个连续红色节点的冲突，不需要调整。

3. 插入节点的父节点为红色，叔节点也为红色，不需要旋转，直接染色，注意递归向上调整。

   分析：插入N之前，N所在的位置必为NIL，由于插入之前也是一棵 RB-Tree，则 B 节点必为 NIL。插入新节点之后树仍是平衡的，所以不需要旋转。

4. 插入节点的父节点是红色，叔节点是黑色:

   1. 左左插入，左旋

      分析：插入N之前，N所在的位置为NIL，由于插入之前也是一棵 RB-Tree，则 B 节点与 U 节点必为 NIL。插入新节点之后树为LL-imbalance，需要进行LL-Rotation。

      

   2. 左右插入

      分析：插入N之前，N所在的位置为NIL，由于插入之前也是一棵 RB-Tree，则 B 节点与 U 节点必为 NIL。插入新节点之后树为LR-imbalance，需要进行LR-Rotation。

      

   3. 右右插入

      分析：插入N之前，N所在的位置为NIL，由于插入之前也是一棵 RB-Tree，则 B 节点与 U 节点必为 NIL。插入新节点之后树为RR-imbalance，需要进行RR-Rotation。

      

   4. 右左插入

      分析：插入N之前，N所在的位置为NIL，由于插入之前也是一棵 RB-Tree，则 B 节点与 U 节点必为 NIL。插入新节点之后树为RL-imbalance，需要进行RL-Rotation。

      

总结：根据平衡二叉树正常插入节点之后根据平衡判断是否需要旋转，若不需要旋转，则将 Parent 和 Uncle 染黑，GrandParent 染红，再递归向上调整；若不平衡，则根据情况进行旋转，旋转之后上黑（新的 GrandParent ）下红染色。

红黑树的删除

参考：红黑树删除_bilibili

删除不同的情况：

1. 删除叶节点，且叶节点为红色，无需调整；
2. 删除叶节点，叶节点为黑色，需要调整；
3. 删除节点非叶节点，若该节点只有一个子节点，则用该子节点替代删除节点；若该节点有两个子节点，则将要删除的节点与其前驱或者后继节点进行替代。此时情况变为1或2（根据实际被删除的节点的颜色决定）。

情况2若删除后不平衡则需要根据AVL旋转规则旋转后染色，否则直接染色。

如果不旋转，则将兄弟节点设置为红色，将父节点设置为当前节点递归，直到根节点，或遇到红色节点；如果旋转，则旋转之后 Parent 位置的颜色不变，其他位置根据黑色节点个数进行调整。