目录一. 红黑树的概念1,1 红黑树的规则1.2 关键问题思考红黑树如何保证最长路径≤2× 最短路径1.3 红黑树的效率问题二. 红黑树的实现2.1 红黑树的结构2.2 红黑树的插入2.2.1 情况一变色2.2.2 情况二单旋变色2.2.3 情况三双旋变色2.2.4 代码实现2.3 红黑树的验证一. 红黑树的概念红黑树也是一棵二叉搜索树其每个结点会增加一个存储位颜色存储位用来表示结点的颜色两种颜色可以是红色或者黑色因此被称为红黑树。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的也就是说红黑树是近似平衡的。1,1 红黑树的规则每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点。1.2 关键问题思考红黑树如何保证最长路径≤2× 最短路径由规则 4 可知所有路径的黑色节点数量相同记为bh因此极端场景下最短路径是全黑节点路径长度 bh由规则 2 和 3 可知路径中无连续红色节点因此最长路径是 “黑 - 红” 交替路径长度 2×bh综上任意路径长度满足 bh ≤ 路径长度 ≤ 2×bh即最长路径不超过最短路径的 2 倍。1.3 红黑树的效率问题假设N是红黑树树中结点数量h最短路径的长度那么2^h - 1 N 2^{2h} - 1由此推出hlogN也就是意味着红黑树增删查改最坏也就是走最长路径2logN那么时间复杂度还是O(logN)。红黑树的表达相对AVL树要抽象一些AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束间接的实现了近似平衡他们效率都是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格。二. 红黑树的实现2.1 红黑树的结构枚举表示颜色(red / black)enum Color { RED, BLACK };RBTreeNode 结构templateclass K,class V class RBTreeNode { public: RBTreeNode(const pairK,V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) {} pairK, V_kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Color _col };2.2 红黑树的插入1、插入一个值按二叉搜索树规则进行插入插入后我们只需要观察是否符合红黑树的4条规则。2、如果是空树插入新增结点是黑色结点。如果是非空树插入新增结点必须红色结点因为非空树插入新增黑色结点就破坏了规则4规则4是很难维护的。3、非空树插入后新增结点必须红色结点如果父亲结点是黑色的则没有违反任何规则插入结束。4、非空树插入后新增结点必须红色结点如果父亲结点是红色的则违反规则3。进一步分析c是红色p为红g必为黑这三个颜色都固定了关键的变化看u的情况需要根据u分为以下几种情况分别处理。说明下图中假设我们把新增结点标识为c(cur)c的父亲标识为p(parent)p的父亲标识为g(grandfather)p的兄弟标识为u(uncle)。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变回黑色。下图将以上类似的处理进行了抽象表达d / e / f代表每条路径拥有hb个黑色结点的子树a / b代表每条路径拥有hb - 1个黑色结点的根为红的子树hb 0。下图则分别展示了hb 0 / hb 1 / hb 2的具体情况组合分析——当hb等于2时这里组合情况上百亿种这些样例是帮助我们理解不论情况多少种有多么复杂处理方式都是一样的变色再继续往上处理即可所以我们只需要看抽象图即可。2.2.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.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.2.4 代码实现insert 插入bool insert(const pairK, V kv) { Node* cur _root; Node* parent nullptr; if (cur nullptr) { _root new Node(kv); _root-_col BLACK; return true; } while (cur) { if (kv cur-_kv) { parent cur; cur cur-_right; } else if (kv cur-_kv) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); cur-_col RED; if (parent-_kv kv) { parent-_left cur; } else { parent-_right 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 BLACK; uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { if (cur parent-_left) { RotateR(grandfather); grandfather-_col RED; parent-_col BLACK; } else { RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { Node* uncle grandfather-_left; if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; } else { if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { RotateR(parent); PotateL(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; Node* pParent parent-_parent; parent-_left SubLR; SubL-_right parent; if (SubLR) { SubLR-_parent parent; } if (parent _root) { _root SubL; SubL-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left SubL; SubL-_parent pParent; } else { pParent-_right SubL; SubL-_parent pParent; } } parent-_parent SubL; } void RotateL(Node* parent) { Node* SubR parent-_right; Node* SubRL SubR-_left; Node* pParent parent-_parent; parent-_right SubRL; SubR-_left parent; if (SubRL) { SubRL-_parent parent; } if (parent _root) { _root SubR; SubR-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left SubR; SubR-_parent pParent; } else { pParent-_right SubR; SubR-_parent pParent; } } parent-_parent SubR; }2.3 红黑树的验证1、规则1枚举颜色类型天然实现保证了颜色不是黑色就是红色。2、规则2直接检查根即可。3、规则3前序遍历检查遇到红色结点查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲的颜色就方便多了即孩子不一定存在父亲一定存在。4、规则4前序遍历遍历过程中用形参记录根节点到当前结点的blackNum黑色结点数量前序遍历遇到黑色结点就blackNum走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值依次比较即可。public: bool Isbalance() { if (_root nullptr) { return true; } if (_root-_col RED) { return false; } Node* cur _root; int refNum 1; while (cur-_left) { cur cur-_left; if (cur-_col BLACK) { refNum; } } return Check(_root, refNum, 0); } private: bool Check(Node* root, int refNum, int blackNum) { if (root nullptr) { if (refNum ! blackNum) { cout 存在黑色节点的数量不相等的路径 endl; return false; } return true; } if (root-_col BLACK) { blackNum; } else { if (root-_parent-_col RED) { cout root-_kv.first 存在连续的红色节点 endl; return false; } } return Check(root-_left, refNum, blackNum) Check(root-_right, refNum, blackNum); }