小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了红黑树实现红黑树的概念、红黑树的实现、插入、查找、验证内容全由作者原创无AI并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~目录1. 红黑树的概念1.1 红黑树的规则1.2 思考一下红黑树如何确保最长路径不超过最短路径的2倍的1.3 红黑树的效率2. 红黑树的实现2.1 红黑树的结构2.2 红黑树的插入2.2.1 红黑树树插入一个值的大概过程2.2.2 情况1变色2.2.3 情况2单旋变色2.2.4 情况3双旋变色2.3 红黑树的插入代码实现2.4 红黑树的查找2.5 红黑树的验证结语1.红黑树的概念红黑树是一棵二叉搜索树他的每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的。1.1红黑树的规则1. 每个结点不是红色就是黑色2. 根结点是黑色的3. 如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。4. 对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点说明《算法导论》等书籍上补充了一条每个叶子结点NIL都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点而是我们说的空结点有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径。1.2思考一下红黑树如何确保最长路径不超过最短路径的2倍的由规则4可知从根到NULL结点的每条路径都有相同数量的黑色结点所以极端场景下最短路径就就是全是黑色结点的路径假设最短路径长度为bhblack height。由规则2和规则3可知任意一条路径不会有连续的红色结点所以极端场景下最长的路径就是一黑一红间隔组成那么最长路径的长度为2*bh。综合红黑树的4点规则而言理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x那么 bhh2*bh。1.3红黑树的效率假设N是红黑树树中结点数量h最短路径的长度那么 2^h-1N2^(2h)-1由此推出 h≈log N也就是意味着红黑树增删查改最坏也就是走最长路径 2log N那么时间复杂度还是 O(log N)。红黑树的表达相对AVL树要抽象一些AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束间接的实现了近似平衡他们效率都是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格。2.红黑树的实现2.1红黑树的结构// 枚举值表示颜色 enum Colour { RED, BLACK }; // 这里我们默认按key/value结构实现 templateclass K, class V struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 pairK, V _kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Colour _col; RBTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { } }; templateclass K, class V class RBTree { typedef RBTreeNodeK, V Node; public: private: Node* _root nullptr; };2.2红黑树的插入2.2.1红黑树树插入一个值的大概过程1. 插入一个值按二叉搜索树规则进行插入插入后我们只需要观察是否符合红黑树的4条规则。2. 如果是空树插入新增结点是黑色结点。如果是非空树插入新增结点必须红色结点因为非空树插入新增黑色结点就破坏了规则4规则4是很难维护的。3. 非空树插入后新增结点必须红色结点如果父亲结点是黑色的则没有违反任何规则插入结束。4. 非空树插入后新增结点必须红色结点如果父亲结点是红色的则违反规则3。进一步分析c是红色p为红g必为黑这三个颜色都固定了关键的变化看u的情况需要根据u分为以下几种情况分别处理。说明下图中假设我们把新增结点标识为ccurc的父亲标识为pparentp的父亲标识为 ggrandfatherp的兄弟标识为uuncle。2.2.2情况1变色c为红p为红g为黑u存在且为红则将p和u变黑g变红。在把g当做新的c继续往上更新。分析因为p和u都是红色g是黑色把p和u变黑左边子树路径各增加一个黑色结点g再变红相当于保持g所在子树的黑色结点的数量不变同时解决了c和p连续红色结点的问题需要继续往上更新是因为g是红色如果g的父亲还是红色那么就还需要继续处理如果g的父亲是黑色则处理结束了如果g就是整棵树的根再把g变回黑色。情况1只变色不旋转。所以无论c是p的左还是右p是g的左还是右都是上面的变色处理方式。2.2.3情况2单旋变色c为红p为红g为黑u不存在或者u存在且为黑u不存在则c一定是新增结点u存在且为黑则 c一定不是新增c之前是黑色的是在c的子树中插入符合情况1变色将c从黑色变成红色更新上来的。分析p必须变黑才能解决连续红色结点的问题u不存在或者是黑色的这里单纯的变色无法解决问题需要旋转变色。如果p是g的左c是p的左那么以g为旋转点进行右单旋再把p变黑g变红即可。p变成这颗树新 的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则。如果p是g的右c是p的右那么以g为旋转点进行左单旋再把p变黑g变红即可。p变成这颗树新 的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则。2.2.4情况3双旋变色c为红p为红g为黑u不存在或者u存在且为黑u不存在则c一定是新增结点u存在且为黑则 c一定不是新增c之前是黑色的是在c的子树中插入符合情况1变色将c从黑色变成红色更新上来的。分析p必须变黑才能解决连续红色结点的问题u不存在或者是黑色的这里单纯的变色无法解 决问题需要旋转变色。如果p是g的左c是p的右那么先以p为旋转点进行左单旋再以g为旋转点进行右单旋再把c变 黑g变红即可。c变成这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且 不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。如果p是g的右c是p的左那么先以p为旋转点进行右单旋再以g为旋转点进行左单旋再把c变 黑g变红即可。c变成这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且 不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。2.3红黑树的插入代码实现bool Insert(const pairK, 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-_col RED; if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; while (parent parent-_col RED) { Node* grandfather parent-_parent; if (parent grandfather-_left) { Node* 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) { RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { Node* 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); parent-_col BLACK; grandfather-_col RED; } else { RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_col BLACK; return true; }2.4红黑树的查找按二叉搜索树逻辑实现即可搜索效率为 O(log N)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; }2.5红黑树的验证这里获取最长路径和最短路径检查最长路径不超过最短路径的2倍是不可行的因为就算满足这个条 件红黑树也可能颜色不满足规则当前暂时没出问题后续继续插入还是会出问题的。所以我们还 是去检查4点规则满足这4点规则一定能保证最长路径不超过最短路径的2倍。1. 规则1枚举颜色类型天然实现保证了颜色不是黑色就是红色。2. 规则2直接检查根即可。3. 规则3前序遍历检查遇到红色结点查孩子不太方便因为孩子有两个且不一定存在反过来检 查父亲的颜色就方便多了。4. 规则4前序遍历遍历过程中用形参记录跟到当前结点的blackNum黑色结点数量前序遍历遇到 黑色结点就blackNum走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点 数量作为参考值依次比较即可。bool Check(Node* root, int blackNum, const int refNum) { if (root nullptr) { // 前序遍历走到空时意味着一条路径走完了 //cout blackNum endl; if (refNum ! blackNum) { cout 存在黑色结点的数量不相等的路径 endl; return false; } return true; } // 检查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲就方便多了 if (root-_col RED root-_parent-_col RED) { cout root-_kv.first 存在连续的红色结点 endl; return false; } if (root-_col BLACK) { blackNum; } return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum); } 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); }结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~