C++之红黑树
文章目录
目录
前言
一、红黑树的相关规则
二、对其规则的解释
三、红黑树的效率
四、红黑树的实现
4.1 红黑树的结构
4.2 红黑树的插入
4.2.1 操作情况1：变色
4.2 .2 操作情况2：单旋+变色
4.2.3 操作情况3：双旋+变色
4.3 红黑树的查找
4.4 红黑树的验证
五、红黑树封装实现set,map
5.1 set,map的底层结构
5.2 模拟实现set,map
5.3 set,map的iterator模拟实现
5.4 set的模拟实现代码
5.5 map的模拟实现
前言
在这之前，我们学习了AVL树，它是一棵二叉搜索树，它通过平衡因子（balance factor)来保证平衡（子树之间的高度差保持在一定的范围之内），它从本质上提高了二叉搜索树的搜查效率。而这节我们再来学习一种二叉搜索树——红黑树。这种二叉搜索树的树结点上增加了一个属性——颜色，颜色为红色或黑色。通过对各节点上的颜色进行约束从而使得整个树平衡。
一、红黑树的相关规则
红黑树是一种自平衡二叉搜索树，通过特定的颜色标记和性质约束，确保树的高度保持在O(log n)以内，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。以下是红黑树结点的相关规则：
- 红黑树的根节点颜色一定要是黑色的；
- 如果一个结点的颜色是红色的，那么它的两个子结点都要是黑色的（即没有两个连续的红色结点）
- 从任一结点到达其每一个叶子结点的所有路径上都包含有相同数目的黑色结点；
- 每个叶子结点（NIL结点，空结点）是黑色的。
上面几种情况都是红黑树，我们可以看到它们都是遵循上面那四条规则的。其中，我们还可以使所有结点的颜色都设置为黑色（但是我们要确保根节点到其所有的叶子结点中的结点数都相同，即为一个满二叉树），但是我们不可以将所有结点的颜色设置为红色，那样就违反了规则2。
二、对其规则的解释
首先，对于其根节点的颜色一定是黑色的，我们就把它当成是约定俗成的。其实我们把规则3和规则4放在一块看，就能够看出蹊跷。我们要保持任意节点到其叶子结点的黑色结点数一致，且叶子结点（空结点)是黑色的，我们只能够将根节点设置为黑色，才能够保证上面两个规则在所有情况下都能够成立，如果根节点为红色的话，那么我们就不能够保证所有情况都能够使得上面那些规则成立，只有在满二叉树的时候，根节点为红色是可能成立的。
由规则3可知，由根到达NULL结点的每条路径上都有相同数目的黑色结点，所以在极端情况下，红黑树的最短路径就是全是黑色结点的路径，假设最短路径为bh(black height)。我们由规则2可以知道，在红黑树中是不能够有两个连续的红色结点的，因此我们的最长路径就是一红一黑结点间隔排列，那么其最长路径为2*bh。综合那四条规则，红黑树的高度设为x，那么 bh<=x<=2*bh。因此也就验证了红黑树的最长路径是不超过最短路径的2倍的，这也是红黑树保证其平衡的重要准则。
三、红黑树的效率
假设红黑树的结点数目为N,其最短路径为h,那么红黑树的结点数范围为 2^h -1 <= N <= 2^2*h -1,由此我们可以推出h约等于longN,最长路径也约等于2*longN，因此红黑树对于每条路径上的增删查改的时间复杂度都是O(longN)。
红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。
四、红黑树的实现
4.1 红黑树的结构
红黑树较我们之前的AVL树而言，也就多了一个颜色的属性，其大体结构和我们之前的AVL树基本上都是一样的。对于颜色，我们可以使用枚举，来将我们所需要的颜色（红RED,黑BLACK)都放进去。
enum Colour
{RED,BLACK
};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){}};4.2 红黑树的插入
回想一下，我们之前AVL树的插入，我们先是寻找一下插入位置，然后再创建一个新的结点进去插入，然后我们再对那个树进行旋转操作使其保持平衡，其中旋转操作主要是为了保持平衡因子正确。而在红黑树中，我们也会进行一些简单的旋转操作，那些旋转操作是为了保证红黑树对一些结点的颜色进行修改后仍然符合规则。
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;while (parent && parent->_col==RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) //uncle一定存在，且是红色的//parent uncle的颜色都是红色的，g是未知的//我们将p,u都变成黑色的，g变成红色的{parent->_col = uncle->_col = RED;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //uncle不存在或者存在也是黑色的{// g// p u// cif (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// g c// p u p g// c uelse{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// g p// u p g c// c u if (parent->_right== cur){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// g c// u p u g // c pelse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}我们对红黑树进行插入时，也要分情况进行插入，当树为空树的时候，我们需要插入一个黑色结点作为根节点，这是我们的规则1所要求的；当树不为空树的时候，我们需要先找到插入的位置，毕竟红黑树的本质是一棵平衡二叉搜索树，我们要确保其平衡，不能够随意插入结点。这里我们新插入的结点的颜色我们一定要注意一下：我们新插入结点的颜色必须是红色的。因为有红黑树的规则3（每条路径上的黑色结点数目要保持一致）的约束，因此我们新插入的结点不能为黑色的，因为一旦插入，那个黑色结点数目相等的平衡就被打破了。插入之后，我们就要对整个红黑树的所有结点进行一个检查（遵循上面那四条规则），如果不遵循上面的规则，我们就要进行一些操作修改。
这里我们检查颜色的循环条件，我们设置为 parent && parent->_col==RED 。我们首先要保证我们新插入结点cur有一个双亲结点parent ，然后我们再对根据规则2（不能有连续两个红色结点）的要求，我们设置parent的结点颜色为红色，cur也是红色的，那么只能够parent为黑色才能够跳出那个循环；否则的话，它就要进入到循环中进行操作（变色操作，旋转操作）。对于parent的颜色操作我们就要追溯到它的双亲结点grandfather和它的兄弟结点uncle。我们通过它们在不同的位置以及颜色，来画出示意图，然后我们再根据示意图进行旋转，变色等操作。在进行颜色的检查完后，我们一定要保证根结点的颜色是黑色的。
接下来我们将我们的新插入结点cur，cur双亲结点parent,parent的双亲结点grandfather,parent的兄弟结点分别简写为c,p,g,u。以便对下面几种情况的赘述。
4.2.1 操作情况1：变色
c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。在把g当做新的c，继续往上更新。分析：因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加⼀个黑色结点，g再变红，相当于保持g所在子树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题，需要继续往上更新是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束了；如果g就是整棵树的根，再把g变回黑色。 情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。
4.2 .2 操作情况2：单旋+变色
c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c⼀定是新增结点，u存在且为黑，则 c⼀定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。
如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。
如果p是g的右，c是p的右，那么以g为旋转点进行左单旋，再把p变黑，g变红即可。p变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。
4.2.3 操作情况3：双旋+变色
c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c⼀定是新增结点，u存在且为黑，则 c⼀定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。
如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变 黑，g变红即可。c变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且 不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。
如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点进行左单旋，再把c变黑，g变红即可。c变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且 不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。
4.3 红黑树的查找
由于红黑树的本质上还是一棵二叉搜索树，而且查找这一操作并不依赖颜色这一属性，因此我们红黑树的操作逻辑即为二叉搜索树的查找逻辑：定义一个结点从根节点出发，按照二叉搜索树的遍历规则（左小右大）进行遍历。
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;}4.4 红黑树的验证
我们并不能通过 最长路径不超过最短路径的2倍 这一根据来验证是否是一棵红黑树，就算满足了这一条件，其颜色也不一定能够满足规则，即使当前满足了，在后续的插入中，也可能导致不是红黑树。因此我们还是得根据以下四点规则进行验证，满足了这四点规则，也就能保证我们的最长路径不超过最短路径的2倍
- 规则1枚举每个结点的颜色：不是黑色就是红色；
- 规则2直接检查根结点的颜色即可；
- 规则3前序遍历检查是否有两个连续的红色结点，但是遇到红色结点查孩子结点不太方便，因为孩子结点有两个，还有可能不存在，因此我们放过来检查，遇到红色的孩子结点，我们检查其双亲结点的颜色；
- 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再以任意一条路径（我们的参考代码中是以最左的那条路径）黑色结点数量作为参考值，依次比较即可。
bool Check(Node* root, int balcknum, const int refnum){if (root == nullptr){if (blacknum != refnum){cout << "存在黑色结点不一致的路径" << endl;return false;}return true;}if (root == RED && root->_parent->_col == RED){cout << "存在连续的红色结点的路径" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, balcknum, refnum) && Check(root->_right, balcknum, refnum);}bool isBalance(const K&key){if (_root == nullptr){return true;}if (_root->_col == RED){return false;}int refnum = 0;Node* cur = _root;while (cur){if (cur->_kv.first ==BLACK)refnum++;cur = cur->_left;}return Check(_root, 0, refnum);}五、红黑树封装实现set,map
5.1 set,map的底层结构
在我们刚开始学习map和set的时候，我们就已经介绍过了，这两个STL的底层实现结构是红黑树。当时我们连AVL树都还没学，我们只是简单介绍了一下set和map的简单使用。今天我们学习完了红黑树，也学习了如何实现一棵红黑树，那么我们就来封装一下红黑树，再模拟实现一下set和map。
在模拟实现set和map之前，我们先了解一下它们两个之间的区别：set只能存储一个数据，而map存储的是一个数据对。我们是不可以对set的数据进行修改的，因为那个唯一的数据是用来表示它在红黑树中的结点位置的，但是map中可以修改数据，因为它的结点存储的是一个数据对，一个数据来表示在红黑树中的结点位置，一个数据表示具体值，这个我们是可以进行修改的。
上图，是从stl源码中截取的一段代码，我们可看到源码中rb_tree用了⼀个巧妙的泛型思想实现，rb_tree是实 现key的搜索场景，还是key/value的搜索场景不是直接写死的，而是由第⼆个模板参数Value决定 _rb_tree_node中存储的数据类型。
set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是 pair，这样⼀棵红黑树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。要注意一下，源码里面模板参数是用T代表value，而内部写的value_type不是我们我们日常 key/value场景中说的value，源码中的value_type反而是红黑树结点中存储的真实的数据的类型。
rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型，为什么还要传第一个模板 参数Key呢？尤其是set，两个模板参数是一样的，这是很多同学这时的一个疑问。要注意的是对于 map和set，find/erase时的函数参数都是Key，所以第一个模板参数是传给find/erase等函数做形 参的类型的。对于set而言两个参数是一样的，但是对于map而言就完全不一样了，map的insert是pair对象，但是find和ease的是Key对象。
5.2 模拟实现set,map
我们在上面已经说过了，我们是以红黑树作为底层结构来实现set和map的。因此我们首先要对红黑树的结构结构进行处理，我们从上面的源码中可以看到，我们复用红黑树来实现set和map时，我们对红黑树的参数时使用了一个泛型思想的，即并不是一个写死的类型，是可以根据不同的对象进行变化类型的。我们这里模拟实现相比源码调整一下，key参数就用K，value参数就用V，红黑树中的数据类型，我们使用 T。
其次因为RBTree实现了泛型不知道T参数导致是K，还是pair，那么insert内部进行插入逻辑比较时，就没办法进行比较，因为pair的默认支持的是key和value一起参与比较，我们需要时的任何时候只比较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进行比较，具体 细节参考如下代码实现。
//settemplate<class K>class myset{struct SetKeyofT{const K& operator()(const K& key){return key;}};};//maptemplate<class K,class V>class Mymap{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};};//RBTreetemplate<class K,class T,class KeyOfT>class RBTree{public:private:};5.3 set,map的iterator模拟实现
我们iterator实现的大框架和我们之前学习的list的iterator的思路是一致的，用一个类型封装结点的指针，再通过重载运算符来进行实现，迭代器就行指针一样访问的行为。这里我们的operator++和operator--和我们的list是不一样的，只是向前或向后走，我们这里是树形结构，我们在学习map和set时知道了，它们的迭代器是按照树的中序遍历进行访问遍历的即，左子树->根节点->右子树，那么begin（）会返回中序中的第一个结点的iterator。
迭代器++的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下一个结点。
- 迭代器++时，如果it指向的结点的右子树不为空，代表当前结点已经访问完了，要访问下一个结点是右子树的中序第一个，一棵树中序第一个结点是它的最左结点，所以我们直接找右子树的最左结点即可；
- 迭代器++时，如果it指向的结点的右子树为空，代表当前结点已经访问完了且当前结点所在的子树也已经访问完了，要访问的下一个结点在当前结点的祖先中，所以我们要沿着当前结点到根的祖先路径向上查找。
- 如果当前结点时父亲结点的左孩子结点，根据中序顺序：左子树->根节点->右子树,那么下一个访问的结点就是当前结点的父亲结点；
- 如果当前结点是父亲结点的右孩子结点，根据中序顺序：左子树->根节点->右子树,说明当前当前结点所在的子树已经访问完了，当前结点所在父亲的子树也访问完了，那么下一个访问的结点需要继续往根的祖先结点中去找，直到找到孩子是父亲结点左边的那个祖先就是中序要遍历的下一个结点。
对于end()就是表示最后一个有效结点的下一个位置，我们中序遍历的最后一个结点是个叶子结点，那么叶子结点的下一个结点就是nullptr,所以我们一般将end()设置为nullptr。那么--end()就是中序遍历的最后一个结点，也就是整个红黑树中最右下端的那个结点。
迭代器--的实现和++的思路完全类型，逻辑正好反过来即可，那么迭代器--所访问的顺序就是：右子树->根节点->左子树。
set的iterator不支持修改，我们把set的第二个模板参数改成const K即可,RBTree<K,const K,SetKeyOfT> _t;
map的iterator不支持修改key但是可以修改value，我们把map的第二个模板参数pair的第一个参数改成const K即可， RBTree<K, pair<const K,V> ,MapKeyOfT> _t;
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right)//如果当前结点的右子树不为空，那么迭代器++即为右子树中序遍历的第一个结点{Node* minleft = _node->_right;if (minleft->_left){minleft = minleft->_left;}_node = minleft;}else//这种情况说明我们右子树中所有的结点都已经访问完了，我们需要往上来寻找下一个中序遍历的结点了，我们定义两个结点，一个当前结点，一个当前结点的父亲结点，当我们的当前结点时父亲结点的左孩子时，我们此时的双亲结点就是我们下一个要访问的结点了{Node* cur = _node;Node* parent = cur->_parent;while (parent &&cur==parent->_right){cur = parent;parent = cur->_parent;}//此时cur是parent->left (LDR)_node = parent;}return *this;}Self& operator--(){if (_node == nullptr) //end(){//--end()则表示的是整个树的最后一个结点，即整个树的最右结点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left) //_node结点的左子树不为空，则上一个即为左子树的最右结点{Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left==cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}};5.4 set的模拟实现代码
对于set的模拟实现很简单，由于它没有修改结点值等操作，因此我们可以直接符我们的红黑树的代码来实现一些它的各种功能。
#pragma once
#include"RBTree2.h"
namespace hjc
{template<class K>class myset{struct SetKeyofT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyofT>::Iterator iterator;typedef typenaem RBTree<K, const K, SetKeyofT>::ConstIterator const_iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}const_iterator begin() const{return _rbtree.Begin();}const_iterator end() const{return _rbtree.End();}pair<iterator, bool> Insert(const K& key){return _rbtree.Insert(key);}iterator Find(const K& key){return _rbtree.Find(key);}private:RBTree<K, const K, SetKeyofT> _rbtree;};
}5.5 map的模拟实现
map相较于set就麻烦一点，因为它可以对值进行修改，因此它多了一个接口operator[ ]，我们在当时介绍这个接口时，就说了这是一个复合接口，它可以查找+修改，也可以插入+修改。这得益于它特殊的结构。它有两个pair:⼀个是map底层红黑树节点中存的pair<key,T>，另一个是insert返回值pair<iterator,bool>。如下是map的一段源码：
因此我们在模拟实现map的insert时，我们要创建一个pair来接收红黑树插入的pair，返回时返回那个创建pair的一个数据。
V& operator[](const K& key){pair<iterator, bool> ret = _rbtree.Insert({ key,V() });return ret.first->second;}下面是map模拟实现的全部代码：
#pragma once
#include"RBTree2.h"
namespace hjc
{template<class K,class V>class Mymap{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<K, V>, MapkeyOfT>::ConstIterator const_iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}const_iterator begin() const{return _rbtree.Begin();}const_iterator end() const{return _rbtree.End();}pair<iterator, bool> Insert(const pair<K,V>& kv){return _rbtree.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _rbtree.Insert({ key,V() });return ret.first->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _rbtree;};
}