之前我们分析了红黑树的原理和操作算法,现在我们来用C++语言实现一个基本的红黑树结构。在后文的插入和删除操作中提到的各种情况,详细描述请参见上一篇文章。
具体代码可参考https://github.com/LumiOwO/DS-Playground/blob/master/include/tree/RBTree.h
1 数据结构定义
首先,为红黑树结点的颜色定义一个枚举:
1 | /// Enumeration for node color. |
之后定义红黑树结点RBTreeNode
模板类。这里我额外增加了模板参数ALLOW_DUP
,该参数表示是否允许结点出现相同的值。具体实现这个类时,我考虑了以下几点:
- 在这个类中,指向左右子树的指针使用的是C++11标准提供的智能指针,这样就不需要在程序结束后手动释放申请的结点内存了;
- 由于在插入和删除过程中都需要根据当前结点找到父结点的位置,因此在结点中加入指向父结点的指针;
- 为了避免
shared_ptr
循环引用,指向父结点的指针应该使用weak_ptr
; - 将指向
RBTreeNode
类的智能指针重命名为RBTree
1 | template <typename T, bool ALLOW_DUP = false> |
2 Inline函数
主要有两个Inline函数:IsBlack()
和IsRed()
,用来判断结点的颜色。之所以不把这两个函数写成结点的成员函数,是因为空的NIL结点将被看做黑色的结点,而访问空指针的成员函数将会报错。换句话说,如果在代码中用IsRed()
函数判断出一个结点为红色,则该指针必不为空指针。
1 | template <typename T, bool ALLOW_DUP> |
3 搜索
搜索过程和在二叉搜索树中查找目标值的过程相同。这里给出非递归的搜索代码:
1 | template <typename T, bool ALLOW_DUP> |
4 旋转
旋转操作分为左旋和右旋。这里以左旋为例。
首先声明左旋函数。因为旋转后顶部的结点发生了变化,因此应该传入的指针top
应该是一个引用,然后在函数的最后将top
的值修改为旋转后的顶部结点位置。
1 | template <typename T, bool ALLOW_DUP> |
第一步应该找到旋转过程的关键结点,即当前结点self
和右子树that
。同时别忘了我们的结点还要维护指向父结点的指针。
1 | RBTree<T, ALLOW_DUP> self = top; |
之后改变关键结点self
和that
的相对位置:
1 | self->_parent = that; |
最后,调整这两个结点相关的其他结点指针:
1 | // 调整子树 |
右旋的操作类似,镜像地考虑即可。
Tips: 按照镜像的情况重新思考一遍能加深对算法的理解。但如果实在想不清楚,直接将代码中的
left
和right
两个单词互换即可得到正确结果。之后提到的左右镜像操作都可以按照这样的思路去考虑。
5 插入
插入操作的函数声明如下:
1 | template <typename T, bool ALLOW_DUP> |
该函数传入一棵红黑树的根结点指针引用root
,将目标值value
插入树中,并返回一个布尔量表明是否插入成功。如果模板参数ALLOW_DUP
为false
,那么插入一个已在树中的值时,函数将不会为插入的值新建结点,而是直接返回false
。
插入函数实现的原则是:先插入后调整。
5.1 插入
按照二叉搜索树的插入思路,首先找到待插入的结点位置:
1 | RBTree<T, ALLOW_DUP> parent = nullptr; |
找到插入位置后,新建一个红色结点并插入树中:
1 | cur = std::make_shared<RBTreeNode<T, ALLOW_DUP>>(RED, value); |
插入完成后,对当前结点进行调整,使红黑树平衡:
1 | __Insert_Adjust(cur, root); |
5.2 调整
插入操作的调整函数声明如下:
1 | template <typename T, bool ALLOW_DUP> |
该函数传入当前指向的结点指针引用cur
和整棵树的根结点引用root
。
首先,找到cur
结点的父结点parent
,并考虑情况1:父结点为黑色
1 | RBTree<T, ALLOW_DUP> parent = cur->_parent.lock(); |
之后找到祖父结点grand
:
1 | RBTree<T, ALLOW_DUP> grand = parent->_parent.lock(); |
下面考虑父结点为祖父结点的左子树的情况,即parent == grand->_left
。
首先找到叔叔结点uncle
,并考虑情况2:父结点为红色,且叔叔结点为红色。这种情况下,将父结点和叔叔结点置为黑色,并将祖父结点置为红色,之后向上递归地调整。
1 | RBTree<T, ALLOW_DUP> uncle = grand->_right; |
接着考虑情况3:父结点为红色,且叔叔结点为黑色。如果此时当前结点为父结点的右子树(即情况3.1),应该通过左旋操作转化为当前在父结点左子树的情况(即情况3.2)。对于情况3.2,将父结点颜色置为黑色,并将祖父结点置为红色,随后将祖父结点右旋即可。注意祖父结点有可能会是整棵树的根结点,因此要注意更新根结点指针root
。
1 | // 情况3 |
父结点为祖父结点的右子树时,可以镜像地考虑。
6 删除
删除操作的函数声明如下:
1 | template <typename T, bool ALLOW_DUP> |
该函数传入一棵红黑树的根结点指针引用root
,将目标值value
从树中删除,并返回包含删除值value
的结点指针。如果该值不在树中,则返回空指针。
首先,我们需要找到包含value
值的结点。这里直接使用之前的Search
函数即可。
1 | RBTree<T, ALLOW_DUP> cur = Search(root, value); |
找到对应结点后,需要判断该结点的度。如果度为2,即有两个子树,我们找到右子树中的最小结点,将当前结点值value
和这个最小结点的值交换,并改为在右子树中删除value
值。这样就能保证删除结点的度是小于等于1的,即最多只有一棵子树。
1 | if (cur->_left && cur->_right) { |
删除函数实现的原则是:先调整后插入。
6.1 调整
注意只有在删除黑色结点时才需要调整:
1 | if (IsBlack(cur)) { |
删除操作的调整函数声明如下:
1 | template <typename T, bool ALLOW_DUP> |
该函数传入当前指向的结点指针常引用cur
和整棵树的根结点引用root
。
首先仍然是找到父结点parent
。如果父结点为空,说明当前为根结点,直接退出函数。
1 | RBTree<T, ALLOW_DUP> parent = cur->_parent.lock(); |
下面考虑当前结点为父结点的左子树的情况,即cur == parent->_left
。
首先获得兄弟结点sib
,并考虑情况1:兄弟结点为红色。这时需要将其转化为兄弟结点为黑色的情况。因此将父结点置为红色,兄弟结点置为黑色,然后将父结点左旋即可。注意父结点有可能会是整棵树的根结点,因此要注意更新根结点指针root
。旋转结束后,更新当前的父结点指针parent
和兄弟结点指针sib
。
需要注意的是,由于当前结点是黑色的,所以兄弟结点的路径上必须要有黑色结点。这也就意味着兄弟结点一定不为空指针。
1 | RBTree<T, ALLOW_DUP> sib = parent->_right; |
接下来,我们先考虑情况3:兄弟为黑色,右侄子为黑色,左侄子为红色,因为这种情况可以转化为后面的情况2。这里我们将左侄子置为黑色,兄弟结点置为红色,然后将兄弟结点右旋即可。
1 | // 情况3 |
对于情况2:兄弟为黑色,右侄子为红色,左侄子任意,我们将右侄子置为黑色,然后将兄弟结点和父结点的颜色互换,最后将父结点左旋即可。同样注意,这里的父结点可能为树的根结点。
1 | // 情况2 |
最后考虑情况4:兄弟为黑色,右侄子为黑色,左侄子为黑色。这里又分为两种子情况:如果父结点为红色,即情况4.1,将兄弟置为红色、父结点置为黑色即可;如果父结点为黑色,即情况4.2,将兄弟置为红色,并对父结点递归地向上调整。
1 | // 情况4 |
当前结点为父结点的右子树时,可以镜像地考虑。
6.2 删除
由于之前的操作已经将树的结构调整为待删除结点处的路径上多出了一个黑色结点,并且该结点最多只有一棵子树,因此我们直接将当前的cur
结点从树上删除即可。
这里有一个特殊情况需要优先处理:当前结点cur
为根结点。由于我们已经保证了当前结点最多只有一棵子树,因此cur
为根结点时只会有以下三种情况:1. 根结点为叶结点;2. 根结点只有一个左儿子,左儿子为红色的叶结点;3. 根结点只有一个右儿子,右儿子为红色的叶结点。
1 | if (!parent) { |
最后,对于一般的情况,将当前结点的子树接到父结点对应的位置上即可。
1 | // 父结点子树指针的引用 |
7* 测试
为了使测试结果更直观,我采用的测试办法是:手动设计几个测试样例,将每次操作结束的红黑树结构用可视化的方式输出,观察其和手动模拟的结果是否相同。
我使用了Graghviz工具进行红黑树的可视化。操作流程为:
- 安装Graghviz程序,并添加到环境变量
- 将红黑树输出为.dot文本文档
- 使用命令
dot -Tpng 文档名.dot -o 图片名.png
输出为png格式的图片
文档的具体格式和其他使用细节在此不展开讨论,可参考我的红黑树测试代码。