C++之红黑树
前言：博主的重点是实现红黑树的插入
目录
红黑树
红黑树的概念
红黑树的性质
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
AVL树与红黑树效率的比较
为什么红黑树用的跟多呢？
红黑树的实现
红黑树节点的定义
在节点的定义中，为什么要将节点的默认颜色给成红色的？
红黑树的插入操作
1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏
情况一: cur为红，p为红，g为黑，u存在且为红
解决方式：
抽象图：
具象图：
情况二: cur为红，p为红，g为黑，u不存在/u为黑
解决方法：
抽象图：
编辑具象图：
编辑情况三: cur为红，p为红，g为黑，u不存在/u为黑
解决方法：
抽象图：
编辑具象图：
红黑树的验证
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质
红黑树的测试
编辑红黑树的删除
红黑树的应用
红黑树的完整代码
红黑树
红黑树的概念
红黑树 ，是一种 二叉搜索树 ，但 在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black 。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩 倍 ，因而是 接近平衡 的。
红黑树的性质
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 ，但是没有连续的红节点 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路径的黑色节点都相同） 5. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点，也就是NIL节点 ) eg:该树只有两个节点
因此性质5平常我们是不用去关注它的，但我们要知道它对应的是哪种情况即可。
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
最短路径：全是黑节点 最长路径：一黑一红一黑一红.... 假设每条路径黑节点是N，那么N<=任意路径<=2N。
AVL树与红黑树效率的比较
AVL树左右两边更均衡，高度更接近logN。红黑树左右两边并没有那么均衡，它的整体高度： 假设红黑树中一条路径的黑色节点的数量是X 假设红黑树的高度是h, 2X>=h>=X.N是树中节点的数量 2^X-1<= N <=2^X=2X-1 全黑满二叉树 一黑一红满二叉树 X=(log₂N+1)/2 黑色最坏情况是㏒₂N，加上红色以后最坏情况就是2*㏒₂N 结论：AVL 树严格平衡，效率logN，红黑树接近平衡，效率是2*logN;
为什么红黑树用的跟多呢？
因为在内存中CPU非常快，N对于CPU非常小，假如N是10亿，AVL找30次，红黑树找60次。这对于CPU是没差别的。就好比你有1块与你有5毛的区别，不管你有哪个你都是穷的；另外AVL树达到平衡需要很多次的旋转才能达到，但是红黑树却不需要旋转，也就是说AVL树结果虽然比红黑树好一点，但是这一丁点是无足轻重的，而且为了好这一点AVL树付出了很大旋转的代价； 所以红黑树在经常进行增删的结构 中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
红黑树的实现
红黑树节点的定义
enum Colour{RED,BLACK};templatestruct RBTreeNode{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair _kv;Colour _col;RBTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //红的黑的都无所谓, _kv(kv){}};在节点的定义中，为什么要将节点的默认颜色给成红色的？
插入黑节点或者插入红节点就代表着破坏规则3和4，但是破坏规则3的代价要比破坏4的代价小很多 。所以我们默认插入的是红节点。
红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点
bool Insert(const pair& 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 _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 _right = cur;cur->_parent = parent; //把三叉链链上}else{parent->_left = cur;cur->_parent = parent;}//控制平衡return true;}2. 检测新节点插入后，红黑树的性质是否造到破坏
因为 新节点的默认颜色是红色 ，因此：如果 其双亲节点的颜色是黑色，没有违反红黑树任何性质 ，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点 ，此时需要对红黑树分情况来讨论：
约定: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 做左单旋转，对g进行右单旋转 ； p 为 g 的右孩子， cur 为 p 的左孩子，则针对 p 做右单旋转，对g进行左单旋转；cur、 g 变色 --cur 变黑， g 变红
抽象图：
具象图：
完整代码：
//控制平衡while (parent&& parent->_col == RED) //父亲存在且为红一定不是根{Node* grangfather = parent->_parent;if (parent == grangfather->_left) //父亲在g的左{Node* uncle = grangfather->_right;if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红{//变色+继续向上处理parent->_col = uncle->_col = BLACK;grangfather->_col = RED;cur = grangfather;parent = cur->_parent;}else //情况二+三：叔叔存在/叔叔存在且为黑 {// g // p//c// g// p// cif (cur == parent->_left) //情况二{ //单旋RotateR(grangfather);parent->_col = BLACK;grangfather->_col = RED;}else //情况三{//双旋RotateL(parent);RotateR(grangfather);cur->_col = BLACK;grangfather->_col = RED;}break; //我这棵树旋转完成了后，每条路径黑节点的个数没变，不会影响其他路径，这棵字树的根已经是黑色了，与情况一不同}}else//parent == grangfather->_right p在g的右{Node* uncle = grangfather->_left;if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红{//变色+继续向上处理parent->_col = uncle->_col = BLACK;grangfather->_col = RED;cur = grangfather;parent = cur->_parent;}else //情况二+三：叔叔存在/叔叔存在且为黑 {// g// p// c// g// p// cif (cur == parent->_right) //情况二{RotateL(grangfather);parent->_col = BLACK;grangfather->_col = RED;}else //情况三{RotateR(parent);RotateL(grangfather);cur->_col = BLACK;grangfather->_col = RED;}break; //我这棵树旋转完成了后，每条路径黑节点的个数没变，不会影响其他路径，这棵字树的根已经是黑色了，与情况一不同}}}_root->_col = BLACK;红黑树的验证
红黑树的检测分为两步：
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
中序遍历代码：
void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout <_kv.first << ":" <_kv.second <_right);}2. 检测其是否满足红黑树的性质
可以用最长路径不超过最短路径的二倍检查吗？
可以但是不好，eg:
- 每个节点不是红色就是黑色，好检查，我们的颜色本身就是枚举值。
- 根节点是黑色，好检查。
- 每个节点是红色，则它的孩子都是黑的，我们可以通过遍历去检查红节点，然后再检查它的孩子是不是黑节点，但是这样不好，因为红节点的孩子的情况很多，可能存在2个，1个或者0个；所以我们可以通过检查红节点的父亲结点是不是黑节点来进行检查。
- 如何检查每条路径的黑色节点的个数都相等？通过将一条最左路径的黑色节点数量做基准值，然后递归每条路径，与这个基准值做比较，如果相等则代表没问题，不相等就代表出现问题
检查代码：
bool IsBalance(){if (_root && _root->_col == RED){cout << "根节点不是黑色" <_col == BLACK)++banchmark;left = left->_left;}int blackNum = 0;return _IsBalance(_root, banchmark, blackNum);}bool _IsBalance(Node* root, int banchmark, int blackNum){//依据规则进行检查if (root == nullptr){if (blackNum != banchmark){cout << "存在路径黑色节点的数量不相等" <_col == RED && root->_parent->_col == RED){cout << "出现连续的红色节点" <_col == BLACK){++blackNum;}return _IsBalance(root->_left, banchmark, blackNum)&& _IsBalance(root->_right, banchmark, blackNum);}红黑树的测试
void TestRBtree(){RBTree t;//int a[] = { 5,4,3,2,1,0 };//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(make_pair(e, e));/*if (!t.IsBalance()){cout << "Insert" << e << endl;}*/cout << "Insert" << e << ":" << t.IsBalance() << endl;}t.InOrder(); //中序遍历是可以验证红黑树是搜索二叉树cout << t.IsBalance() << endl; //判断每棵树是否平衡//可以用最长路径不超过最短路径的二倍检查吗？可以但是不好//cout << "深度" << t.Height() << endl;}
红黑树的删除
红黑树的删除不做讲解，如果有兴趣可参考：《算法导论》或者《 STL 源码剖析》，或者下面两位大佬的博客。 http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html http://blog.csdn.net/chenhuajie123/article/details/11951777
红黑树的应用
1. C++ STL 库 -- map/set 、 mutil_map/mutil_set 2. Java 库 3. linux 内核 4. 其他一些库
红黑树的完整代码
#pragma once#include#includeusing namespace std;enum Colour{RED,BLACK};templatestruct RBTreeNode{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair _kv;Colour _col;RBTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //红的黑的都无所谓, _kv(kv){}};templatestruct RBTree{typedef RBTreeNode Node;public:RBTree():_root(nullptr){}bool Insert(const pair& 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 _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 _right = cur;cur->_parent = parent; //把三叉链链上}else{parent->_left = cur;cur->_parent = parent;}//控制平衡while (parent&& parent->_col == RED) //父亲存在且为红一定不是根{Node* grangfather = parent->_parent;if (parent == grangfather->_left) //父亲在g的左{Node* uncle = grangfather->_right;if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红{//变色+继续向上处理parent->_col = uncle->_col = BLACK;grangfather->_col = RED;cur = grangfather;parent = cur->_parent;}else //情况二+三：叔叔存在/叔叔存在且为黑 {// g // p//c// g// p// cif (cur == parent->_left) //情况二{ //单旋RotateR(grangfather);parent->_col = BLACK;grangfather->_col = RED;}else //情况三{//双旋RotateL(parent);RotateR(grangfather);cur->_col = BLACK;grangfather->_col = RED;}break; //我这棵树旋转完成了后，每条路径黑节点的个数没变，不会影响其他路径，这棵字树的根已经是黑色了，与情况一不同}}else//parent == grangfather->_right p在g的右{Node* uncle = grangfather->_left;if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红{//变色+继续向上处理parent->_col = uncle->_col = BLACK;grangfather->_col = RED;cur = grangfather;parent = cur->_parent;}else //情况二+三：叔叔存在/叔叔存在且为黑 {// g// p// c// g// p// cif (cur == parent->_right) //情况二{RotateL(grangfather);parent->_col = BLACK;grangfather->_col = RED;}else //情况三{RotateR(parent);RotateL(grangfather);cur->_col = BLACK;grangfather->_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* parentParent = parent->_parent; //提前记录一下parent的父亲subL->_right = parent;parent->_parent = subL;if (parent == _root) //如果是一颗独立的树{_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent) //改变parent父亲的链接{parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent; //注意三叉链接}}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 (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout <_kv.first << ":" <_kv.second <_right);}bool IsBalance(){if (_root && _root->_col == RED){cout << "根节点不是黑色" <_col == BLACK)++banchmark;left = left->_left;}int blackNum = 0;return _IsBalance(_root, banchmark, blackNum);}bool _IsBalance(Node* root, int banchmark, int blackNum){//依据规则进行检查if (root == nullptr){if (blackNum != banchmark){cout << "存在路径黑色节点的数量不相等" <_col == RED && root->_parent->_col == RED){cout << "出现连续的红色节点" <_col == BLACK){++blackNum;}return _IsBalance(root->_left, banchmark, blackNum)&& _IsBalance(root->_right, banchmark, blackNum);}int Height(){return _Height(_root);}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; //不能写反}private:Node* _root;};
