目录前言概念为什么红黑树满足 最长路径的节点个数 2 * 最短路径的节点个数答案揭晓举例红黑树诞生原因红黑树的模拟实现“颜色”定义基本数据结构定义RBTreeNode的定义RBTree的定义基本操作实现Insert函数基础知识“叔叔”这个身份的认知插入原则插入的准备工作插入节点的颜色定义情况分类情况1根节点为空情况2叔叔为红色情况2叔叔不存在或者叔叔为黑色分析1、叔叔不存在2、叔叔为黑色IsBalance函数测试代码总代码前言我在前面的文章中已经详细讲解了二叉搜索树二叉搜索树的模拟实现-CSDN博客、AVL树AVL树模拟实现-CSDN博客的模拟实现终于我要讲解红黑树啦~~~让我们进入正题吧ヾ(≧▽≦*)o概念红黑树也是一棵二叉搜索树它有如下特点1、每个节点不是红色就是黑色从红黑树名字就可得知2、根节点是黑色的这是检查红黑树是否正确的一个判断条件3、如果一个节点是红色的那它的两个孩子就是黑色的因此在每个路径上不可以出现连续的两个红色节点这既可以作为检查红黑树是否正确的判断条件也是判断插入一个节点后是否需要进行旋转操作的一个条件4、从该节点到所有后代叶节点的简单路径上均包含相同数目的黑色节点这是检查红黑树是否正确的一个判断条件这些特点使得红黑树效率也很高因为他们构成了一个大特点最长路径的节点个数 2 * 最短路径的节点个数为什么红黑树满足 最长路径的节点个数 2 * 最短路径的节点个数通过第四个特点我们思考一下(1) 最短路径满足什么条件(2) 从最短路径的情况能推断出最长路径应该长什么样答案揭晓(1) 最短路径满足什么条件答当该路径所有节点都是黑色节点时该路径最短(2) 从最短路径的情况能推断出最长路径应该长什么样答当该路径黑红相间时该路径最长举例当每条路径上的黑色节点数为3时❁ 当所有节点为黑色 时该路径长为3❁ 当该路径黑红相间时该路径长为6所以红黑树满足 最长路径的节点个数 2 * 最短路径的节点个数下图就清晰明了了红黑树诞生原因我们通过了解AVL树可知AVL树的效率非常高它通过维持左右子树高度差的绝对值 2来维持平衡如果该绝对值 2则将进行旋转在面对杂乱顺序的数据的情况下仍然游刃有余。但是当数据是有序的也就是基本升序或者降序时AVL树将花大量时间在旋转上这就使得AVL树的效率变低而造成这一结果的原因是AVL树追求的是极度平衡。【注】这一特点使得AVL树高度较低面对100w个数据树的高度也是在27~28之间这使得在最坏情况下我们需要查找比较的次数控制在30以内这也是AVL树效率高的原因因此红黑树在付出更少的旋转的代价下诞生了红黑树的模拟实现“颜色”定义虽然红黑树有颜色但是红色和黑色并不是真的颜色而是用了枚举enum的知识将字符串转化为数字内部因此黑色红色的定义就是一个枚举enum COLOR { BLACK, RED }; // 枚举常量通常用大写基本数据结构定义RBTreeNode的定义该部分和AVL树极其相似忘记的可以去复习哦AVL树模拟实现-CSDN博客只不过多了一个颜色的成员template typename T, typename V struct RBTreeNode//RadBlackTree的缩写 { RBTreeNodeT,V* _left; RBTreeNodeT, V* _right; RBTreeNodeT, V* _parent; pairT, V _data; COLOR _col;/**/ RBTreeNode(const pairT, V kv)// 构造函数 : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(kv) , _col(RED) /* 插入节点起初都为红色最好这样只需要检查 当前所在子树 是否出现连续的红节点的情况 若为黑色将会改变该路径的长度将会影响 所有路径 */ {} };RBTree的定义仍然和普通的树一样template typename T, typename V class RBTree { typedef RBTreeNodeT, V Node; public: private: Node* _root nullptr; };基本操作实现Insert函数所有的二叉搜索树都一样最关键的部分就是Insert部分而红黑树的Insert部分无非就是 平衡的调整 颜色的变换也就是说Insert 旋转 变色基础知识“叔叔”这个身份的认知我们在红黑树的插入部分需要注意的就是“叔叔”这个角色叔叔就是自己的父亲的兄弟也就是自己爷爷的另一个儿子“叔叔”将会是插入操作的重要部分。插入原则❁ 保证目前子树的所有路径的黑色节点数不变否则和插入黑色节点没区别将影响所有路径❁根节点必须是黑色插入的准备工作在插入前我们首先要做的就是找到❁插入位置❁ 插入位置的父亲这一部分也和二叉搜索树相同啦bool Insert(const pairT, V kv) { Node* cur _root; Node* parent nullptr; while (cur) { parent cur; if (kv.second cur-_data.second) { cur cur-_right; } else if (kv.second cur-_data.second) { cur cur-_left; } else { return false; } } Node* newnode new Node(kv); newnode-_parent parent; if (kv.second parent-_data.second) { parent-_right newnode; } else if (kv.second parent-_data.second) { parent-_left newnode; } cur newnode; while (parent parent-_col RED) { Node* grandfather parent-_parent; Node* uncle; if (parent grandfather-_left) { uncle grandfather-_right; } else { uncle grandfather-_left; } } _root-_col BLACK; /*重点(插入原则根节点为黑色)*/ return true; }插入节点的颜色定义我在“基础数据结构定义”部分已经注释了插入节点起初都为红色最好这样只需要检查当前所在子树是否出现连续的红节点的情况若为黑色将会改变该路径的长度将会影响所有路径通过这里我们就知道我们插入的节点应该起初定义为红色但是我们红黑树的一个重要特点就是一条路径下不能有连续的红色节点这一点造成我们插入一个数据后需要判断其父亲的颜色❁ 如果父亲为黑色那么不需要在意❁ 如果父亲为红色那我们需要按情况调整情况已经在下面列举出来啦让我们看看吧(´▽ʃ♡ƪ)情况分类情况1根节点为空这个情况自然是第一个节点插入的时候只需要给_root分配空间并将其颜色设置为黑色就可以返回啦if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; }情况2叔叔为红色如下图所示我们需要满足“插入原则”1、该子树所有路径黑色节点数不变所以我们可以通过如下操作来改变(1) 父亲必须变为黑色这是一定的根据第一点我们会发现该子树最左边的路径的黑色节点数增加1为了不改变路径的黑色节点数我们进行第二步(2) 爷爷变为红色根据红黑树的特点不可以有连续的两个红色节点。我们进行第三步(3) 叔叔变为黑色如下图所示细心的读者可能会发现爷爷的颜色变为红色了在红黑树这个非红即黑的树下我们就需要对“红色”极其敏感这里爷爷不一定是祖先所以我们应该注意爷爷的父亲是什么颜色因此将更新cur grandfatherparent也随其改变parent cur-_parentcur grandfatherparent也随其改变parent cur-_parent代码如下if (uncle uncle-_col RED/*叔叔颜色是红色*/) { /*只需要变色,然后grandfather变为cur*/ /* grandfather变为红色 parent和uncle变为黑色 */ grandfather-_col RED; uncle-_col parent-_col BLACK; // 继续向上更新 cur grandfather; parent cur-_parent; }情况2叔叔不存在或者叔叔为黑色这两种情况我们需要进行的操作如下旋转 变色旋转左左、右右情况同AVL树的旋转左右、右左情况按照cur的情况分析如果parent是左孩子cur是右孩子左旋parent然后就转化为左左情况如果parent是右孩子cur是左孩子右旋parent然后就转化为右右情况变色parent变为黑色因为他变为了该子树的祖先grandfather、cur变为红色为了不影响每条路径的黑色节点个数分析1、叔叔不存在左左情况红黑树是一棵“近似平衡”的树但如上图所示该树不平衡这个时候我们就需要“旋转”根据AVL树的知识我们就可以知道该树为“左左情况”因此我们需要“右旋”如下所示而插入原则规定不可改变该子树路径中的黑色节点个数因此这里我们需要保证每条路径的黑色节点数目不变因此1、将parent的颜色改为黑色2、新插入节点 和 grandfather的颜色改为红色同样我们观察一下最上面的节点我们可以发现它的颜色为黑色因此我们不需要向上更新2、叔叔为黑色左左情况根据叔叔不存在且为“左左”的情况我们同样可以知道叔叔存在时的“左左”情况可以写为1、右旋grandfather2、更改颜色parent变黑色cur和grandfather变红色通过以上可见uncle不存在 和 uncle为黑色 的情况的处理方法一样所以如下部分我将以 uncle为黑色的情况讲述~(▽)~*if (parent grandfather-_left) { if (cur parent-_left) { // 左左情况 // 右旋 RotateR(grandfather); // 变色 parent-_col BLACK; cur-_col grandfather-_col RED; } }右右情况很显然右右情况和左左情况类似只不过旋转方向变了因此它的操作如下1、左旋grandfather2、parent的颜色 黑色cur的颜色 grandfather的颜色 红色else { if (cur parent-_right) { // 右右情况 // 左旋 RotateL(grandfather); // 变色 parent-_col BLACK; cur-_col grandfather-_col RED; } }左右情况这种情况看似复杂其实我们能发现这棵树不平衡。因此我们思路就是先变平衡。很显然从parent那里就已经不平衡了因此我们需要左旋parent我们会发现这个情况变为了“左左”情况因此我们只需要右旋grandfather就好并更改颜色颜色更改cur 黑色parent grandfather 红色我们可以发现最上面的节点为黑色。因此我们不用继续向上更新// 左右情况 // 先左旋parent RotateL(parent); // 再右旋grandfather RotateR(grandfather); // 变色 cur-_col BLACK; parent-_col grandfather-_col RED;右左情况同样和左右情况类似步骤1、右旋parent2、变为了“右右”情况左旋grandfather3、更改颜色cur 黑色parent grandfather 红色// 右左情况 // 先右旋parent RotateR(parent); // 再左旋grandfather RotateL(grandfather); // 变色 cur-_col BLACK; parent-_col grandfather-_col RED;IsBalance函数该部分用来检查该红黑树是否正确public: bool IsBalance() { return _IsBalance(_root); // 这种在外部接口里面调用内部接口的原因我在AVL树和二叉搜索树部分讲过 // 原因这样子使用就不需要设置外部接口让类外访问_root再调用该函数 } private: bool _IsBalance(Node* root, int numfirst -1/*第一条路径的黑色节点个数*/, int num 0/*该路径黑色节点的个数*/) { if (root nullptr)// 到了一条路径的末尾 { if (numfirst -1)// 说明是第一条路径 { numfirst num; return true; } else// 不是第一条路就 { // 打印提示信息方便定位插入哪个部分代码不对 if (numfirst ! num) cout 不是所有路径的黑色节点个数相同 endl; return numfirst num;// 判断每条路径的黑色节点个数是否相同 } } // 根必须为黑色 if (root _root _root root-_col RED) { cout 根为红色 endl; return false; } // 不能有连续的红色 if (root-_col RED) { if (root-_left root-_left-_col RED) { cout 两个连续节点为红色 endl; return false; } if (root-_right root-_right-_col RED) { cout 两个连续节点为红色 endl; return false; } } else // 每条路径的黑色节点数相同 { return _IsBalance(root-_left, numfirst, num 1) /*注意不是*/ _IsBalance(root-_right, numfirst, num 1); } return true; }测试代码我们可以采用随机数的方法来检测我们的代码是否有bug哦以下部分就是该方法的代码啦void test() { const int N 10000000; vectorint v; v.reserve(N); srand(time(0));// 随机数种子 for (size_t i 0; i N; i) { v.push_back(rand() i);// i使得数据更随机 } size_t begin2 clock();// 记录Insert部分的起始时间 RBTreeint, int t; for (auto e : v) { //cout Insert: e -; t.Insert(make_pair(e, e)); //cout t.IsBalance() endl; } size_t end2 clock();// 记录Insert部分的结束时间 cout Insert: end2 - begin2 endl;// 计算Insert 10000000个数据时所需要的时间 cout t.IsBalance() endl; }中序遍历部分就和普通树的部分一样啦这里就不过多赘述啦总代码#pragma once enum COLOR { BLACK, RED }; template typename T, typename V struct RBTreeNode { RBTreeNodeT,V* _left; RBTreeNodeT, V* _right; RBTreeNodeT, V* _parent; pairT, V _data; COLOR _col; RBTreeNode(const pairT, V kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(kv) , _col(RED) /* 插入节点起初都为红色最好这样只需要检查 当前所在子树 是否出现连续的红节点的情况 若为黑色将会改变该路径的长度将会影响 所有路径 */ {} }; template typename T, typename V class RBTree { typedef RBTreeNodeT, V Node; public: bool Insert(const pairT, V kv) { if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; } Node* cur _root; Node* parent nullptr; while (cur) { parent cur; if (kv.second cur-_data.second) { cur cur-_right; } else if (kv.second cur-_data.second) { cur cur-_left; } else return false; } Node* newnode new Node(kv); newnode-_parent parent; if (kv.second parent-_data.second) { parent-_right newnode; } else if (kv.second parent-_data.second) { parent-_left newnode; } cur newnode; while (parent parent-_col RED) { Node* grandfather parent-_parent; Node* uncle; if (parent grandfather-_left) { uncle grandfather-_right; } else uncle grandfather-_left; if (uncle nullptr/*叔叔不存在*/ || uncle-_col BLACK/*叔叔颜色是黑色*/) { /*旋转 变色*/ /* 旋转 左左、右右情况同AVL树的旋转 左右、右左情况按照cur的情况分析 如果parent是左孩子cur是右孩子左旋parent然后就转化为左左情况 如果parent是右孩子cur是左孩子右旋parent然后就转化为右右情况 变色 p变为黑色因为他变为了该子树的组先 g、c变为红色为了不影响每条路径的黑色节点个数 */ // 旋转 if (parent grandfather-_left) { if (cur parent-_left) { // 左左情况 // 右旋 RotateR(grandfather); // 变色 parent-_col BLACK; cur-_col grandfather-_col RED; } else { // 左右情况 // 先左旋parent RotateL(parent); // 再右旋grandfather RotateR(grandfather); // 变色 cur-_col BLACK; parent-_col grandfather-_col RED; } } else { if (cur parent-_right) { // 右右情况 // 左旋 RotateL(grandfather); // 变色 parent-_col BLACK; cur-_col grandfather-_col RED; } else { // 右左情况 // 先右旋parent RotateR(parent); // 再左旋grandfather RotateL(grandfather); // 变色 cur-_col BLACK; parent-_col grandfather-_col RED; } } break; } else// if (uncle-_col RED/*叔叔颜色是红色*/) { /*只需要变色,然后grandfather变为cur*/ /* grandfather变为红色 parent和uncle变为黑色 */ grandfather-_col RED; uncle-_col parent-_col BLACK; // 继续向上更新 cur grandfather; parent cur-_parent; } } _root-_col BLACK;/*重点*/ return true; } // 左单旋 void RotateL(Node* root) { Node* subR root-_right; Node* subRL subR-_left;/*可能为空*/ root-_right subRL; if (subRL) { subRL-_parent root; } subR-_left root; subR-_parent root-_parent; root-_parent subR; if (root _root) _root subR; if (subR-_parent) { if (root subR-_parent-_left) { subR-_parent-_left subR; } else subR-_parent-_right subR; } } // 右单旋 void RotateR(Node* root) { Node* subL root-_left; Node* subLR subL-_right;/*可能为空*/ root-_left subLR; if (subLR) { subLR-_parent root; } subL-_right root; subL-_parent root-_parent; root-_parent subL; if (root _root) _root subL; if (subL-_parent) { if (root subL-_parent-_left) { subL-_parent-_left subL; } else subL-_parent-_right subL; } } void InOrder() { _InOrder(_root); cout endl; } // 检查是否平衡时用 void PreOrder() { _PreOrder(_root); cout endl; } void _PreOrder(Node* root) { if (root nullptr) return; cout root-_data.first ( root-_col ) ; _PreOrder(root-_left); _PreOrder(root-_right); } bool IsBalance() { return _IsBalance(_root); } bool IsBalance2() { if (_root nullptr) return true; if (_root-_col RED) return false; //参考值 int refVal 0; Node* cur _root; while (cur) { if (cur-_col BLACK) { refVal; } cur cur-_left; } int blacknum 0; return Check(_root, blacknum, refVal); } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_data.first ; _InOrder(root-_right); } bool _IsBalance(Node* root, int numfirst -1/*第一条路径的黑色节点个数*/, int num 0) { if (root nullptr) { if (numfirst -1) { numfirst num; return true; } else { // 打印提示信息方便定位插入哪个部分代码不对 if (numfirst ! num) cout 不是所有路径的黑色节点个数相同 endl; return numfirst num; } } // 根必须为黑色 if (root _root _root root-_col RED) { cout 根为红色 endl; return false; } // 不能有连续的红色 if (root-_col RED) { if (root-_left root-_left-_col RED) { cout 两个连续节点为红色 endl; return false; } if (root-_right root-_right-_col RED) { cout 两个连续节点为红色 endl; return false; } } else // 每条路径的黑色节点数相同 { return _IsBalance(root-_left, numfirst, num 1) /*注意不是*/ _IsBalance(root-_right, numfirst, num 1); } return true; } // 根节点-当前节点这条路径的黑色节点的数量 bool Check(Node* root, int blacknum, const int refVal) { if (root nullptr) { //cout balcknum endl; if (blacknum ! refVal) { 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, refVal) Check(root-_right, blacknum, refVal); } private: Node* _root nullptr; };完结撒花~❀❀❀❀❀❀❀❀❀快开学啦祝大家在新的一学期收获满满哦脑子不好的小菜鸟和你一起加油哦(●ˇ∀ˇ●)