红黑树(C++)

写在前面

在上篇文章中，我们实现了AVL树，AVL树是一种高度平衡的二叉搜索树。通过确保任何节点的左右子树的高度差不超过1，AVL树能够维持严格的平衡状态。然而，严格平衡的代价是某些插入和删除操作可能需要多次旋转。

本篇文章将实现红黑树，它是一种近似平衡的二叉搜索树。红黑树通过维持某些性质来保持树的平衡。通过这些性质，红黑树确保从根到叶子的所有路径中，最长路径不超过最短路径的两倍，从而实现近似平衡。这种近似平衡比AVL树的严格平衡稍松一些，使得它在某些插入和删除操作中的效率更高，因为它需要的旋转次数较少。

在接下来的内容中，我们将详细介绍红黑树的实现过程，以及它是如何通过旋转和重新着色来维护红黑树的平衡性。

1. 红黑树的概念及性质

1. 1 红黑树的概念

红黑树，是一种二叉搜索树，其每个节点存储一个额外的颜色位，用于确保树的平衡性。在红黑树中，节点的颜色可以是红色或黑色。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

1. 2 红黑树的性质

红黑树通过以下性质来保持树的平衡：

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

2. 根节点是黑色。

3. 每个叶子节点（NIL节点）是黑色。
   ps：NIL节点不是传统意义上的叶子节点，而是指空节点，是用来方便我们来数路径的。
   

4. 如果一个节点是红色，则它的两个子节点都是黑色（不能出现连续的红色节点）。

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

为什么满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍？
分析如下：

2. 红黑树节点的定义

TreeNode成员的几点解释：

1. 枚举类型 Color 用于表示红黑树节点的颜色。红黑树节点只能是红色或黑色。
2. TreeNode 是一个模板结构体，用于存储红黑树节点的信息。
   _left 指向左孩子节点，_right 指向右孩子节点，_parent 指向父节点。
   _kv 存储节点的键值对，类型为 pair<K, V>，其中 K 是键的类型，V 是值的类型。
   _col 存储节点的颜色，类型为 Color。
   构造函数初始化节点的左孩子、右孩子和父节点为空指针，键值对通过参数传递进来，并将节点颜色初始化为红色（新插入的节点默认是红色）。

enum Color
{RED,BLACK
};
template<class K, class V>
struct TreeNode
{TreeNode* _left; // 左孩子节点TreeNode* _right;// 右孩子节点TreeNode* _parent;// 父节点pair<K, V> _kv;// 存储键值对Color _col;  // 节点颜色// 构造函数TreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)// 新插入的节点初始为红色{}
};

3. 红黑树的插入

红黑树就是在二叉搜索树的基础上增加了节点的颜色来控制平衡，因此红黑树也可以看成是二叉搜索树。那么红黑树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点。
2. 检测新节点插入后，红黑树的性质是否造到破坏。

具体操作步骤如下：

3.1 按照二叉搜索的树规则插入新节点

具体操作过程参考之前写的文章，这里就不在赘述，详情参考之前写的这篇文章：搜索二叉树，这里直接给出插入新节点的具体代码。

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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}//插入cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;cur->_parent = parent;}else{cur->_parent = parent;parent->_left = cur;}
}

3.2 检测新节点插入后，红黑树的性质是否造到破坏

这里涉及的旋转操作参考之前写的文章AVL树（C++），里面详细介绍了旋转操作，这里就不在赘述。
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；
注意：下面图片中的树有可能是一颗完整的树，也有可能是一颗局部的子树。

但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
ps:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

• 情况一: cur为红，p为红，g为黑，u存在且为红。
  
  ps:cur可能是新插入的节点，也有可能是在下面插入节点，不断往上调整，使得cur的颜色变红。

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

ps:如果g是根节点，调整完成后，需要将g改为黑色;
如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整。

• 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
  解决方式：
  cur是p的左孩子，以g为旋转点右单旋，g变红，p变黑，调整结束，无需向上调整；
  cur是p的右孩子，先以p为旋转点左单旋，再以g为旋转点右单旋，g变红，p变黑，调整结束，无需向上调整。
  

1. 如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。

2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

p有可能是g的右孩子，这种情况下旋转操作与上面的情况相反，变色操作还是一样的，这里就不在赘述了。
如下图：

检测新节点插入后，红黑树的性质是否造到破坏的具体代码如下：

