红黑树

系统管理员 2020-11-29 04:30 842阅读 0赞

# 1. 从 2-3 树说起 #

一棵标准的 BST （二叉查找树 / 二叉搜索树）是长这个样子的：  
![BST][]  
其中，这棵二叉查找树中的每个结点也叫 2-结点 ，2-结点 就表示树中的每一个结点含有一个值和两条边，如下：  
![2 结点][2] ![3 结点][3]  
由此，引入 3-结点，3-结点 就表示树中的每一个结点含有两个值和三条边（如上）

2-3 树在二分查找树的基础上多了一种 3-结点 ，树中的结点可以存放 1 个元素（2 个孩子），还可以存放 2 个元素（3 个孩子，此时，左孩子的值 ＜ b，中间孩子的值介于 b 和 c 之间，右孩子的值是 ＞ c 的，如上面右图所示），这就是 2-3 树名称的由来。可以看出，除了多了一种结点，2-3 树也是满足二分查找树的基本性质的。  
![2-3 树][2-3]  
**2-3 树是一个完全平衡的树**，也就是说，2-3 树从根结点到任意一个叶子结点的距离（所经过的结点数量）一定是相同的（如上图所示）。

下面简单看下 2-3 树的查找、插入（结点）。

## 1.1 查找 ##

与二叉查找树的查找思路是一样的，当查找某一个值 a 时：

*  先将 a 与根结点比较，如果相等，则返回；
 *  如果 a ＜ 父结点的值，在其指向的左子树中继续查找；
 *  如果 a ＞ 父结点的值，在其指向的右子树中继续查找；
 *  一直指向到最后的空结点，这时返回为空。

如果查找到了 3-结点 ：

*  如果 a ＜ 3-结点 的左值，则在 3-结点 的左子树中继续查找；
 *  如果 a ＞ 3-结点 的右值，则在 3-结点 的右子树中继续查找；
 *  如果 a 介于 3-结点 左右两个值之间，则在 3-结点 的中间子树中继续查找。

## 1.2 插入 ##

前面提到 2-3 树满足二叉查找树的基本性质，并且是一种绝对平衡的二叉树，那么，在添加结点的时候，必定也是以维持其绝对平衡性来执行添加操作的。

由于 2-3 树既包含 2-结点，也包含 3-结点，据此，大致可以分为两种情况讨论：

### 1.2.1 如果向 2-结点 中插入新值 ###

![向 2-结点 中插入新值][2-_]

### 1.2.2 如果向 3-结点 中插入新值 ###

![向 3-结点 中插入新值][3-_]  
这个例子中的 2-3 树是从根结点开始“生长”的，再往下“繁衍”，又不可避免的会遇到下面这两种情景：

#### 1.2.2.1 向一个父结点为 2-结点 的 3-结点 中插入新值 ####

![向一个父结点为 2-结点 的 3-结点 中插入新值][2-_ _ 3-_]

#### 1.2.2.2 向一个父结点为 3-结点 的 3-结点 中插入新值 ####

![向一个父结点为 3-结点 的 3-结点 中插入新值][3-_ _ 3-_]

### 1.2.3 小结 ###

*  插入思路和二分查找树类似，小于时，放在左边，大于时，放在右边。
 *  往 2-3 树中插入元素时，不会像二分查找树那样直接新建一棵子树来放置被插入的元素，而总是在插入位置进行结点融合，使 2-结点 上升为 3-结点。
 *  插入时，始终以维持 绝对平衡 为目的，来进行结点的融合（2-结点 上升为 3-结点、暂存为 4-结点）、4-结点 拆分（成新的 2-3 子树）。

# 2. “红”与“黑” #

## 2.1 从 2-3 树到红黑树 ##

![从 2-3 树到红黑树][2-3 1]  
黑色的结点 其实还是一个 2-结点，红色的结点 就表示它与它的父亲结点在原来的 2-3 树中是一个 3-结点 ，替换掉了 2-3 树中的 3-结点，这就是 红黑树 。

