数据结构——红黑树

一.红黑树的定义

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

红黑树的性质：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

解读：

性质三：保证树中没有连续的红色节点

性质四：每条路径上黑色节点的数目相同

满足以上性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍

其中，其极限最短：全黑。极限最长：一黑一红……

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

二.红黑树的插入

1.红黑树节点的定义

enum Colour
{Red,Black
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode():_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv){}
};

2.红黑树的插入操作

插入步骤：

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

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

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

   • 情况一: cur为红，p为红，g为黑，u存在且为红
     
     解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

   • 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
     

   解决方式：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转。p、g变色–p变黑，g变红

   • 情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑
     
     解决方式：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

3.总结：

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

1. 叔叔存在且为红，变色，向上调整（可能变为三种情况中的任意一种)
2. 叔叔不存在/存在且为黑，直线。单旋+变色
3. 叔叔不存在/存在且为黑，折线，两次单旋+变色

三.红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($lo{g}_{2}N$)

红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

四.检验手写的红黑树

//检查有没有连续红节点
bool Check(Node* root,int blackNum,const int ref)
{if (root == nullptr){if (blackNum != ref){cout << "路径上黑节点数量不一致" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则，父子均为红" << endl;return false;}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 != nullptr){if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root,0,ref);
}

五.源码

namespace dianxia
{enum Colour{Red,Black};template<class K,class V>struct RBTreeNode{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;  //节点颜色RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}};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;}else{parent->_left = cur;}cur->_parent = parent;//检查是否满足红黑树的要求while (parent && parent->_col == Red){//p为红则gp一定存在且为黑Node* grandparent = parent->_parent;assert(grandparent);assert(grandparent->_col==Black);if (parent == grandparent->_left){Node* uncle = grandparent->_right;//1.u存在且为红，变色并继续向上更新if (uncle && uncle->_col == Red){parent->_col = uncle->_col = Black;grandparent->_col = Red;cur = grandparent;parent = cur->_parent;}//2.u不存在或u为黑  变色加旋转else{if (cur == parent->_left){//	    g//    p   u//  c//右旋RotateR(grandparent);parent->_col = Black;grandparent->_col = Red;}else{//		g//	  p	  u//		c//先左旋再右旋RotateL(parent);RotateR(grandparent);cur->_col = Black;grandparent->_col = Red;}break;}}else //grandparent->_right==parent{Node* uncle = grandparent->_left;//1.u存在且为红，变色并继续向上更新if (uncle && uncle->_col == Red){parent->_col = uncle->_col = Black;grandparent->_col = Red;cur = grandparent;parent = cur->_parent;}//2.u不存在或u为黑  变色加旋转else{if (cur == parent->_right){//	    g//    u   p//		    c//左RotateL(grandparent);parent->_col = Black;grandparent->_col = Red;}else{//		g//	  u	  p//		c//先右旋再左旋RotateR(parent);RotateL(grandparent);cur->_col = Black;grandparent->_col = Red;}break;}}}_root->_col = Black;return true;}~RBTree(){_Destroy(_root);_root = nullptr;}void Inorder(){_InOrder(_root);}//检查红黑树：1.检查以根节点为根的每条路径黑色节点的数目是否都相等//			2.检查某条路径上是否有连续的红色节点bool Isbalance(){if (_root && _root->_col == Red){cout << "根节点是红色的" << endl;return false;}int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == Black)++benchmark;cur = cur->_left;}return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}int _Height(Node* root){if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}bool _Check(Node* root, int blacknum, int benchmark){if (root == nullptr){if (benchmark != blacknum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == Black)++blacknum;if (root->_col == Red && root->_parent && root->_parent->_col == Red){cout << "某条路径存在连续的红色节点" << endl;return false;}return _Check(root->_left, blacknum, benchmark)&& _Check(root->_right, blacknum, benchmark);}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;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}private:Node* _root = nullptr;};
}

---

本文到此结束，码文不易，还请多多支持！！