红黑树

Dear 丶 2022-12-13 04:18 36阅读 0赞

# 红黑树的定义 #

*  每个节点要么是红色，要么是黑色。
 *  根节点必须是黑色， 每个叶子节点是黑色（叶子节点包含NULL）。
 *  红色节点不能连续（红色节点的孩子和父亲都不能都是红色）
 *  如果一个节点是红色的，则它的子节点必须是黑色的
 *  从任意节点出发，到其所有叶子节点的简单路径上都包含相同数目的黑色节点.

# 平衡二叉查找树 #

我们以这样一个数组为例 \[42，37，18，12，11，6，5\] 构建一棵二叉搜索树，由于数组中任意一点都可以作为二叉搜索树的根节点，因此这棵二叉搜索树并不唯一，我们来看一个极端的例子（以42作为根节点，顺序插入元素）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]  
在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。

为了让二叉搜索树不至于太“倾斜”，我们需要构建一棵**平衡二叉搜索树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]  
可以看出，平衡二叉搜索树的搜索时间复杂度为O(logn)，避免了因为随机选取根节点构建二叉搜索树而可能造成的退化成链表的情况。下面再抄一段平衡二叉搜索树的官方定义：

平衡二叉查找树：简称平衡二叉树。是由前苏联的数学家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：

性质1. 可以是空树。

性质2 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1

[详解什么是平衡二叉树（AVL）][AVL]

# 2-3树 #

经过上面的例子，我们可以知道，**构建一颗平衡二叉搜索树的关键在于选取“正确”的根节点**， 那么我们如何在每次构建平衡二叉搜索树的时候都能选取合适的根节点呢？这里就要另一种重要的树：2-3树（读作二三树），2-3树和红黑树是等价的，理解2-3树对理解红黑树以及B类树都有很大的帮助。

[2-3平衡树与B树的详细探讨][2-3_B]

# 红黑树 #

## 2-3树与红黑树的转换 ##

既然2-3树已经能够保持自平衡，为什么我们还需要一颗红黑树呢？这是因为:

*  **2-3树这种每个节点存储1-2个元素以及拆分节点向上融合的性质不便于代码操作**，

因此我们希望通过一些规则，将2-3树转换成二叉树，而且转换后的二叉树依然能够保持平衡。

**红黑树实际上就是2-3树的二分搜索树表示**，其中红节点于其父节点组合形成3节点，没有红色孩子节点的节点就是2节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]

例如这颗红黑树中，这个红色的节点与其父节点（元素11所在的节点）组成一个3节点，这颗红黑树等价于以下的2-3树  
![在这里插入图片描述][20201020084616554.png_pic_center]

总结：我们怎么将2-3树转换为红黑树

*  对于2节点，可以直接转换为红黑树中的一个黑节点
 *  对于3节点：
    
     *  将3节点拆开，成为一棵树，并且3节点的左元素作为又元素的子树
     *  将原来的左元素标记为红色（表示红色节点于其父节点在2-3树种曾经是平衡关系）  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]  
        推论：由于红色节点是由3节点拆分而来，因此所有的红色节点只会出现在左子树上。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]

## 红黑树的性质 ##

*  每个节点要么是红色，要么是黑色
 *  根节点是黑色

> 根节点要么对应2-3树的2-节点或者3-节点，而这两者的根节点都是黑色的，因而根节点必然是黑色。从上图2-3树节点和红黑树节点对应关系就能很容易看出来

*  每个叶子节点是黑色

> 注意，这里的叶子是指的为空的叶子节点  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 5]

*  如果一个节点是红色的，那么它的子节点必须是黑色的

> 由于红黑树的每个节点都由2-3树转换而来，红色节点连接的节点必然是一个2-节点或者3-节点，而无论是2-节点还是3-节点，其根节点都是黑色的，因此红色节点的子节点必然是黑色的

[红黑树][Link 1]  
[面经手册 · 第6篇《带着面试题学习红黑树操作原理，解析什么时候染色、怎么进行旋转、与2-3树有什么关联》][_ _6_2-3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d560081d830848ed8e5eee626b62546e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/2d462a7126e54290b149eba42d6a2036.png
[AVL]: https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484608&idx=1&sn=68b96e6e65a048da54177b6e95b02676&chksm=fa0e6b41cd79e257daa1f276e0921ed4a060c9caf964e4131f68010ae2a9b8211f56af866fed&scene=21#wechat_redirect
[2-3_B]: https://blog.csdn.net/zhizhengguan/article/details/108987419
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/91aa83bb457847db9612fb10a3092084.png
[20201020084616554.png_pic_center]: /images/20221123/a09bb114194f4b399293c39d9e5cc6ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/1d0a31a299f84ebe8fb63aeb145fdf6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/da86b964f1374b25850f4a5d98b5da80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/e6436ee6f86a49ee8b68b6f60002190b.png
[Link 1]: https://blog.csdn.net/qq_25940921/article/details/82184055#comments_13437100
[_ _6_2-3]: https://blog.csdn.net/generalfu/article/details/108137335