那些你不知道的avl树和红黑树的姿势！

浅浅的花香味﹌ 2023-02-17 03:15 12阅读 0赞

## 一、二叉排序树 ##

什么是二叉排序树？

对于任意一个节点，左子树的节点都比该节点大，右子树的节点都比该节点小，这就是平衡二叉树，这个和大顶堆有很大区别哦，别傻傻分不清。**画图狂魔上线！**就下面这玩意就叫做二叉排序树。二叉排序树、二叉查找树、二叉搜索树说的都是一个意思！！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

**为啥要有这个东西？它能干啥？装x吗？**

原因是这个东西的查询效率特别高，他的时间复杂度是O（logn），这里的n是树的高度。相比于你一个数组从头遍历还得时间复杂度O（n）呢，所以这个有点像二分法查找，但是二分法需要首先前提要求是数组必须有序。也就是说如果你输入一个无序的数组，这种方式就不行了。如果先排序的话最快时间复杂度O（nlogn）。

所以这个二叉搜索树的这个数据结构就上场了，我先创建这么一个树结构，这个数的插入、删除和查找都是时间复杂度O（logn）（弱弱的说一句，如果给一个数组的话，你将这个数组放入树结构，因为要遍历所以还是O（n），这个结构的主要优势体现在已经建立好了这个树，我们对它进行插入、删除和查找是非常快的）。

**如何查找？**以上面的结构为例，如果查找32，那么先跟头节点比较，发现在右子树，跟45比较，在左子树，跟15比较，在右子树。直到找到。

**如何插入？**跟查找是一样的，找到一个节点，它的左子树或者右子树为null，那么直接插入到上面。

**如何删除？**删除就不是那么容易了，分为以下三种情况：

（1）如果要删除的节点是一个叶节点！直接删除

（2）如果要删除的节点有一个子节点（无论是左还是右），那么直接用左子树节点或者右子树节点代替该节点就可以了。

（3）如果要删除的节点同时有左孩子和有孩子，咋办？看图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

现在要删除节点45，那么有两种方式：

（1）找到该节点左孩子的最大值，用该值（图上32）替换掉45，然后删除左子树的最大值。

（2）找到该节点有孩子的最小值，用该值（图上46）替换掉45，然后删除右子树的最小值。

采用（1）如图所示。上面两种策略应该想5分钟，就能够想明白了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]

至此，二叉搜索树完毕！代码部分，在下面的码云链接里可以找到。

## 二、介绍几种其他的树 ##

### 1、AVL树 ###

这个东西是一个严格的平衡搜索二叉树。还加了一个平衡。

**为啥要有这个东西？它能干啥？很屌吗？**

很屌！！！

如果普通二叉搜索树极端情况，看如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3][]

这个玩意看着眼熟不？这不就是链表吗，二叉搜索树极端情况下退化成链表了！你这还不如链表呢，每个节点比链表多了一个指针！查询速度时间复杂度O（n）。为啥会变成这样，说白了就是不平衡啊。

我给他搞成平衡的。时刻都是平衡的。怎么做到的呢？莫急！！！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4][]

这里面的插入、删除、以及查询跟普通的搜索二叉树是一摸一样的。只不过在执行操作的时候会有一个balance方法执行，如果不平衡，用于调整这棵树！！！我们来说一下这个过程，具体的coding细节可以看代码。先了解两个平衡基本操作：

**左旋和右旋**

看完左旋你就知道右旋咋回事了。

现在的树结构：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5][]

来了一个节点11。变成这个样子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6][]

这一定不平衡，左旋：让头节点的右节点节点记为：right，头节点：head。

然后：head.right = right.left，right.left = head。就是让右孩子成为头节点，然后右孩子的左孩子变成原头节点的有孩子，然后右孩子的左指针指向头节点，变成了这个样子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7][]

可以理解为：右孩子的右子树上面插入数据导致失衡，那么这种情况属于RR，采用左旋。

相反，左孩子的左子树上面插入数据导致失衡，那么这种情况输入LL，采用右旋。

