数据结构与算法——红黑树(下)

心已赠人 2022-11-17 13:50 201阅读 0赞

### 文章目录 ###

*  实现红黑树的基本思想
 *   *  基本操作
 *  插入操作的平衡调整
 *   *  CASE1
     *  CASE2
     *  CASE3
 *  附地址

# 实现红黑树的基本思想 #

不知道你有没有玩过魔方？其实魔方的复原解法是有固定算法的：遇到哪几面是什么样子，对应就怎么转几下。你只要跟着这个复原步骤，就肯定能将魔方复原。

实际上，红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。还记得我们前面讲过的红黑树的定义吗？今天的内容里，我们会频繁用到它，所以，我们现在再来回顾一下。  
一棵合格的红黑树需要满足这样几个要求：

*  根节点是黑色的；
 *  每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
 *  任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
 *  每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

在插入、删除节点的过程中，第三、第四点要求可能会被破坏，而我们今天要讲的“平衡调整”，实际上就是要把被破坏的第三、第四点恢复过来。

## 基本操作 ##

在正式开始之前，我先介绍两个非常重要的操作，左旋（rotate left）、右旋（rotate right）。左旋全称其实是叫围绕某个节点的左旋，那右旋的全称估计你已经猜到了，就叫围绕某个节点的右旋。

我们下面的平衡调整中，会一直用到这两个操作，所以我这里画了个示意图，帮助你彻底理解这两个操作。图中的a，b，r表示子树，可以为空。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70]  
**左旋**  
上升的节点有两个左分支，剪断一个原来的左分支，补到下沉节点的右分支上

**右旋**  
上升的节点有两个右分支，剪断一个原来的右分支，补到下沉节点的左分支上

前面我说了，红黑树的插入、删除操作会破坏红黑树的定义，具体来说就是会破坏红黑树的平衡，所以，我们现在就来看下，红黑树在插入、删除数据之后，如何调整平衡，继续当一棵合格的红黑树的。

# 插入操作的平衡调整 #

首先，我们来看插入操作。  
`红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上`。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

*  如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
 *  如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：`左右旋转`和`改变颜色`。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作`关注节点`。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。

我们下面依次来看每种情况的调整过程。提醒你注意下，`为了简化描述，我把父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点`。

## CASE1 ##

CASE 1：如果关注节点是a，它的叔叔节点d是红色，我们就依次执行下面的操作：

*  将关注节点a的父节点b、叔叔节点d的颜色都设置成黑色；
 *  将关注节点a的祖父节点c的颜色设置成红色；
 *  关注节点变成a的祖父节点c；
 *  跳到CASE 2或者CASE 3。

![在这里插入图片描述][c98dcc9054e56f0b02e770845afbf4b2.png_pic_center]

## CASE2 ##

CASE 2：如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的右子节点，我们就依次执行下面的操作：

*  关注节点变成节点a的父节点b；
 *  围绕新的关注节点 b左旋；
 *  跳到CASE 3。

![在这里插入图片描述][e62615e7785ec8b3ca3865dd49ff7a62.png_pic_center]

## CASE3 ##

CASE 3：如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的左子节点，我们就依次执行下面的操作：

*  围绕关注节点a的祖父节点c右旋；
 *  将关注节点a的父节点b、兄弟节点c的颜色互换。
 *  调整结束。

![在这里插入图片描述][5122e4ef2d9776541593a9ab8c57feaf.png_pic_center]

# 附地址 #

[清晰理解红黑树的演变—红黑的含义][Link 1]  
[234树][234]  
[仓库地址][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70]: /images/20221022/113c2f2c328c4025971f0e69ccdb8cea.png
[c98dcc9054e56f0b02e770845afbf4b2.png_pic_center]: /images/20221022/0ceeb19a219344f7b26da8f8e494a52c.png
[e62615e7785ec8b3ca3865dd49ff7a62.png_pic_center]: /images/20221022/ae3835cabb3f4daaae87e19367090832.png
[5122e4ef2d9776541593a9ab8c57feaf.png_pic_center]: /images/20221022/0700380beac1418db1437453616e1084.png
[Link 1]: https://blog.csdn.net/chen_zhang_yu/article/details/52415077
[234]: https://zhuanlan.zhihu.com/p/104031183
[Link 2]: https://github.com/wangzheng0822/algo