红黑树从零开始理解

末蓝、 2023-09-26 09:52 94阅读 0赞

作者简介：本人三本院校菜鸡一枚，毕业之后发现对于很多基础都掌握的不牢固，特此，在这里进行一下复习加反思，如果有不对的地方，欢迎大家批评指正！注意，这里不涉及代码，只是简单地利用例子进行讲解，更加直观、简洁、针对性！

在学习红黑树之前，你首先要了解一下二叉搜索树和二叉平衡树，因为红黑树主要是以这两棵树为基础的！！

## **（1）二叉搜索树：** ##

什么是二叉搜索树，其实他的定义很简单，直白点说，对于二叉树的每个节点的左孩子都要小于父节点，对于每个节点的右孩子则要大于该父节点，当所有的节点满足这一要求的时候，我们就称呼这可二叉树为二叉搜索树！

![cef652794705499382fa3f4770a2eaa6.jpeg][]

## **（2）二叉平衡树：** ##

简单点来说二叉平衡树就是在二叉搜索树的基础上要求 任何一个节点的左孩子的高度与右孩子的高度的绝对值之差不得大于1。

因此他需要满足两个条件：

（1）这棵树是一个二叉搜索树

（2）树中的每个节点的左孩子与右孩子高度之差的绝对值不得大于1

![09495fe2a7754523b6f9a76d593ce610.jpeg][]

其实在这里除了要了解一下二叉平衡树的基础概念，更重要的是了解二叉平衡树的调整方式-----所谓的调整方式即通过每增加一个新的节点，当他不满足二叉平衡树的定义规则后，我们可以通过调整节点的位置，使其再度成为一个二叉平衡树。因为其实在红黑树中的调整方式与平衡二叉树的调整方式其实是类似的！

**其实在这里的调整方式总共分为四类：LL、LR、RR、RL**

**在这里主要给大家举个例子：**

![09a13c96c74e433dada1a5a2cdf21bfb.jpeg][]

![ef785911e3424299b0d1e003f484dcff.jpeg][]

（3）红黑树

**首先我想先强调一点：红黑树不是严格意义上的一个二叉平衡树，因为他可能不满足每个节点的左孩子与右孩子高度之差的绝对值小于1，但是一定是一棵二叉搜索树！**

首先我们必须明确的关于红黑树几个**重要性质**：

（1）红黑树中的每个节点都是带颜色的，但是只有两宗颜色，不是红色，就是黑色！

（2）红黑树的根节点必须是黑色！

（3）红黑树的叶子节点一定是黑色，且不能存储数据，也就是相当于为空的黑色叶子节点！

（4）红黑树每个节点到叶子节点所经过的黑色节点数目是相同的！

（5）如果一个结点为红色，那么他的孩子结点不可再为红色结点！

因此满足上述需求的一颗二叉搜索树，我们称之为红黑树！

在这里我只简单介绍一下，关于红黑树是如何通过不断调整自身方式保持一颗红黑树！

**首先你要知道，每插入一个结点，这个结点的默认颜色为红色。**

（1）当第一个结点插入时，因为没有根节点，而我们规定红黑树的根节点必须为黑色，因此，改变该节点的颜色为黑色。

![b6551c8e8dde423c8f98c5b402f94a32.jpeg][]

（2）当插入结点时，如果该节点父节点为黑色节点，那么直接插入。

![d81af1cb68794d35af028c273e0d13b6.jpeg][]

（3）当插入的结点的父节点为红色结点时则要分为两种情况：

**第一种情况：**当插入结点的父节点和父节点的兄弟节点都为红色时，那么改变其父节点和父节点兄弟节点的颜色，然后在改变父节点的父亲的颜色，依次递归，直到根节点结束为止！

![fb39f9fa69bd43e4b86884af3b2e48ec.jpeg][]

（但是这里有人可能会有疑惑，按照之前的规则，那么爷爷结点的兄弟结点需要改变颜色吗，答案是不需要，周星星要改变爷爷结点的颜色，大家可以自己试一下，在这里给大家举个例子，大家就明白了）大家可以看出8和11这两个结点，只有8改变颜色了，而11并没有改变颜色，在这里我们也看出来了，他并不属于严格意义上的二叉平衡树！

![348caa416c24490e8f26cfd6953f77f6.jpeg][]

**第二种情况：当插入结点的父节点的兄弟结点为黑色或者是为黑色叶子节点时，又分为四种情况**

**（1）第一种情况：当插入结点的父节点为爷爷结点的右孩子结点，并且父节点的兄弟结点为黑色节点或者为空（黑色叶子结点）时，并且插入的节点为父节点的右孩子：**

此时我们需要进行RR旋转，然后父节点与左孩子节点交换颜色：