**以上是调整四种情况中的两个。**

**另外两种情况：LR和RL：**

以LR为例子，左孩子的右子树上面插入数据导致失衡。

原树结构是这个亚子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8][]

现在插入7，变成：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9][]

这玩意就不平衡了，是以头节点为9的位置，左右子树不平衡。

我们采用的策略是：（1）对失衡节点的左孩子进行左旋，（2）然后对该节点进行右旋。

经过第一步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 10][]

经过（2）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 11][]

实际上RL场景是一样的。自此删除也是一样的，四种场景！

我们现在来说它是如何找到失衡节点的。首先在每一个节点中除了value、left、right之外还有一个属性就是height，一个指针是parent。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 12][]

树的高度取决于左右子树中height较大的。现在插入11，我们说过插入和普通的二叉搜索树是一样的。刚插入的height=1。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 13][]

然后开始获取11节点的左右子树的高度分别是leftH，rightH，现在肯定没有所以。回退到parent指针，也就是8位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 14][]

同样，8位置会获取左右子树的高度比较，判断他们差的绝对值是否大于了2，然而左子树没有 右子树是1，所以没有大于2。更新当前的height，取两个中大的值 + 1。然后回退到9

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 15][]

同样符合条件，回退到6。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 16][]

然而发现，两个3 - 1 = 2，并不小于2，说明不平衡，然后进行调整。还得调整高度，具体怎么调整可以看代码！

### 2、红黑树 ###

红黑树也是一个二叉搜索树，但是不是一个严格的二叉平衡搜索树。

**鬼见愁的红黑树，每次面试遇到它，小伙伴们是不是要开骂了，还节点上颜色，这些颜色有什么用？一会就告诉你为什么会有颜色这个东西！**

我们来看一下它的性质：

（1）每一个节点是红色或者黑色

（2）根节点是黑色，null节点也是黑色

（3）任意两个红色节点不能相邻（但是黑色节点可以相邻哦，好多同学以为必须红黑相间呢）

（4）从一个节点到该节点的子孙节点的所有路径上面的黑色节点是相同的。（**好多同学不知道这个性质干啥的，我们一会来分析，非常重要！！！**）

我们首先来说这个东西为啥不是一个严格的平衡二叉树，看图（一种极端情况）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 17][]

右边都是黑色节点，左边都是红黑相间，我们关注两边！

现在是符合上面的条件的，这里面的条件（4），保证了根节点到下面所有子节点的黑色节点是相同的，这个树是avl树吗，肯定不是，两边高度差值是2，所以不是平衡树，此时红黑树左边到了最长，右边到了最短，这是一个极限值，左子树的高度是右子树的2倍，也就是说**两边子树高度差不会超过短的两倍。这个相当于是红黑树的平衡条件。**但是确是不符合我们说的avl树。

如此怪异的平衡的目的是啥？红黑树为啥出现？

就是源于这种怪异的平衡，目的是：减少平衡调整次数。在avl树中，最坏的情况是每次插入或者删除都不平衡，两边子树高度差大于1，调用调整平衡方法，但是红黑树的最坏情况并不是每次都需要调整，因为**这个调整的时机，是由两个子树短的高度来决定的**。所以可以减少平衡调整的次数。这也是为什么红黑树要有颜色和一些奇怪的规定的根本原因。

红黑树的插入、查询、删除的时间复杂度都是O（logn），**性能上不能够说谁更优越！**好多人认为红黑树更牛x，这个是不对的！他们只在调整次数上面有不同。

**像avl树一样，红黑树插入有五种组合、删除有八种组合，基本都是左旋和右旋还有变色。**

git@gitee.com:Zesystem/hongheishuheavlshu.git

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200611151937246.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200611155351356.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020061115561456.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200611161144678.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200611161348846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200611163654913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020061116364368.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200611163840560.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200611164443155.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200611164546903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200611165007317.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200611165117647.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200611171302125.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200611171425219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200611171446647.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200611171809942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200611172122548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20200611175316830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70