【C++】红黑树的模拟实现

🌇个人主页：平凡的小苏
📚学习格言：命运给你一个低的起点，是想看你精彩的翻盘，而不是让你自甘堕落，脚下的路虽然难走，但我还能走，比起向阳而生，我更想尝试逆风翻盘。
🛸C++专栏：C++内功修炼基地
> 家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问，感谢你们的转发！ 关注我，关注我，关注我，你们将会看到更多的优质内容！！

一、红黑树的概念

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

二、红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的

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

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

   最优情况：全黑或每条路径都是一黑一红的满二叉树，高度logN

   最差情况：每颗子树左子树全黑，右子树一黑一红。高度2*logN。

   可以发现，最坏情况的时间复杂度和AVL树一样，都是O(logN)，但是红黑树这种近似平衡的结构减少了大量旋转，综合性能优于AVL树。

注：第三点的意思就是，没有连续的红色节点进行连接

三、红黑树的定义

enum Color
{RED,BLACK
};
template<class K, class V>
struct RedBlackTreeNode
{pair<K, V> _kv;RedBlackTreeNode<K, V>* _left;//该节点的左孩子RedBlackTreeNode<K, V>* _right;//该节点的右孩子RedBlackTreeNode<K, V>* _parent;//该节点是父亲节点Color _col;//颜色RedBlackTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_col(RED){}
};

思考：在节点的定义中，为什么要将节点的默认颜色给为红色的而不是黑色？

因为给成红色就会和红黑树的性质3冲突，而给成黑色就会和红黑树的性质4冲突那么对于冲突性质3比性质4更优，因为冲突性质4，不管插入哪个位置，都会引起颜色的变换或者旋转。而冲突性质3有可能会引起改变，也可能不改变

四、红黑树的插入（主要看叔叔的颜色）

1.情况一：uncle存在且节点颜色为红

这种情况cur、parent、grandfather都是确定颜色的，唯独uncle的颜色是不确定的。

2.情况二：uncle不存在或者uncle存在且节点为黑（直线）

uncle不存在示例图：

uncle存在且为黑的情况示例图：

---

3.情况三：uncle不存在/存在并且为黑（折线）

uncle的情况分两种。

uncle不存在，则cur为插入节点，两次单旋即可。

uncle存在且为黑示例图

4.总结

插入新节点时，父节点为红，看叔叔的颜色。

​ 1、叔叔存在且为红，变色，向上调整（可能变为三种情况中的任意一种）

​ 2、叔叔不存在/存在且为黑，直线。单旋+变色

​ 3、叔叔不存在/存在且为黑，折线，两次单旋+变色

五、红黑树的插入代码

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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// ... 控制平衡while (parent && parent->_col == RED)//parent不为空并且为红进循环{Node* grandfather = parent->_parent;if (grandfather->_left == parent){if (parent->_left == cur){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//叔叔节点为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}}else{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在并且叔叔节点为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}}else{if (parent->_right == cur){Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//叔叔节点为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateL(grandfather);parent->_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 = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}}}_root->_col = BLACK;//处理根一直为黑的情况return true;}

六、红黑树代码是否正确的代码检测

bool checkColour(Node* root, int blacknum, int beachmark){if (root == nullptr){if (blacknum != beachmark)//和基准值比较，如果不相等，则红黑树代码出错{return false;}return true;}if (root->_col == BLACK)//记录黑色节点数量{++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return checkColour(root->_left, blacknum, beachmark) && checkColour(root->_right, blacknum, beachmark);}bool _IsBalance(Node* root){if (root == nullptr){return true;}if (root->_col != BLACK)//根节点不为黑，不符合红黑树的性质{return false;}//基准值int beanchmark = 0;Node* cur = root;while (cur)//求一条路径的黑色节点的数量作为基准值{if (cur->_col == BLACK){++beanchmark;}cur = cur->_left;}return checkColour(root, 0, beanchmark);}

详看代码注释

七、红黑树的整体代码

#include <iostream>
#include <cassert>
using namespace std;template<class K, class V>
class RedBlackTree
{typedef RedBlackTreeNode<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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// ... 控制平衡while (parent && parent->_col == RED)//parent不为空并且为红进循环{Node* grandfather = parent->_parent;if (grandfather->_left == parent){if (parent->_left == cur){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//叔叔节点为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}}else{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在并且叔叔节点为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}}else{if (parent->_right == cur){Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//叔叔节点为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateL(grandfather);parent->_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 = cur->_parent;}else //叔叔节点为空或者为黑的情况{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}}}_root->_col = BLACK;//处理根一直为黑的情况return true;}bool IsBalance(){return _IsBalance(_root);}
private:bool checkColour(Node* root, int blacknum, int beachmark){if (root == nullptr){if (blacknum != beachmark){return false;}return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return checkColour(root->_left, blacknum, beachmark) && checkColour(root->_right, blacknum, beachmark);}bool _IsBalance(Node* root){if (root == nullptr){return true;}if (root->_col != BLACK){return false;}//基准值int beanchmark = 0;Node* cur = root;while (cur){if (cur->_col == BLACK){++beanchmark;}cur = cur->_left;}return checkColour(root, 0, beanchmark);}void RotateR(Node* parent){Node* cur = parent->_left;Node* curRight = cur->_right;parent->_left = curRight;cur->_right = parent;Node* ppNode = parent->_parent;if (curRight){curRight->_parent = parent;}parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = cur;}else{ppNode->_right = cur;}cur->_parent = ppNode;}}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft)//判断是否为空，空的话就不用接上父亲节点{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}
private:Node* _root = nullptr;
};