//插入以后判断是否满足红黑树的规则
//不满足则调整
while (parent && parent->_col == RED)
{Node* grandfather = parent->_parent;//p是g的左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;//u存在且为红if (uncle && uncle->_col == RED){//变色+向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else{//不存在或者存在且为黑//旋转+变色//cur 是p的左 以g为旋转点右单旋if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//cur 是p的右 先以p为旋转点左单旋，再以g为旋转点右单旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//p是g的右孩子{Node* uncle = grandfather->_left;//u存在且为红if (uncle && uncle->_col == RED){//变色+向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else{//不存在或者存在且为黑//旋转+变色//cur 是p的右 以g为旋转点左单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//cur 是p的左 先以p为旋转点右单旋，再以g为旋转点左单旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}
}
_root->_col = BLACK;

4.红黑树的删除

红黑树的删除和AVL树一样不做深入研究，实现红黑树的插入已经足够帮助我们来了解其是如何控制平衡的，关于红黑树的删除有兴趣的可参考：《算法导论》或者《STL源码剖析》。

5.红黑树的验证

红黑树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证红黑树，可以分两步：

1. 检测其是否满足二叉搜索树
   如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
   代码如下：

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

2. 检测其是否满足红黑树的性质
   不能出现连续的红色节点；每条路径上的黑色节点数量相同。

bool _IsRbTree(Node* root, int blacknum, int num)
{if (root == nullptr){//判断当前路径和最左路径上的黑色节点数量是否相同if (blacknum != num)return false;return true;}//当前节点为黑色，当前路径上的黑色节点数量加1if (root->_col == BLACK) num++;Node* parent = root->_parent;//判断是否出现连续的红色节点if (root->_col == RED && parent->_col == RED){cout << "出现连续的红色节点";return false;}//递归去判断其左右子树是否满足性质return _IsRbTree(root->_left, blacknum, num)&& _IsRbTree(root->_right, blacknum, num);
}
bool IsRbTree()
{//空树是红黑树if (_root == nullptr) return true;if (_root->_col == RED) return false;//检查根节点的颜色//统计最左路径黑色节点的数量，以其为参考值，去判断每条路径上的黑色节点数量是否相同int blacknum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){blacknum++;}cur = cur->_left;}return _IsRbTree(_root, blacknum, 0);
}

验证用例：
常规场景1 ：{16, 3, 7, 11, 9, 26, 18, 14, 15}。

特殊场景2：{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}。

场景三：随机生成N个数字插入验证，这里给出代码，有兴趣的可以自己去测试一下。

int main()
{const int N = 1000;srand((unsigned int)time(nullptr));RBTree<int, int> rbTree;for (int i = 0; i < N; ++i){int num = rand() + i;rbTree.insert(make_pair(num, num));}//rbTree.InOrder();cout << rbTree.IsRbTree();return 0;
}

6.源码

#include <iostream>
using namespace std;
enum Color
{RED,BLACK
};
template<class K, class V>
struct TreeNode
{TreeNode* _left;TreeNode* _right;TreeNode* _parent;pair<K, V> _kv;Color _col;TreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K, class V>
class RBTree
{typedef TreeNode<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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}//插入cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;cur->_parent = parent;}else{cur->_parent = parent;parent->_left = cur;}//插入以后判断是否满足红黑树的规则//不满足则调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else{if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsRbTree(){if (_root == nullptr) return true;if (_root->_col == RED) return false;int blacknum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){blacknum++;}cur = cur->_left;}return _IsRbTree(_root, blacknum, 0);}
private:bool _IsRbTree(Node* root, int blacknum, int num){if (root == nullptr){if (blacknum != num)return false;return true;}if (root->_col == BLACK) num++;Node* parent = root->_parent;if (root->_col == RED && parent->_col == RED){cout << "出现连续的红色节点";return false;}return _IsRbTree(root->_left, blacknum, num)&& _IsRbTree(root->_right, blacknum, num);}void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_kv.first << ' ';_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//旋转，sub的右子树做parent的左子树//parent做subL的右子树parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;//parent为根节点，需要将根节点更新为subR if (parent == _root){_root = subR;subR->_parent = nullptr;}else{//更新subR的父节点指针if (subR->_kv.first > pParent->_kv.first){pParent->_right = subR;}else{pParent->_left = subR;}subR->_parent = pParent;}}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 (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (subL->_kv.first > pParent->_kv.first){pParent->_right = subL;}else{pParent->_left = subL;}subL->_parent = pParent;}}
private:Node* _root = nullptr;
};#include "RBTree.h"
int main()
{RBTree<int, int> rbTree;int nums[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : nums){rbTree.insert(make_pair(e, e));}rbTree.InOrder();cout << rbTree.IsRbTree() << endl;return 0;
}

至此，本片文章就结束了，若本篇内容对您有所帮助，请三连点赞，关注，收藏支持下。

创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！

如果本篇博客有任何错误，请批评指教，不胜感激 ！！！