数据结构——红黑树
一、红黑树
1.红黑树的概念
红黑树是一种二叉搜索树，但在其每个节点上增加了一个存储位表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是近似平衡的。
2.红黑树的性质★
（1）每个节点不是红色就是黑色；
（2）根节点是黑色的；
（3）如果一个节点是红色的，则它的两个孩子节点是黑色的（即不存在两个相连的红色节点）；
（4）对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点；
（5）每个叶子节点都是黑色的（此处的叶子节点指的是空节点）。
3.红黑树节点的定义
enum Color{RED, BLACK};//节点颜色//约定value唯一
template<class T>
struct RBTreeNode {//节点定义RBTreeNode(const T& value = T(), Color color = RED): _left(nullptr), _right(nullptr), _parent(nullptr), _value(value), _color(color){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _value;Color _color;
};注意：节点颜色默认给红色
4.红黑树的结构
为了方便后续实现关联式容器，在红黑树的实现中加入一个头结点，因为根节点必须是黑色，为了与根节点进行区分，将头节点给定为红色，让根节点的_parent指针域指向头节点，，并且让头结点的_parent指针域指向红黑树根节点，_left指针域指向红黑树中最左侧节点，_right指针域指向红黑树中最右侧节点：
二、红黑树的操作
1.红黑树的插入
红黑树是在二叉搜索树的基础上加入了平衡限制条件，因此红黑树的插入可分为两步：
（1）按照二叉搜索树的方式进行插入新节点。
（2）检测新节点插入后，红黑树的性质是否被破坏：
因为新节点的默认颜色是红色，因此，若其双亲节点是黑色，则没有违法红黑树任何性质，此时不需要调整；若其双亲节点是红色，则违法了性质三不能有两个连在一起的红节点，此时就需要进行调整，调整需要分情况讨论：
约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
1.1 情况一
cur红，p红，g黑，u存在且为红
注意：此树可能是一棵完整的树，也可能是一棵子树。abcde可能为空，也可能是节点。
解决方法：
将p、u改为黑色，g改为红色，然后把g当成cur，若g是根节点则改回黑色，否则继续向上调整。
1.2 情况二
cur红，p红，g黑，u不存在/u黑
u的情况有两种：
（1）u节点不存在：则cur一定是新插入的节点，可根据性质判断出。
（2）u节点存在：则其一定是黑色，cur原先的颜色也一定是黑色，是由于cur子树的节点在调整时被调整成了红色，同样是可以根据性质判断出。
解决方法：
①p为g的左孩子，cur为p的左孩子，则进行右单旋；如图左
②p为g的右孩子，cur为p的右孩子，则进行左单旋；图左的对称图
③p改为黑色，g改为红色。
1.3 情况三
cur红，p红，g黑，u不存在/u黑
解决方法：
①p为g的左孩子，cur为p的右孩子，则针对p进行左单旋；如图
②p为g的右孩子，cur为p的左孩子，则针对p进行右单选；图为上图的对称图
③旋转后，如图就变成了情况二，再按照情况二进行调整即可。
2.红黑树的验证
红黑树的验证分为两步：
（1）验证其是否满足二叉搜索树，即中序遍历是否为有序序列。
（2）验证其是否满足红黑树的性质。
三、红黑树实现
1.代码实现
enum Color{RED, BLACK};//节点颜色template<class T>
struct RBTreeNode {//节点定义RBTreeNode(const T& value = T(), Color color = RED): _left(nullptr), _right(nullptr), _parent(nullptr), _value(value), _color(color){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _value;Color _color;
};//约定value唯一
template<class T>
class RBTree {typedef RBTreeNode<T> Node;
public:RBTree() {_head = new Node();_head->_left = _head;_head->_right = _head;}~RBTree() {Destroy(_head->_parent);delete _head;_head = nullptr;}//插入bool Insert(const T& value) {Node*& root = GetRoot();//1.按照二叉搜索树的方式插入if (root == nullptr) {//空树root = new Node(value, BLACK);root->_parent = _head;_head->_left = root;_head->_right = root;return true;}//查找插入位置Node* cur = root;Node* parent = cur->_parent;while (cur) {parent = cur;//保存其双亲if (value < cur->_value) {cur = cur->_left;}else if (value > cur->_value) {cur = cur->_right;}else {//已存在return false;}}//插入新节点cur = new Node(value);//默认插入节点为红色if (value < parent->_value) {parent->_left = cur;}else {parent->_right = cur;}cur->_parent = parent;//2.红黑树性质约束while (parent != _head && parent->_color == RED) {//两个红色相连违法规则Node* grandFather = parent->_parent;if (parent == grandFather->_left) {Node* uncle = grandFather->_right;//情况一：叔叔节点存在且为红if (uncle && uncle->_color == RED) {parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;//改变cur，继续向上调整cur = grandFather;parent = cur->_parent;}else {//情况二或三：叔叔节点为空，或叔叔节点存在且为黑//因为情况三可以调整为情况二，所有先处理情况三if (cur == parent->_right) {//将情况三转换为情况二RotateLeft(parent);std::swap(parent, cur);}//情况二parent->_color = BLACK;grandFather->_color = RED;RotateRight(grandFather);}}else {//三种情况的对称情况-->解决方法相同Node* uncle = grandFather->_left;if (uncle && uncle->_color == RED) {//情况一parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;//改变cur，继续向上调整cur = grandFather;parent = cur->_parent;}else {//情况二或三if (cur == parent->_left) {//情况三//调整为情况二RotateRight(parent);std::swap(cur, parent);}//情况二parent->_color = BLACK;grandFather->_color = RED;RotateLeft(grandFather);}}}//注意：最后根节点可能被调整为了红色，所以需要被改回黑色root->_color = BLACK;//3.更新头结点左右指针域--插入元素可能改变树的最值_head->_left = MostLeft();_head->_right = MostRight();return true;}//查找Node* Find(const T& value) {Node*& root = GetRoot();if (root == nullptr) return nullptr;Node* cur = root;while (cur) {if (value < cur->_value) {cur = cur->_left;}else if (value > cur->_value) {cur = cur->_right;}else {return cur;}}return nullptr;}//检测是否是红黑树bool IsRBTree() {Node* root = GetRoot();if (root == nullptr) return true;if (root->_color == RED) {//检测性质2std::cout << "FALSE: 根节点为红色！" << std::endl;return false;}int blackCount = 0;Node* cur = root;while (cur) {//统计一条路径黑色节点个数if (cur->_color == BLACK) ++blackCount;cur = cur->_left;}return _IsRBTree(root, blackCount, 0);}//中序遍历void InOrder() {_InOrder(GetRoot());std::cout << std::endl;}//获取最值int GetMax() {return MostRight()->_value;}int GetMin() {return MostLeft()->_value;}private://获取根节点Node*& GetRoot() {return _head->_parent;}//获取树的最值节点Node* MostLeft() {//最左侧节点Node*& root = GetRoot();if (root == nullptr) return _head;Node* cur = root;while (cur->_left) {cur = cur->_left;}return cur;}Node* MostRight() {//最右侧节点Node*& root = GetRoot();if (root == nullptr) return _head;Node* cur = root;while (cur->_right) {cur = cur->_right;}return cur;}//左单旋void RotateLeft(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) {//注意subrl可能为空subRL->_parent = parent;}subR->_left = parent;//跟新parent和subR的双亲节点//先保存好parent原先的双亲节点Node* pparent = parent->_parent;parent->_parent = subR;subR->_parent = pparent;//处理上层节点if (pparent == _head) {//已经更新到根节点_head->_parent = subR;}else {if (parent == pparent->_left) {pparent->_left = subR;}else {pparent->_right = subR;}}}//右单旋void RotateRight(Node* parent) {//其思想与左单旋相同Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) {subLR->_parent = parent;}subL->_right = parent;Node* pparent = parent->_parent;parent->_parent = subL;subL->_parent = pparent;if (pparent == _head) {_head->_parent = subL;}else {if (parent == pparent->_left) {pparent->_left = subL;}else {pparent->_right = subL;}}}//检测是否满足红黑树特性bool _IsRBTree(Node* root, const int blackNum, int count) {if (root == nullptr) return true;if (root->_color == BLACK) ++count;//统计路径内的黑色节点//检测是否满足性质3if (root->_parent != _head && root->_color == RED && root->_parent->_color == RED) {std::cout << "FALSE: 存在两个相连的红色节点！" << std::endl;return false;}if (root->_left == nullptr && root->_right == nullptr) {//是叶子节点，此路径统计结束return count == blackNum;//检测性质4}return _IsRBTree(root->_left, blackNum, count) && _IsRBTree(root->_right, blackNum, count);}//中序遍历void _InOrder(Node*& root) {if (root == nullptr) return;_InOrder(root->_left);std::cout << root->_value << " ";_InOrder(root->_right);}//销毁void Destroy(Node* root) {if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}
private:Node* _head;
};2.红黑树与AVL树的比较
红黑树与AVL树都是高效的平衡二叉树，增删改查时间复杂度都是O()，红黑树不追求绝对平衡，只需保证最长路径不超过最短路径的两倍即可，相对而言，降低了插入和旋转的次数，所以经常在增删改查的结构中性别比AVL树更好，且红黑树的实现相对来说更简单，实际运用中也更多。
