1.红黑树的概念
红黑树是一颗二叉搜索树，他的每个节点增加一个存储位来表示节点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的
1.1红黑树的规则
1.每个结点不是红色就是黑色
2.根结点是黑色的
3.如果一个结点是红色的，则它的两个孩子结点必定是黑色的，也就是说，任意一条路径不会有连续的红色结点
4.对于任意一个结点，从该结点到其所有的NULL结点的简单路径上，均包含相同数量的黑色结点
2.2.1红黑树插入过程
1.插入值按二叉搜索树规则进行插入，插入后我们观察是否符合红黑树四条规则
2.如果是空树插入，新增结点是黑色结点，如果是非空树插入，新增结点必定是红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4难以维护
3.非空树插入后，新增结点必须是红色结点，如果父亲结点是黑色的，则没有违法任何规则，插入结束
4.非空树插入后，新增结点必须是红色结点，如果父亲结点是红色的，违反规则3，处理办法由下图分析
2.2.2情况一：变色
c为红（图有点问题），p为红，g为黑，u存在且为红，则将g变为红，p和u都变为黑色，此时会出现一个问题，g的父节点是什么颜色的？我们是不能确认的，所以把g当成新的c，继续往上更新
2.2.3情况二：单旋+变色
c为红，p为红，g为黑，u不存在或者u存在且为黑
u不存在时，c为新增结点
if (cur == parent->_left) { RotateR(grandf); parent->_col = BLACK; grandf->_col = RED; }u存在且为黑色时，c不为新增结点，是grandfather转换来的，因为如果是新增结点，那么在新增之前构不成红黑树
2.2.4情况三：双旋+变色
同上，但是区别就是，c和p的相对位置不同，当为同侧时就是单旋+变色，当是异侧时，就是双旋+变色
同侧 异侧
g g g g
p u u p p u p u
c c c c
简单理解就是直线和折线形
全部代码实现
#pragma once #include<iostream> using namespace std; enum Colour { RED, BLACK }; template<class K,class V> struct RBTreeNode { pair<K,V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K,V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) { } }; template<class K,class V> class RBTree { using Node= RBTreeNode<K, V>; 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->_parent = parent; cur->_col = RED; if (parent->_kv.first < cur->_kv.first) { parent->_right = cur; } else { parent->_left = cur; } //父亲是红色，出现连续红色结点，需要处理 while(parent && parent->_col == RED) { Node* grandf = parent->_parent; if (grandf->_left == parent) { Node* uncle = grandf->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandf->_col = RED; //继续往上处理 cur = grandf; parent = parent->_parent; } else { //这个时候就要进行旋转+变色 if (cur == parent->_left) { // g // p u //c RotateR(grandf); parent->_col = BLACK; grandf->_col = RED; break; } else { // g // p u // c //cur在parent左边的时候 RotateL(parent); RotateR(grandf); cur->_col = BLACK; grandf->_col = RED; break; } } } else { Node* uncle = grandf->_left; if (uncle && uncle->_col == RED) { // g // u p // c parent->_col = uncle->_col = BLACK; grandf->_col = RED; cur = grandf; parent = cur->_parent; } else { if (cur == parent->_right) { RotateL(grandf); parent->_col = BLACK; grandf->_col = RED; } else { // g // u p // c RotateR(parent); RotateL(grandf); cur->_col = BLACK; grandf->_col = RED; } break; } } } _root->_col = BLACK; return true; } //右旋 void RotateR(Node* parent) { if (parent == nullptr || parent->_left == nullptr) { return; } Node* subL = parent->_left; Node* subLR = subL->_right; if (subLR) { subLR->_parent = parent; } parent->_left = subLR; subL->_right = parent; Node* pParent = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; _root->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subL; } else { pParent->_right = subL; } subL->_parent = pParent; } } //左旋 void RotateL(Node* parent) { if (parent == nullptr || parent->_right == nullptr) { return; } Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } Node* pParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (pParent == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (parent == pParent->_left) { pParent->_left = subR; } else { pParent->_right = subR; } subR->_parent = pParent; } } //中序遍历 void InOrder() { _InOrder(_root); cout << endl; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return nullptr; } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) { return false; } int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { refNum++; } cur = cur->_left; } return Check(_root, 0, refNum); } private: bool Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { if (refNum != blackNum) { cout << "存在黑色结点数量不相等的路径" << endl; return false; } return true; } if (root->_parent != nullptr && root->_col == RED && root->_parent->_col == RED) { cout << "存在连续的红色结点" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNUum) && Check(root->_right, blackNum, refNum); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } private: Node* _root = nullptr; };
