RB-tree(红黑树)
红黑树的规则如下：
1.每个节点不是红色就是黑色
2.根节点为黑色
3.如果节点为红色，那么它的子节点必须为黑色
4.任何一个节点到NULL（树的尾端）的任何路径所包含的黑节点个数相同
简而言之就是每个路径的黑色节点数量相同
新增的节点必须为红，因为增加红色节点所要付出的代价会比黑色的要小很多，如果新增节点为黑色，那么就会打破第四条规则，整棵树都要调整，代价是相当之大的
红黑树节点的定义
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) {} };
红黑树的插入操作
红黑树的插入操作分为几种情况
情况一：
当cur为红、parent为红、grandparent为黑、uncle存在并且为红
操作过程：
将parent和uncle全部染成黑色，grandparent染成红色，然后把cur给grandparent继续向上判断，如果cur的parent依旧为红色，那么就要继续染色，如果cur为_root了，将根节点染成黑色。
具象图：
抽象图：
在抽象图当中，在a或者b子树当中触发了染色机制，然后一路染色上来，一直到cur也染成了红色，cur和p就造成冲突，需要继续染色。
情况二：
当cur为红，p为红，g黑，u不存在/u为黑
操作：
p为g的左孩子，cur为p的左孩子，则进行右单旋转；
相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转
最后p变为黑色，cur和g变为红色
具象图：
当uncle为空的时候
抽象图：
情况三：
当cur和p为红，g为黑，u为黑/不存在
如果parent为grandparent的左儿子，对parent左旋，再对grandparent右旋
如果parent为grandparent的右儿子，对parent右旋，再对grandparent左旋
cur染为黑色，cur和grandparent染为红色。
具象图：
抽象图：
红黑树+测试代码
#pragma once #include"AVLTree.h" 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) { //如果父亲节点的颜色为红色，那么就有可能需要改变颜色或者旋转 Node* grandparent = parent->_parent; assert(grandparent); assert(grandparent->_col == Black);//父亲为红色，那么祖父一定为黑色，不然之前的插入就存在问题 if (parent == grandparent->_left) { Node* uncle = grandparent->_right; //情况一，uncle存在并且uncle为红色，就要继续往上染色 if (uncle && uncle->_col == Red) { parent->_col = uncle->_col = Black; grandparent->_col = Red; cur = grandparent; parent = cur->_parent; } else { //uncle不存在或者uncle为黑色就会走到这里 //情况二+情况三 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; parent->_col = grandparent->_col = Red; } break; } } else { Node* uncle = grandparent->_left; if (uncle && uncle->_col == Red) { parent->_col = uncle->_col = Black; grandparent->_col = Red; cur = grandparent; parent = cur->_parent; } else { if (cur == parent->_right) { RotateL(grandparent); parent->_col = Black; grandparent->_col = Red; } else { RotateR(parent); RotateL(grandparent); cur->_col = Black; grandparent->_col = Red; } break; } } } _root->_col = Black; return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == Red) { cout << "根节点不是黑色" << endl; return false; } // 黑色节点数量基准值 int benchmark = 0; Node* cur = _root; while (cur) { if (cur->_col == Black) ++benchmark; cur = cur->_left; } return PrevCheck(_root, 0, benchmark); } private: bool PrevCheck(Node* root, int blackNum, int& benchmark) { if (root == nullptr) { if (blackNum != benchmark) { cout << "某条黑色节点的数量不相等" << endl; return false; } else { return true; } } if (root->_col == Black) { ++blackNum; } if (root->_col == Red && root->_parent->_col == Red) { cout << "存在连续的红色节点" << endl; return false; } return PrevCheck(root->_left, blackNum, benchmark) && PrevCheck(root->_right, blackNum, benchmark); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* pparent = parent->_parent; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) { pparent->_left = subR; } else { pparent->_right = subR;; } subR->_parent = pparent; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; Node* pparent = parent->_parent; //防止空指针 if (subLR) { subLR->_parent = parent; } subL->_right = parent; parent->_parent = subL; if (parent == _root) { //如果parent就是根节点 _root = subL; subL->_parent = nullptr; } else { //如果parent只是一颗子树的根节点，就还需要连接好parent //判断是左还是右节点 if (pparent->_left == parent) { pparent->_left = subL; } else { pparent->_right = subL; } subL->_parent = pparent; } } Node* _root = nullptr; }; void TestRBTree2() { size_t N = 1000; srand(time(0)); RBTree<int, int> t1; for (size_t i = 0; i < N; ++i) { int x = rand(); cout << "Insert:" << x << ":" << i << endl; t1.Insert(make_pair(x, i)); } cout << "IsBalance:" << t1.IsBalance() << endl; }
运行结果：
