c++进阶之------红黑树

一、概念

红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学的许多领域中都有广泛应用，比如Java中的TreeMap和C++中的set/map等数据结构的底层实现。红黑树通过在每个节点上增加一个颜色属性（红色或黑色），并遵循一定的规则来确保树的平衡性，从而保证了各项操作的时间复杂度为O(log n)。

二、性质

红黑树具有以下性质：

1. 每个节点是红色或黑色。

2. 根节点是黑色。

3. 所有叶子节点（NIL节点）是黑色。

4. 如果一个节点是红色，则它的两个子节点都是黑色。（注：这条规则保证了从任一节点到其每个叶子节点的所有路径上不会出现两个连续的红色节点）

5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

三、构建红黑树

3.1 树的基本结构

#pragma once// 枚举值表示颜色
enum color
{RED,BLACK
};
// 这里我们默认按key/value结构实现
template<class K,class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针pair<k, v> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};

3.2 树的插入

在红黑树中插入一个节点后，可能会破坏红黑树的性质，因此需要通过旋转和重新着色来恢复红黑树的平衡。插入操作的具体步骤如下：

1. 插入节点：按照普通二叉查找树的插入方式插入新节点，并将新节点着色为红色。

2. 检查平衡性：检查插入新节点后是否破坏了红黑树的性质。如果插入的新节点是根节点，则直接将其着色为黑色；如果新节点的父节点是黑色，则红黑树的性质未被破坏，插入结束；如果新节点的父节点是红色，则需要进行修复。

3. 修复红黑树性质：根据新节点的父节点和叔叔节点的颜色以及它们的位置关系，分为以下几种情况：

   • 情况一：叔叔节点是红色：将父节点和叔叔节点着色为黑色，祖父节点着色为红色，然后将祖父节点作为新的当前节点，继续检查。

   • 情况二：叔叔节点是黑色，且当前节点是父节点的左孩子：此时要进行旋转来解决，单纯的变色已经不能解决问题了，以爷爷结点为基准右旋之后在变色

   • 情况三：叔叔节点是黑色，且当前节点是父节点的右孩子：此时要进行左右双旋转，具体参见代码

注：情况123均需要考虑u  p 还是p  u 的问题！！！ 

 代码显示：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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);//要是插入黑节点会导致性质5不符合，所以插红的cur->_col = RED;//考虑做左孩子还是右孩子if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;      //别忘了把_parent给到parent,否则下文的parent还是空！//由于我插入的结点必须为红，而红黑树又要求不能有两个连着的红结点//所以我们要判断一下父节点的颜色while (parent && parent->_col == RED){//父节点为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left)                    //parent为左孩子   {//   g                      黑// p   u                 红     红Node* uncle = grandfather->_right;// 叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;   //g和u都为红，那么一起变色就o而k之grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者存在且为黑//      g                  黑//   p     u            红    黑//c                  红if (cur == parent->_left){RotateR(grandfather);          //单纯变色无法解决，旋转一下parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//      cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;              //处理的是一个子树，这个符合了上面的也就Ok了}}     else                    //parent为右孩子{//   g                   黑// u   p             红      红Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者存在且为黑// // 旋转+变色//      g                  黑//   u     p            黑     红//             c       红if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g             黑//   u     p       黑     红//      c               红RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

3.3 遍历红黑树

 我们还是使用中序遍历遍历红黑树，代码如下：

	void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}

3.4 检查红黑树

 检查的方法很简单，就是通过随便跑一条路，数一下黑色节点，并将其作为参考值，之后在遍历整棵树，看看是不是每条路上的黑色节点数都是等于参考值的，换句话说，如果我们的树满足红黑树的性质，那么就o而k之,否则就不o而k之~

	// 前序递归遍历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 && 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);}bool IsBalanceTree(){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);}

3.5 代码测试

#include<iostream>
#include<vector>
using namespace std;#include"RBTree.h"// 测试代码
void TestRBTree1()
{RBTree<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.IsBalanceTree() << endl;
}void TestRBTree2()
{const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}RBTree<int, int> t;for (size_t i = 0; i < v.size(); ++i){t.Insert(make_pair(v[i], v[i]));}cout << t.IsBalanceTree() << endl;
}int main()
{TestRBTree1();TestRBTree2();return 0;
}

3.6 代码汇总

这里只放.h文件的！

#pragma once
#include<iostream>
#include<utility>
using namespace std;
// 枚举值表示颜色
enum color
{RED,BLACK
};
// 这里我们默认按key/value结构实现
template<class K,class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
template<class K,class V>
class RBTree
{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* parent = nullptr;Node* cur = _root;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);//要是插入黑节点会导致性质5不符合，所以插红的cur->_col = RED;//考虑做左孩子还是右孩子if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;      //别忘了把_parent给到parent,否则下文的parent还是空！//由于我插入的结点必须为红，而红黑树又要求不能有两个连着的红结点//所以我们要判断一下父节点的颜色while (parent && parent->_col == RED){//父节点为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left)                    //parent为左孩子   {//   g                      黑// p   u                 红     红Node* uncle = grandfather->_right;// 叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;   //g和u都为红，那么一起变色就o而k之grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者存在且为黑//      g                  黑//   p     u            红    黑//c                  红if (cur == parent->_left){RotateR(grandfather);          //单纯变色无法解决，旋转一下parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//      cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;              //处理的是一个子树，这个符合了上面的也就Ok了}}     else                    //parent为右孩子{//   g                   黑// u   p             红      红Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者存在且为黑// // 旋转+变色//      g                  黑//   u     p            黑     红//             c       红if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g             黑//   u     p       黑     红//      c               红RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;parent->_parent = subL;//if (parentParent == nullptr)if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}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;}}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}// 前序递归遍历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 && 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);}bool IsBalanceTree(){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;
};

四、总结及应用

在红黑树中，我们省去了ALV树的平衡因子，而换用颜色来判断树的平衡，这样使得代码的逻辑变得简单明了 ，后续我们对map和set的封装（实现mymap和myset)便会用到红黑树的思想与结构！

红黑树通过其自平衡的特性，确保了在插入、删除和查找操作中的高效性，使其成为许多实际应用中不可或缺的数据结构。