目录
红黑树的概念
红黑树的性质
红黑树节点的定义
红黑树的插入
1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏
红黑树的检测
红黑树的删除
红黑树和AVL树的比较
红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍，因而是接近平衡的。
红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？
红黑树节点的定义
//节点的颜色
enum Colour
{BLACK, RED
};//节点定义
template<class T>
struct RBTreenode
{ T _data; //储存的数据RBTreenode<T>* _left; //左孩子RBTreenode<T>* _right; //右孩子RBTreenode<T>* _parent; //父亲Colour _col; //颜色//构造函数RBTreenode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};再我们定义节点的时候，需要用一个枚举类型来定义我们的节点的颜色。然后还是三叉链，左孩子，右孩子，父亲。
红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点
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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first<cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new node(kv);if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;// ~~~~~~~~~~~~~~~~~~~~~~//判断颜色return true;
}2. 检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
情况一: cur为红，p为红，g为黑，u存在且为红
看到上图，cur插入的时候本身就为红，如果说它的父亲为红，叔叔存在且为红的话，我们就需要把p和u 变为黑，再让g 变为红，然后我们还需要向上更新，因为这幅图可能是一颗子树，它的祖先也需要更新颜色，如下图。
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
说明： u的情况有两种
1.如果u节点存在，则cur一定是新插入的节点，因为如果cur不是新插入的节点，则cur和p一定有一个的节点是黑色，就不满足性质4：每条路径黑色节点个数相同。
2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur由黑色变为了红色。
对于这种情况，我们就需要进行旋转了，对，没错，和AVL树里面的旋转操作是一样的，代码我就复制一下。
p为g的左孩子，cur为p的左孩子，则进行右单旋；
相反，p为g的右孩子，cur为p的右孩子，则进行左单旋。
我们在旋转完成之后，需要和上图一样，再把相应的颜色变换就行了。
右单旋：
void RotateR(node* parent)
{node* subL = parent->_left;node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}
}左单旋：
void RotateL(node* parent)
{node* subR = parent->_right;node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}
}情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑
像上面这种情况，我们就需要旋转两次，和AVL树的操作差不多。
p为g的左孩子，cur为p的右孩子，则对p进行左单旋；
相反，p为g的右孩子，cur为p的左孩子，则对p进行右单旋。
注意：这样它们就转化为了情况二，所以，我们再对它们进行情况二的右单旋或左单旋即可。旋转完之后，再修改它们的颜色即可。
我们在插入的时候，对每种情况进行相应的处理即可。
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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first<cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new node(kv);if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//判断颜色 ，变色while (parent&&parent->_col == RED){node* grandfather = parent->_parent;if (parent == grandfather->_left){// g//p unode* uncle = grandfather->_right;//叔叔存在且为红，只需变色，再向上更新即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑（旋转再变色）else{if (cur == parent->_left){// g// p u// cRotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g// p u// cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else //parent == grandfather->_right{// g// u pnode* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}_root->_col = BLACK;}return true;
}以上就是整个的插入代码。
红黑树的检测
红黑树的检测分为两步：
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质
中序遍历
void _Inorder(node* _root){if (_root == nullptr){return;}_Inorder(_root->_left);cout << _root->_kv.first << ":" << _root->_kv.second << endl;_Inorder(_root->_right);}检查
bool Check(node* _root, int blackNum, const int refNum)
{if (_root == nullptr){if (blackNum != refNum){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, refNum) && Check(_root->_right, blackNum, refNum);
}红黑树的删除
https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
删除操作我们只做了解就行了。
红黑树和AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红 黑树更多。
总代码
enum Colour
{BLACK,RED
};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), _col(RED){}};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 (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first<cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new node(kv);if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//判断颜色 ，变色while (parent&&parent->_col == RED){node* grandfather = parent->_parent;if (parent == grandfather->_left){// g//p unode* uncle = grandfather->_right;//叔叔存在且为红，只需变色，再向上更新即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑（旋转再变色）else{if (cur == parent->_left){// g// p u// cRotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g// p u// cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else //parent == grandfather->_right{// g// u pnode* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}_root->_col = BLACK;}return true;}void RotateR(node* parent){node* subL = parent->_left;node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}}void RotateL(node* parent){node* subR = parent->_right;node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void Inorder(){_Inorder(_root);cout << endl;}int size(){return _size(_root);}int height(){return _height(_root);}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 (blackNum != refNum){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, refNum) && Check(_root->_right, blackNum, refNum);}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;}int _size(node*_root){if (_root == nullptr)return 0;return _size(_root->_left) + _size(_root->_right) + 1;}void _Inorder(node* _root){if (_root == nullptr){return;}_Inorder(_root->_left);cout << _root->_kv.first << ":" << _root->_kv.second << endl;_Inorder(_root->_right);}node* _root=nullptr;};我们后面还会用红黑树来模拟实现map和set。
