【C++】RBTree——红黑树

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的 。（既最长路径长度不超过最短路径长度的 2 倍）

ps:树的路径是从根节点走到空节点（此处为NIL 节点）才算一条路径

二、红黑树的性质

• 每个结点不是红色就是黑色

• 根结点是黑色的

• 如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的红色结点）

• 对于每个结点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

• 每个叶子结点都是黑色的（此处的叶子结点指的是空节点,NIL节点），如果是空树，空节点也是黑色，符合第一个性质

理解最长路径长度不超过最短路径长度的 2 倍：

根据第三个性质：红黑树不会出现连续的红色结点，根据第四个性质：从每个结点到所有后代结点的路径上包含相同数目的黑色结点。

极端场景：最短路径上全黑，一条路径黑色节点的数量，最长路径上是一黑一红相间的路径

---

三、红黑树节点的定义

三叉链结构，对比AVL数节点的定义，把平衡因子替换成节点颜色，采用枚举的方式：

//结点颜色
enum Color
{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;Color _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};

这里可以清楚的看到，构造结点时默认设置为红色,问题来了：

如果插入的是黑色结点那就是不符合第四个性质（路径上均包含相同的黑色结点），此时我们必须要去进行维护每条路径的黑色结点

如果插入的是红色结点那就是不符合第三个性质（没有出现连续的红色结点），但是我们并不一定需要调整，如果根刚好为黑色，就不需要进行调整。

所以如果插入为红色结点，不一定会破坏结构，但是如果插入黑色结点我们就必须去进行维护了

---

四、红黑树的插入

红黑树插入的操作部分和AVL树的插入一样：

• 找到待插入位置
• 将待插入结点插入到树中
• 调整：若插入结点的父结点是红色的，我们就需要对红黑树进行调整

前两步大差不差

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

关键在于对红黑树进行调整：为了能够展示出各种情况，这里有一个基本的模型：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红 :

cur为红，p为红，g为黑，u存在且为红

关键看u结点，根结点的颜色为黑色，不能有连续的红色结点，所以上面的情况已经出现连续的红色结点了，此时我们需要进行调整：

把p结点改为黑色，同时把u结点也改为黑色（符合性质四：每条路径上的黑色节点数量相同），最后在把g结点改为红色；如果g是子树的话，g一定会有双亲，为了维持每条路径上黑色节点的数量，g必须变红，不然会多出一个黑色节点，在把g结点当做cur结点继续往上调整，当g为根结点时，在把g置为黑色：

代码实现：

      while (parent && parent->_col == RED){Node* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;//情况一：u存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;parent = cur->_parent;}else//其他情况{}}else//parent==grandfater->_right{Node* uncle = grandfater->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;parent = cur->_parent;}else{}}}_root->_col = BLACK;

情况二：cur为红，p为红，g为黑，u不存在/u为黑，gpc在同一侧：

此时u的情况：

如果u结点不存在，则cur一定是新增结点，因为如果cur不是新增结点：则cur和p一定有一个节点时黑色，就不满足每条路径都有相同的黑色结点的性质。

如果u结点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色，在其子树调整过程中变为了红色

如果p为g的左孩子，cur为p的左孩子，则进行右单旋转；

如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，

同时，p、g变色–p变黑，g变红

以下情况：u不存在，cur为新增节点，进行右单旋：

以下情况：u结点存在且为黑：

情况三: cur为红，p为红，g为黑，u不存在/u为黑，gpc不在同一侧:

这时候我们就需要进行双旋了：

p为g的左孩子，cur为p的右孩子，对p做左单旋转；
p为g的右孩子，cur为p的左孩子，对p做右单旋转;
旋转之后则转换成了情况2，在继续进行调整即可

---

五、代码实现

送上源码：

#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
enum Color
{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;Color _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;//情况一：u存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;//向上调整cur = grandfater;parent = cur->_parent;}else{//情况2if (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}//情况3else{//       g//  p//    c RotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else//parent==grandfater->_right{Node* uncle = grandfater->_left;//情况1：u存在且为红色if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfater->_col = RED;//向上调整cur = grandfater;parent = cur->_parent;}else{//情况2：u不存在/u存在为黑色//g//    p//        cif (cur == parent->_right){RotateL(grandfater);grandfater->_col = RED;parent->_col = BLACK;}//情况3//     g//         p//      celse{RotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}//根变黑_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subL;subL->_right = parent;if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool Check(Node*root,int blackNum,int ref){if (root == nullptr){//cout << blackNum << endl;if (blackNum != ref){cout << "违反规则：本条路径的黑色结点的数量根最左路径不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则：出现连续的红色结点" << endl;return false;}if (root->_col == BLACK){++blackNum;}return Check(root->_left,blackNum,ref)&& Check(root->_right,blackNum,ref);}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col != BLACK){return false;}int ref = 0;Node* left = _root;while (left){if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root,0,ref);}
private:Node* _root = nullptr;
};void TestRBTree1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsBalance() << endl;
}void TestRBTree2()
{srand(time(0));const size_t N = 100000;RBTree<int, int> t;for (size_t i = 0; i < N; i++){size_t x = rand();t.Insert(make_pair(x, x));}cout << t.IsBalance() << endl;}

---

本篇结束…