【C++】红黑树的性质和实现
上篇博客我们了解了AVL树,这篇博客就让我们来看看另外一个二叉树:红黑树
使用的编译器:VS2019
[TOC]
博客里面引用了一些百度搜到的图片(自己懒的画了,呜呜)
1.概念
AVL树是一个几乎完全平衡的搜素二叉树,其左右子树的高度差不会超过1。与之相对应的,是每一次插入都有可能需要旋转多次,插入的效率较低。
而红黑树则选择了“相对平衡”,并拥有以下的特性:
红黑树可以保证最长路径的小于最短路径的2倍
比如最短路径为30,那么最长路径就不能超过60
对于cpu来说,AVL树遍历20次(百万级数据)和红黑树遍历40次的时间差距极小。所以红黑树即保持了相对平衡,又减小了AVL树多次旋转的消耗。
1.1 性质
其通过下面的几点来维持这一性质:
- 每一个节点不是红色就是黑色
- 根节点一定是黑色
- 每一个红节点的左右子树都是黑色
- 每一个到叶子(空节点NIL)的支路上黑节点数量相同
- 叶子节点(空节点NIL)视作黑色
为什么满足了这几个情况,就满足了红黑树的最长路径的小于最短路径的2倍
的性质呢?
约束4和5,保证了红黑树的大致平衡:根到叶子的所有路径中,最长路径不会超过最短路径的2倍。
这使得红黑树在最坏的情况下,也能有O(logN)
的查找效率
- 黑色高度为3时,最短路径:黑色→ 黑色 →黑色
- 最长路径:黑色→红色 →黑色 →红色 →黑色
- 此时最短路径的长度为2(不算Nil的叶子节点),最长路径为4
这里可以得出一个普遍规律,红黑树最短路径即为全黑路径。而最长路径是一黑一红间隔的情况
1.2 时间复杂度
平衡二叉树(AVL树)和红黑树都是常用的自平衡二叉搜索树。它们的查询操作的平均时间复杂度都为O(log n),其中n是树中节点的数量。
在平衡二叉树中,任意节点的左子树和右子树的高度差不超过1,通过局部旋转操作可以保持平衡。这样,树的高度始终保持在O(log n)的水平,从而使得查询操作的时间复杂度为O(log n)。
红黑树是一种更加复杂的自平衡二叉搜索树,它通过对节点进行染色(红色或黑色)和旋转操作来保持平衡。红黑树具有以下性质:
根据上文提到的红黑树性质,红黑树的高度始终保持在O(log n)的水平,因此查询操作的时间复杂度也为O(log n)。
综上所述,平衡二叉树和红黑树的查询平均时间复杂度都是O(log n)。最差情况中,两个数的节点高度都不会超过 2log(n+1)
,所以最坏的时间复杂度还是O(log N)
2.设计一颗红黑树
在设计红黑树的时候,我们需要牢记上面的5点。其中前4点非常重要且不可以被破坏。一旦被破坏,就影响了红黑树的基本性质。
2.1 设计节点
和AVL树一样,我们需要把节点单独成一个类,来存放我们需要的pair
这里就设计到了颜色的初值应该给什么。红色,还是黑色?
来看看性质3和4:
- 红色的左右子树必须是黑色
- 每一个到叶子(空节点NIL)的支路上黑节点数量相同
简单思考,即可发现,插入红节点的时候,更好控制。而插入黑节点极有可能破坏性质4且较难修复。
1 | //枚举,定义颜色 |
2.2 插入的几种情况
节点设计好了,我们只需要把插入的逻辑搞定,那么红黑树也就完成了!
前半部分的代码和AVL树完全相同,只不过我们需要手动给根节点一个黑色(默认是红色)以维持性质2
1 | bool Insert(const pair<K, V>& kv) |
2.2.1 情况1:无需旋转
在下面的这种情况中,我们在p的左边插入了一个cur新节点。此时违反了性质3,红节点的孩子必须要是黑节点。
这种情况必须满足p和u都是红节点
随后我们就需要开始向上进行更新,操作如下:
- 把p和u都改成黑节点
- 把g改成红节点
修改之后的结果如下,即不影响性质3;也保证了黑节点的个数不变,维持了性质4
需要注意的是,这里的g不一定是根节点。所以在操作完这一课子树之后,我们需要继续向上进行操作,避免g的父节点是红色的情况。
代码实现如下(以父节点为g的左子树为例)
1 | //插入之后需要向上更新颜色,只有出现连续红色之后才需要更新 |
需要注意的是,这种调整会把g改成红节点。如果G是根节点,改成红色之后就不符合性质了。所以我们需要在操作完成之后,统一把根节点改成黑色
1 | //不管是什么情况,最后都把根改成黑,符合条件2 |
2.2.2 情况2:需要单旋
当我们插入了一个cur向上更新的时候,就可能会遇到下图中间的情况。p是红节点,违反了性质3,而u是黑节点,不能简单粗暴的通过把p改成红来解决。
这时候我们就需要针对g进行一次单旋(图中是右单旋,可以简单理解为向u旋转)。因为cur和p形成了同侧的连续两个红节点。和AVL树的单旋情况相似,只有这两节点在同侧,才可以执行单旋。
旋转完毕之后,需要把g更新为红节点,p更新为黑节点
2.2.3 情况3:需要双旋
在情况2中,p和cur都是在它们父亲的同一侧。而情况3就是p和cur在父亲的不同侧。
- 比如p是g的左子树,cur是p的右子树
- 同时满足p是红,u是黑
这时候就需要进行一次三旋,操作如下:
- 以p作为基点,向cur的另外一个方向单旋一次(上图中就是左旋)
- 旋转了之后,就会变成情况2
- 这时候再以g为基点,向u的方向旋转一次(上图中为右旋)
- 旋转完成之后,把g设置为红,cur设置为黑即可
一下是完整的三种情况代码(p是g的左子树的情况)
1 | //p是g的左 |
由于篇幅限制,p是g右子树的情况就不贴出来了,实际上就是把上面的代码全反过来就行了
完整代码请查看我的gitee仓库
2.3 查找(和AVL树完全相同)
1 | //因为kvl树我们需要修改value,所以返回节点的指针 |
2.4 判断是否是红黑树
有两种方案,1是可以通过计算最大高度/最小高度进行间接判断,2是以红黑树性质来验证是否满足最上面提到的5点
2.4.1 计算最小最大高度
这里实现递归即可,最小长度其实就是在最后return的判断中,把大于号改成小于号,返回小的那个子树的高度+1
1 | int maxHeight(){ |
只要最大长度小于最小长度的2倍,那么基本规则就是没有破坏的
但这还不够,我们还需要检查它是否满足红黑树的其余性质
2.4.2 递归检查性质
这里再次列出5点性质
- 每一个节点不是红色就是黑色
- 根节点一定是黑色
- 每一个红节点的左右子树都是黑色
- 每一个到叶子(空节点NIL)的支路上黑节点数量相同
- 叶子节点(空节点NIL)视作黑色
然后通过两个函数来实现,其中一个函数需要进行递归
1 | bool IsRBTree() |
可以看到,不管是随机数还是顺序插入,都通过了检查
3.红黑树的运用
红黑树在很多地方都有使用,在C++中,最为经典的便是map和set这两个容器,它们便使用了红黑树作为底层逻辑
https://gitee.com/musnow/learn_cpp_code/blob/master/STL-Sourcecode/stl_tree.h
在stl源码中,我们可以找到这个tree.h
,里面便是一个红黑树的实现。而map和set就是调用了红黑树,只做了一个简单的封装
结语
在下篇博客中,我会记录map和set的基本使用,以及通过红黑树模拟实现map和set
感谢大家支持!