1、红黑树的概念
红黑树是一棵二叉搜索树,他和前面AVL树不同的是红黑树不是通过平衡因子来保证树的平衡,而是在树结点的处加多了个记录颜色的变量,这个变量可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束,从而确保没有一条路径会比其他路径长处2倍。
1.1 红黑树的特性:
1、每个结点不是黑色就是红色,没有其他颜色。
2、根结点是黑色的。
3、每个根结点到每个路径的结尾处也就是nullptr处时,访问到黑色结点的数量一样,简单点说就是每个路径上的黑色结点的个数是一样的。
4、如果一个结点是红色的,那么他的孩子结点必定是黑色,不能是红色,也就是说一条路径上没有连续的红色结点。
这里补充一下就是黑色结点可以有无数个连续的,不像红色的结点那样有限制。
1.2 红黑树的路径(解释)
可能我们会好奇为什么红黑树能够确保没有路径能比任何一条路径的长度超出两倍。这里我们进行解释一下。
首先我们观察红黑树的特性的最后两条即“每条路径上黑色结点的个数相同”,还有“如果有红色结点,则红色结点的孩子结点必然是黑色,不能存在连续的红色结点”,而这两个条件就已经定死了。
比方说我们想实现最短路径和最长路径,且里面都只有2个黑色结点,最短路径就只能是两个黑色结点连着,而最长路径就是“黑红黑红”的顺序链接,所以最长路径的长度为4。如下图可见
假设最短距离为bh(black height),最长距离就为2bh,我们知道最短距离和最长距离是极端情况,我们平常是很少达到这种情况的所以我们设树长为h,
那么我们就可以推导出一个公式:bh <= h <= 2bh。
根据上面这个公式,我们又可以推出时间复杂度,因为前面二叉树我们讲过树的高度是h, 每层结点的个数为2^h-1,推得2^h-1 <= N <= 2^2*h - 1,h≈logN,红黑树的增删查改最坏也要走2logN,所以时间复杂度为O(logN)。
2、红黑树的实现
2.1 红黑树的结构实现
上面我们说了红黑树和前面的结构几乎类似,只是多了一个表示该结点是什么颜色的变量,该颜色的变量我们可以枚举完即“红”和“黑”那么,我们就可以使用枚举关键字enum进行存储红和黑变量。
而红黑树我们是用key_value结构实现的,那么我们就使用到pair类,然后还有一个Color类型;
结点结构的实现:
#pragma once
#include<iostream>
using namespace std;
//设置红黑结点的定义
enum Colour
{RED,BLACK};//使用key_value的结构来实现红黑树
template<class K, class V>struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
树结构的实现:
和前面AVL树基本类似,只需要传入一个根结点给他就可以,这些都不是重点,所以这里直接上代码。
//定义红黑树的树结构
template<class K, class V>
class BRTree
{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};
2.2 红黑树插入的实现
红黑树的插入我们需要遵循上面红黑树的4条特性,这里我们先列个大概过程出来,因为后面有多种情况需要进行分析。
1、插入的值按二叉搜索树的规则插入。
2、如果树为空,那么插入的结点就是黑色的结点,遵循前面提到的红黑树的特性第二点“根结点是黑色的”。
3、如果树不为空,那么插入的结点即新增的结点就必须是红色的,这个对应前面的第4条规则,因为插入的结点如果是黑色的话就会破坏第四条特性即“每条路径上的黑色结点的数量是相同的”。
4、如果树不为空,插入结点后,如果插入结点的父亲结点也是红色的话违反第三个特性即“不能存在连续两个红色的结点”,那么我们就需要进行分类讨论处理。
这里我们先说明一下等会图内出现的单个字母的表示意思
c为cur,c的父亲为p(parent),p的父亲为g(grandparent),p的兄弟为u(uncle)。
2.2.1 情况一:只需要变色
情况一的条件:只需要变色的条件是c为红,p为红,u存在且为红,g为黑。
即如下图这种情况:
OK,我们来分析一下,首先我们的红黑树的一条特性“如果一个结点是红色,那么他的孩子结点都必须是黑色”,我们看p和c都是红色,连续了,所以我们需要把他们纠正过来,有两种方法:
1、让p变为黑色
2、让c变为黑色
如果我们选择第二种的话,那我们插入的规则即“新插入的结点必须是红色”就被破坏了,那为什么我们不直接改掉规则,让新插入的结点必须是黑色呢?如果我们这么做的话就会破坏“每条路径上黑色结点的数量相同”的规则,这条规则最难维护,因为如果我们在一条路径插入了一个黑色结点,那么我们为了保证这条规则,还需要改变每一条路径上的黑色结点的数量,这样就太麻烦了。
所以我们选择第一种,让parent变为黑色,然后为了解决“每条路径上黑色结点的数量相同”的规则,我们只需要让grandparent变为红色,parent和uncle变为黑色即可。
如果这棵树是某棵树的子树的话则还需要往上继续修改颜色。
实现如下代码所示:
Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//uncle存在且为红色if (uncle && uncle->_col == RED){//开始变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//往上走cur = grandparent;parent = cur->_parent;}
这里只是部分代码的实现,只是这一棵子树的代码实现。最后面会给出完整的代码实现。
2.2.2 情况二:单旋+变色
情况二的条件:cur为红,parent为红,grandparent为黑,uncle不存在或存在且为黑。
uncle不存在的:
uncle存在且为黑色的:
uncle存在或者不存在与cur的关系:
如果uncle不存在,那么cur一定是新增的结点,因为如果u不存在,cur是旧结点的话(旧结点就是本身就存在树内,只是因为子树的变化导致cur从黑色变成红色),那么在变成红色前就已经对不上了,因为那会cur是黑色结点,uncle不存在,root到cur路径就会比root到uncle路径上多一个黑色结点,这不符合红黑树的规则。
如果uncle存在而且为黑色结点的话,那么cur就肯定是旧的结点,c之前就是黑色结点,只不过c的子树中插入了一个结点然后符合情况一(只需要变色),cur作为下面子树的grandparent最终就变成红色了。
分析:因为上面说过了,不能对cur进行改变,那么我们就需要对parent进行修改颜色,让parent的颜色变成黑色,这样就可以解决,但是如果我们按情况一的方法来变色的话就会导致左子树出现两个黑色,因为根结点必须是黑色,尽管通过情况一进行变色后是没有违反黑色结点数量的规则,但是违反了root结点必须为黑色的规则,所以我们 需要对其进行旋转。
实现操作如下:
如果出现下图的情况,那我们必须要让g为旋转点进行右单旋,让p变成root,p变黑,g变红
进行旋转加变色后得到下面这个图:
如果出现下图的情况:那我们一样是按照让g进行单旋,,d变成g的左边,g变成p的右边,p成为新的root,p变黑,g变红,和前面其实是一样的,只不过多了几个结点而已,因为单旋的规则是一样的,变色的规则也是一样的,这里就不细讲单旋操作的逻辑关系,因为前面AVL树有比较详细的讲解。
而单旋+变色的实现很简单,我们只需要使用程序员的“cv大法”,去前面那一篇AVL树的实现那里拿一个右单旋过来使用即可,旋转完我们再让g变成红色,p变成黑色即可。
实现代码如下可见:
//进行单旋操作if (cur == parent->_left){RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}
通过此处我们可以发现当cur==parent->_left的时候就进行单旋加变色操作,如果我们看过前面的AVL树实现那一篇就会发现,当插入的那个结点在插入节点的parent结点的左边的时候是进行单旋操作,在右边如果单单只是用单旋不行,还需要通过双旋进行处理,至此,我们就引出情况三;
2.2.3 情况三:双旋+变色
情况三:c为红,p为红,g为黑,u存在为黑或者不存在都可以,主要的条件是:如果p在g的左边,那么c在p的右边,如果p在g的右边,那么c在p的左边。
其实和前面AVL树实现单旋和双旋的条件很相似,只不过红黑树需要改变结点的颜色。
实现操作如下:
如果出现下面这种情况,我们就思考:我们前面的情况二是通过单旋+变色来解决问题的,但是这个图和前面情况二的不一样,情况二插入的结点是一直往一边倾,那我们就需要构造出一直往一边倾得情况,需要让p进行左旋(因为以p为root的子树是往右倾了,我们想让他往左倾那就需要让他左单旋)。
对p进行左单旋就得到这个,那么我们发现这个结构就和上面的单旋的结构一样了,就可以对g使用右单旋,然后再让c变黑,g变红。
最终得到这个。
如果出现下面这个图,解决思路也是一样的,因为下面这张图其实是一张抽象图,包含了上面图的情况,但是解决思路也是完全类似,所以这里直接开始讲实现的思路;
首先是对p进行左单旋,然后再对g进行右单旋,让c变成树的root,b变成g的左子树,p和g分别变成c的左右子树,然后再让c变黑,g变红,这里的双旋思路和前面实现AVL树也是一样的,只不过就是删掉了平衡因子的修改,添加了颜色的改变。
直接上代码:
//进行双旋操作else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}
ps:这个else是接着上面那个if条件的。
因为左右双旋和右左双旋的实现思路也几乎一样,所以这里也不过多讲述,主要就是uncle结点和parent结点换了位置。
所以接下来我们直接上insert的完整代码:
bool Insert(const pair<K, V>& kv){//如果树为空插入结点就需要让该结点为黑色if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//不是空树,开始找合适的插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//这里出来之后就说明找到了可以插入值的位置cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//链接上父亲cur->_parent = parent;//判断parent是否存在,因为这是遍历完整个树的while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//uncle存在且为红色if (uncle && uncle->_col == RED){//开始变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//往上走cur = grandparent;parent = cur->_parent;}//uncle不存在或者为黑色就需要进行旋转else{//进行单旋操作if (cur == parent->_left){RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//就说明插入或存在且从黑变成红的C在parent的右边,就需要进行双旋操作else{// g// p u// cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}//parent在grandparent的右边else{// g// u pNode* uncle = grandparent->_left;//如果uncle存在且uncle的col为红色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或uncle为黑需要进行旋转操作else{if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//进行双旋操作else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}
ps:前面一大段其实就是平衡二叉树搜索规矩,如果忘记了我们可以看前面平衡二叉树的实现,那里讲的比较详细,其实就是cur->key如果比根结点的大就往右走,小就往左走,一直走到他该处的位置即可,最后这段代码还有一句_root->col = BLACK的作用就是保证根结点的颜色是黑色的。
2.3 红黑树查找的实现
按照二叉搜索树的逻辑实现即可,如果cur的key比当前根结点的key大就往根结点的右子树走,如果cur的key比当前根结点的key小就往根结点的左子树走,一直走到cur该待的位置为止即可。
Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}
2.4 红黑树的验证
如果我们想验证我们的红黑树是否正常,我们只需要验证他们路径上黑色结点的数量是否相等即可。为什么只需要验证第三点特性而不需要验证其他三点特性呢?
其实我们前面的各种操作已经保证了其他三点特性:第一点“每个结点不是黑色就是红色”在用枚举定义变量Colour的时候就已经定死了。
第二点"根结点是黑色"的我们在上面insert的实现的最后一行代码即:_root->col = BLACK也已经保证了这点特性的实现。
第四点"没有连续的两个红色结点",这个验证很麻烦,因为有两个左右子树结点,且不一定存在,但是我们可以放过来检查孩子结点的父亲结点。(等会这点会在下面的check成员函数实现里实现)。
那么通过第三点验证我们可以找一个参考是refNum,然后我们遍历整棵树的左子树找到一条路径上的黑色结点的值,然后再使用递归检查每一棵树到走到空后黑色结点的个数,然后判断是否和refNum相等,如果不相等就返回false即可。如下代码所示:
bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时,意味着一条路径走完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩子不太方便,因为孩子有两个,且不一定存在,反过来检查父亲就方便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}
ps:上面Isbalance就是实现了找refNum值的操作,下面就是实现递归检查最后一个blackNum是否等于refNum的值的操作。
3、完整代码.h和.cpp的代码展示
因为有很多代码例如得到树的高度,树的结点个数还有前序遍历打印都在前面AVL树实现,和在数据结构里的二叉树讲过,而且难度也不是很大,对递归有一定的了解即可看懂,如果不懂的话可以尝试画一下递归展开图进行了解。
3.1 .h代码
#pragma once
#include<iostream>
using namespace std;
//设置红黑结点的定义
enum Colour
{RED,BLACK};//使用key_value的结构来实现红黑树
template<class K, class V>struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};//定义红黑树的树结构
template<class K, class V>
class BRTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){//如果树为空插入结点就需要让该结点为黑色if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//不是空树,开始找合适的插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//这里出来之后就说明找到了可以插入值的位置cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//链接上父亲cur->_parent = parent;//判断parent是否存在,因为这是遍历完整个树的while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//uncle存在且为红色if (uncle && uncle->_col == RED){//开始变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//往上走cur = grandparent;parent = cur->_parent;}//uncle不存在或者为黑色就需要进行旋转else{//进行单旋操作if (cur == parent->_left){RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//就说明插入或存在且从黑变成红的C在parent的右边,就需要进行双旋操作else{// g// p u// cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}//parent在grandparent的右边else{// g// u pNode* uncle = grandparent->_left;//如果uncle存在且uncle的col为红色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或uncle为黑需要进行旋转操作else{if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//进行双旋操作else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时,意味着一条路径走完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩子不太方便,因为孩子有两个,且不一定存在,反过来检查父亲就方便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}
private:Node* _root = nullptr;void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}
};
3.2 .cpp代码
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"BRTree.h"void TestRBTree1()
{BRTree<int, int> t;// 常规的测试用例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalance() << endl;
}int main()
{TestRBTree1();return 0;
}
END!