![8b7cc9b978e14ec382dadc8d9c1eaed6.jpeg][]

**（2）第二种情况：当插入结点的父节点为爷爷结点的右孩子结点，并且父节点的兄弟结点为黑色节点或者为空（黑色叶子结点）时，且插入的节点为父节点的左孩子：**

此时我们需要进行RL旋转，在进行RR旋转，然后父节点与左孩子节点交换颜色：

![714455b9bbeb424e8e8565d065355ff0.jpeg][]

**（3）第三种情况：当插入结点的父节点为爷爷结点的左孩子结点，并且父节点的兄弟结点为黑色节点或者为空（黑色叶子结点）时，且插入的节点为父节点的左孩子：**

此时我们需要进行LL旋转，然后父节点与右孩子节点交换颜色：

![49c70868b16749b2b81ea1ab14bc700a.jpeg][]

**（4）第四种情况：当插入结点的父节点为爷爷结点的左孩子结点，并且父节点的兄弟结点为黑色节点护着为空（黑色叶子结点）时，并且插入的节点为父节点的右孩子：**

此时我们需要进行LR旋转，在进行LL旋转，然后父节点与右孩子节点交换颜色：

![aae6d612b729475da9d8ba4667e18db0.jpeg][]

其实在这里看出来了对于红黑树的变换方式与二叉平衡树的变换方式异曲同工之妙！只不过多加了一个变颜色的操作！

大家可以仿照这个帖子上的例子自己构建一颗红黑树，加深理解，强化印象！！

[红黑树系列1——红黑树的建立\_王Bob的博客-CSDN博客\_红黑树构建过程][1_Bob_-CSDN]

而红黑树的删除操作我就不在这里叙述了，大家有空可以去看看其他的帖子，其实原理也不难!

我感觉自己写的已经非常详细了，大家看完这些，应该已经到达入门水平了！

以后有时间再写一篇他和二叉平衡树的区别，比如在没有过多删除和增加操作的情况下，我们优先选择二叉平衡树作为存储结构，但是牵扯到有频繁的删除和添加操作，我们则优先选择红黑树作为存储结构，大家可以想一下原因：红黑树并不是一棵严格意义上的二叉平衡树！！

![866c7d672e4f30e14c73f9b7a2133883.jpeg][]

[cef652794705499382fa3f4770a2eaa6.jpeg]: https://img-blog.csdnimg.cn/cef652794705499382fa3f4770a2eaa6.jpeg
[09495fe2a7754523b6f9a76d593ce610.jpeg]: https://img-blog.csdnimg.cn/09495fe2a7754523b6f9a76d593ce610.jpeg
[09a13c96c74e433dada1a5a2cdf21bfb.jpeg]: https://img-blog.csdnimg.cn/09a13c96c74e433dada1a5a2cdf21bfb.jpeg
[ef785911e3424299b0d1e003f484dcff.jpeg]: https://img-blog.csdnimg.cn/ef785911e3424299b0d1e003f484dcff.jpeg
[b6551c8e8dde423c8f98c5b402f94a32.jpeg]: https://img-blog.csdnimg.cn/b6551c8e8dde423c8f98c5b402f94a32.jpeg
[d81af1cb68794d35af028c273e0d13b6.jpeg]: https://img-blog.csdnimg.cn/d81af1cb68794d35af028c273e0d13b6.jpeg
[fb39f9fa69bd43e4b86884af3b2e48ec.jpeg]: https://img-blog.csdnimg.cn/fb39f9fa69bd43e4b86884af3b2e48ec.jpeg
[348caa416c24490e8f26cfd6953f77f6.jpeg]: https://img-blog.csdnimg.cn/348caa416c24490e8f26cfd6953f77f6.jpeg
[8b7cc9b978e14ec382dadc8d9c1eaed6.jpeg]: https://img-blog.csdnimg.cn/8b7cc9b978e14ec382dadc8d9c1eaed6.jpeg
[714455b9bbeb424e8e8565d065355ff0.jpeg]: https://img-blog.csdnimg.cn/714455b9bbeb424e8e8565d065355ff0.jpeg
[49c70868b16749b2b81ea1ab14bc700a.jpeg]: https://img-blog.csdnimg.cn/49c70868b16749b2b81ea1ab14bc700a.jpeg
[aae6d612b729475da9d8ba4667e18db0.jpeg]: https://img-blog.csdnimg.cn/aae6d612b729475da9d8ba4667e18db0.jpeg
[1_Bob_-CSDN]: https://blog.csdn.net/u011215133/article/details/116612946
[866c7d672e4f30e14c73f9b7a2133883.jpeg]: https://img-blog.csdnimg.cn/img_convert/866c7d672e4f30e14c73f9b7a2133883.jpeg