另外，从上图中 3-结点 变成 红色结点的过程，在原来的 2-3 树的 3- 结点中，左边的值是 ＜ 右边的值的（b ＜ c），对应成红黑树后，3-结点中的左边（b）变成了红色结点，右边（c）变成了红色结点的父结点。因此，可以看出，**3-结点中的左边都是红色结点**， 在红黑树中，**所有的红色结点都是左倾斜的。**

据此，在 1小节 中的那棵 2-3 树 所对应的 红黑树，就应该是这个样子的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vbm9ub2tlMTEx_size_16_color_FFFFFF_t_70]

## 2.2 红黑树的性质 ##

红黑树总是等价于 2-3 树的。  
结合 2-3 树 再来看红黑树的性质，可能会更加清晰：

*  **每个结点或者是红色的，或者是黑色的。**
 *  **根结点总是黑色的。**
    
     *  在 2-3 树中，根结点要么是 2-结点，要么是 3-结点。如 2.1 小节中的图示：
     *  如果是 2-结点，毫无疑问，它是黑色结点。
     *  如果是 3-结点，那么 3-结点中的左边元素是红色结点，右边元素是黑色结点，左边元素 < 右边元素，因此右边的元素是根结点，它是黑色的。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vbm9ub2tlMTEx_size_16_color_FFFFFF_t_70 1]
 *  **每一个叶子结点（最后的空结点，而不是左右子树都为空的那个结点）是黑色的。**
    
     *  它说明，在红黑树中，一个空结点是黑色的。
     *  根据上条性质：根结点总是黑色的——那么一棵为空的红黑树的根结点（空结点），自然也应该是黑色的。
 *  **如果一个结点是红色的，那么它的孩子结点都是黑色的。**
    
     *  在红黑树中的红色结点，是由原来的 2-3 树中的 3-结点中 左边的元素 而来的。
     *  而这个 左边元素 的孩子结点 就是原来的 2-3 树中的 左孩子 和 中间孩子。
     *  不管是 左孩子 还是 中间孩子，它要么是 2-结点，要么是 3-结点。
     *  和 第 2 条性质的推导一样，参考第 2 条性质中的图示。如果是 2-结点，那么红色结点连接的一点是黑色结点；如果是 3-结点，那么红色结点一定是先连接黑色节点的。
     *  *由这条性质，还可以推导出：如果一个结点是黑色的，那么它的右孩子一定是黑色的。*
 *  **从任意一个结点到叶子结点，经过的黑色结点的数目是一样的。**
    
     *  由于 2-3 树是一棵绝对平衡的树，即，2-3 树中从任一结点出发到任意一个叶子结点的深度（所经过的结点数目）一定是相同的。
     *  而 2-3 树中，只有两种结点： 2-结点 和 3-结点，转化成红黑树后，这两种结点都一定会包含一个黑色结点。
     *  因此，红黑树中的 每一个黑色结点 就象征着原来 2-3 树中 一个2-结点 或 一个3-结点。
     *  在 2-3 树中，是任一结点出发到叶子结点所经过的 结点数目 是相同的，那么，对应在红黑树中，就变成了：任一结点出发到叶子结点所经过的 黑色结点数目 是相同的 —— 有人称，红黑树是保持“黑平衡”的的二叉树（红黑树不是绝对平衡的树，它的最大高度是 2logn）。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vbm9ub2tlMTEx_size_16_color_FFFFFF_t_70 2]

# 更新记录 #

无

喜欢就点个赞呗~~(\*/ω＼\*)

[BST]: /images/1606624224906.png
[2]: /images/1606624213366.png
[3]: /images/1606624180224.png
[2-3]: /images/1606624166441.png
[2-_]: /images/1606624152642.png
[3-_]: /images/1606624140361.png
[2-_ _ 3-_]: /images/1606624126564.png
[3-_ _ 3-_]: /images/1606624112479.png
[2-3 1]: /images/1606624099986.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vbm9ub2tlMTEx_size_16_color_FFFFFF_t_70]: /images/1606624085314.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vbm9ub2tlMTEx_size_16_color_FFFFFF_t_70 1]: /images/1606624071738.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vbm9ub2tlMTEx_size_16_color_FFFFFF_t_70 2]: /images/1606624047283.png