1.红黑树概念
红黑树是一种搜索二叉树，但在每个结点上增加一个储存位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其它路径长俩倍，因而是接近平衡的。
2.红黑树的效率
假设N是红黑树结点数量，h是最短路径的长度，那么2^h-1<=N<2^2*h-1(左右可以看成俩个完全二叉树)，由此推出h=logN，所以复杂度为O(logN)
3.红黑树的性质
1.每个结点不是红色就是黑色
2.根结点是黑色
3.如果一个结点为红色，则俩个子孩子是黑色
4.对于每个结点，从该结点到其所有后代结点的简单路径上含有相同数目的黑色结点
5.每个叶子结点都是黑色
如果一条路径为全黑结点有x个，那么最长的也是有x个黑结点，而红色是下面要接黑，所以一黑一红，那么红色也是x个，那么最长就是2x，不会超过这个。
4.红黑树结点的定义
枚举定义红色黑色，每个结点都有三个指针，并且有一个键值对。
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){}};5.颜色处理
情况1：变色
c为红，p为红，u存在且为红，则将p和u变黑，g变红。在把g当成新的c继续往上更新。
分析:因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加一个黑色结点，再把g变红色，相当于保持g所在的子树黑色结点数量不变，还需要判断是否往上更新，因为g是红色，如果g的父节点也是红色，就还需要继续处理，如果g的父节点是黑色就结束，最后如果g是整棵树的根，就要变化黑色。
情况2：单旋+变色
c为红色，p为红色，g为黑色，u不存在或者为黑色，u不存在，c一定是新增结点，u存在且为黑，则c一定不是新增结点，c之前是黑色，是在c的子树插入的结点，因为子树更新而变成红色
分析：p必须变黑色解决连续红色，还需要旋转。
旋转后根结点的左右结点都变红色，根节点变为黑色。
情况3：双旋+变色
c为红色，p为红色，g为黑色，u不存在或者为黑色，u不存在，c一定是新增结点，u存在且为黑，则c一定不是新增结点，c之前是黑色，是在c的子树插入的结点，因为子树更新而变成红色
p的右边是c需要向单旋变成纯粹一边高，然后再单旋一次就平衡。
6.红黑树的插入操作
第一步是找到要插在哪一个地方，找到地方后创建新结点，通过比较键值来确定是在左还是右边，插入完成后就要开始看颜色，插入结点都是红色，如果是黑色的话很难处理，因为要每一条的路径黑色都相等，越到下面路径越多，所以统一为红色。判断是在那边子树插入，左子树和右子树的实现逻辑一样，只是方向不一样要改左右，然后先走情况1的，关键点是uncle叔叔，叔叔存在且为红色就满足情况1条件，把父节点和叔叔结点变成黑色，然后g祖父结点变成红色。接着是叔叔结点不存在或者存在为黑色，这时就需要旋转了，要判断是否是一边高了，不是就走双旋。
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;}elsereturn false;}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < cur->_kv.first)parent->_right = cur;elseparent->_left = 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//c//纯粹一边高RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//要双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// 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{// g//u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}7.红黑树的验证
检查俩步数：
1.检测是否满足搜索二叉树，中序遍历是否为有序序列
2.检测是否满足红黑树的性质
这里通过记录一条路径的黑色结点的总个数作为判断标准，因为每条路径的黑色结点个数相等，Check里面先判断是否到最下面，到空就是最下面了，接着是判断此结点和其父节点是否都为红色，如果此节点为黑色就把balckNum++，这个数是统计黑色结点个数的，注意这个数没有在全局和用static修饰，所以是只能在当前作用域存活的，只能记住当前的路径的黑色结点个数，通过递归去检测。
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);}bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){if (refNum != blackNum){cout << "有路径黑色结点数量不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && 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);
}8.总代码
test.c
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"RBTree.h"void TestRBTree1()
{RBTree<int, int> t;// 常规的测试用例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalance() << endl;
}int main()
{TestRBTree1();return 0;
}RBTree.h
#pragma onceenum 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;}elsereturn false;}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < cur->_kv.first)parent->_right = cur;elseparent->_left = 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//c//纯粹一边高RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//要双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// 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{// g//u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}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;}elsepParent->_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 Height(){return _Height(_root);}int Size(){return _Size(_root);}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->_col == RED && root->_parent->_col == RED){cout << "存在连续红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && 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);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}private:Node* _root = nullptr;
};