微信支付公司网站,电商发展现状与趋势,做网站的会计分录,济宁建设网站✨✨ 欢迎大家来到小伞的大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;C学习 小伞的主页#xff1a;xiaosan_blog 制作不易#xff01;点个赞吧#xff01;#xff01;谢谢喵#xff01;… ✨✨ 欢迎大家来到小伞的大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏C学习 小伞的主页xiaosan_blog 制作不易点个赞吧谢谢喵 大家应该都学过平衡二叉树(AVLTree)了解到AVL树的性质其实平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。AVL树的效率就是高在这个地方。如果在AVL树中插入或删除节点后使得高度之差大于1。此时AVL树的平衡状态就被破坏它就不再是一棵二叉树为了让它重新维持在一个平衡状态就需要对其进行旋转处理, 那么创建一颗平衡二叉树的成本其实不小. 这个时候就有人开始思考并且提出了红黑树的理论红黑树在业界应用很广泛比如 Java 中的 TreeMapJDK 1.8 中的 HashMap、C STL 中的 map 均是基于红黑树结构实现的。那么红黑树到底比AVL树好在哪里C_数据结构_AVL树-CSDN博客
1.红黑树的概念
红黑树是一棵二叉搜索树他的每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。 通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍 因而是接近平衡的。 思考为什么需要红黑树
对于二叉搜索树如果插入的数据是随机的那么它就是接近平衡的二叉树平衡的二叉树它的操作效率查询插入删除效率较高时间复杂度是OlogN。但是可能会出现一种极端的情况那就是插入的数据是有序的递增或者递减那么所有的节点都会在根节点的右侧或左侧此时二叉搜索树就变为了一个链表它的操作效率就降低了时间复杂度为O(N)所以可以认为二叉搜索树的时间复杂度介于OlogN和O(N)之间视情况而定。那么为了应对这种极端情况红黑树就出现了它是具备了某些特性的二叉搜索树能解决非平衡树问题红黑树是一种接近平衡的二叉树说它是接近平衡因为它并没有像AVL树的平衡因子的概念它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构进而提升整体的性能并没有严格的卡定某个平衡因子来维持绝对平衡。
1.1 红黑树的规则 1.每个结点不是红色就是黑色 2.根结点是黑色的 3. 如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。 4. 对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点 注《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点而是我们说的空结点有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径《算法导论》在后续讲解实现的细节中也忽略了NIL结点所以我们知道一下这个概念即可 例 1.2 思考一下红黑树如何确保最长路径不超过最短路径的两倍的
最短路径由规则4可知从根到NULL结点的每条路径都有相同数量的黑色结点在最极端的场景下最短路径就是全是黑色结点的路径假设最短路径⻓度为bh(black height) 4. 对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点 最长路径由规则2和规则3可知任何路径不会含有连续的红色节点那么在最极端的场景下最长路径会出现在红黑色节点交替最长路径的长度为2*bh。 2.根结点是黑色的 3. 如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。 总结 对于红黑树的4点规则而言理论上全黑最长路径与一黑一红最短路径并不会每棵红黑树都存在假设任意一条从根到NULL结点路径的长度为x那么bh h 2*bh。 1.3 红黑树的效率
假设N是红⿊树树中结点数量h最短路径的⻓度那么 , 由此推出 也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 那么时间复杂度还是 。 2h - 1 N 22∗h - 1 h ≈ logN 2 ∗ logN O(logN)
红黑树的表达相对AVL树要抽象一些AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜色约束间接的实现了近似平衡他们效率都是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格。 2.红黑树的实现
2.1 红黑树的结构
#pragma once
//枚举值表示颜色
enum Colour
{RED,BLACK
};//默认按key/val结构实现
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)//, _col(RED)这里可以不用初始化在后续插入时会给出相应措施//如果要想初始化的话默认初始为RED因为后续插入的if影响不大//思考是否可以初始化为黑色呢————————————{}};templateclass K, class V
class RBTree{typedef RBTreeNodeK, V Node;
public:
private:Node* _root nullptr;
}
如果我们想要初始化颜色为什么要默认是红色呢
我们来分析一下如果我们插入一个新结点给的是黑色那它一定会违反上面提到的红黑树的第5条性质——每条路径上黑色结点的数量一致。 因为原来每条路径黑色结点数量是相同的现在新插入一个黑色结点的话那插入的这条路径会增加一个黑色结点但是其它路径数量不变所以其它所有的路径黑色结点数量都和这一条不相等这样就比较麻烦了。 那如果我们插入结点默认给红色呢会违反规则吗 那红色的话其实要看具体情况了 如果插入一个红色结点但是它的父亲也是红色那就出事了因为红黑树里面不能出现连续的红色结点那这种情况就需要调整了。 但如果它的父亲是黑色那就没问题不需要进行什么处理。 所以我们新插入的结点给成红色当然如果是第一次插入根结点我们可以直接给黑色因为红黑树要求根结点必须是黑色的。
2.2 红黑树的插入
1.找到插入位置我们遍历红黑树找到新节点应该插入的位置。这通常是通过比较新节点的键与当前节点的键来完成的直到找到一个空位置即叶子节点的子节点位置为止。在这个过程中我们还记录了新节点的父节点以便后续操作。
2.插入新节点一旦找到插入位置我们将新节点插入到树中。这涉及到将新节点的父节点指针指向之前记录的父节点并根据新节点的键值更新父节点的左子节点或右子节点指针。
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点必须为黑色节点return true;}Node* parent nullptr;Node* cur _root;//与AVL树一样左小右大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;
}
3.修复红黑树性质插入新节点后红黑树可能不再满足其性质。因此我们需要进行一系列操作来修复这些性质。这主要包括检查新节点的父节点和叔叔节点的颜色并根据需要执行旋转和重新着色操作。
2.2.1 红黑树的插入过程
插入一个值按二叉搜索树规则进行插入插入后我们只需要观察是否符合红黑树的4条规则。
2. 如果是空树插入新增结点是黑色结点。如果是非空树插入新增结点必须红色结点因为非空树插入新增黑色结点就破坏了规则4规则4是很难维护的。
3. 非空树插入后新增结点必须红色结点如果⽗亲结点是黑色的则没有违反任何规则插入结束。
4. 非空树插入后新增结点必须红色结点如果父亲结点是红色的则违反规则3。进一步分析c是红色p为红g必为⿊这三个颜⾊都固定了关键的变化看u的情况需要根据u分为以下⼏种情况分别处理 说明下图中假设我们把新增结点标识为c (cur)c的父亲标识为p(parent)p的父亲标识为g(grandfather)p的兄弟标识为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的左还是右都是上面的变色处理方式。 跟AVL树类似图0我们展示了一种具体情况但是实际中需要这样处理的有很多种情况。
• 图1将以上类似的处理进⾏了抽象表达d/e/f代表每条路径拥有hb个黑色结点的子树a/b代表每
条路径拥有hb-1个黑色结点的根为红的子树hb0。
• 图2/图3/图4分别展⽰了hb 0/hb 1/hb 2的具体情况组合分析当hb等于2时这⾥组合情况上百亿种这些样例是帮助我们理解不论情况多少种多么复杂处理方式一样的变色再继续往上处理即可所以我们只需要看抽象图即可。 2.2.3 情况2单旋变⾊ c为红p为红g为黑u不存在或者u存在且为黑u不存在则c一定是新增结点u存在且为黑则c一定不是新增c之前是黑色的是在c的⼦树中插⼊符合情况1变⾊将c从黑色变成红色更新上来的。 分析p必须变黑才能解决连续红色结点的问题u不存在或者是黑色的这⾥单纯的变色⽆法解决问题需要旋转 变色。 g p u c 如果p是g的左c是p的左那么以g为旋转点进行右单旋再把p变⿊g变红即可。p变成课这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则。 g u p c 如果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不存在或者是黑色的这⾥单纯的变色⽆法解决问题需要旋转变色。 g p u c
如果p是g的左c是p的右那么先以p为旋转点进⾏左单旋再以g为旋转点进⾏右单旋再把c变黑g变红即可。c变成课这颗树新的根这样⼦树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。 g u p c
如果p是g的右c是p的左那么先以p为旋转点进行右单旋再以g为旋转点进行左单旋再把c变黑g变红即可。c变成课这颗树新的根这样⼦树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则 2.3 红黑树插入实现
左单旋
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 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;}else{pParent-_right subL;}subL-_parent pParent;}
}
红黑树插入
// 旋转代码的实现跟AVL树是⼀样的只是不需要更新平衡因⼦
bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点必须为黑色节点return true;}Node* parent nullptr;Node* cur _root;//与AVL树一样左小右大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){// g// p uNode* uncle grandfather-_right;if (uncle uncle-_col RED){//如果g的⽗亲还是红⾊那么就还需要继续处理如果g的⽗亲是⿊⾊则处理结束//了如果g就是整棵树的根再把g变回⿊⾊// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_left){//p必须变⿊才能解决连续红⾊结点的问题u不存在或者是⿊⾊的这⾥单纯的变⾊⽆法解//决问题需要旋转 变⾊// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// c//p必须变⿊才能解决连续红⾊结点的问题u不存在或者是⿊⾊的这⾥单纯的变⾊⽆法解//决问题需要旋转 变⾊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;} 回答前面问题有规则可知对于空树父亲节点必须为黑色节点当if语句将其排除那么对于非空树插入则必须为红色节点。所以如果将颜色是否初始化为RED并不影响其插入。 if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点必须为黑色节点return true;} 2.4 红黑树的查找
按二叉搜索树逻辑实现即可搜索效率为 O(logN)
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⾛到空就计算出了⼀条路径的黑色结点数量。再任意⼀条路径黑色结点数量作为参考值依次⽐较即可。 我们也要检测其是否满足红黑树的性质我们需要两个函数
a. Check 函数 Check 函数用于递归地检查红黑树的性质是否得到满足。它接受三个参数当前节点 cur、从根节点到当前节点路径上的黑色节点数 blackNum 和从根节点到最左侧路径上的黑色节点数 refBlackNum。
空节点检查如果当前节点为空cur nullptr则检查从根节点到该路径的黑色节点数 blackNum 是否与最左侧路径的黑色节点数 refBlackNum 相等。如果不相等则输出错误信息并返回 false。连续红色节点检查如果当前节点为红色且其父节点也为红色则违反了红黑树的性质性质 4输出错误信息并返回 false。黑色节点计数如果当前节点为黑色则增加 blackNum 的计数。递归检查子节点递归调用 Check 函数检查当前节点的左子树和右子树只有当左右子树都返回 true 时当前节点才返回 true。
b. IsBalance 函数 IsBalance 函数用于检查整棵红黑树是否平衡。
根节点颜色检查如果根节点存在且为红色则直接返回 false因为根节点必须是黑色性质 2。计算最左侧路径黑色节点数从根节点开始沿着最左侧路径遍历树计算遇到的黑色节点数存储在 refBlackNum 中。调用 Check 函数从根节点开始调用 Check 函数递归地检查整棵树是否满足红黑树的性质。传递的初始黑色节点数 blackNum 为 0参考黑色节点数 refBlackNum 为之前计算得到的值。
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);
}
3. 红黑树的删除
红黑树的删除呢我们这里不做详细讲解红黑树的删除比较复杂要比插入还复杂好多。 但关键的是红黑树的删除在考研包括我们找工作笔试面试的时候一般是不会考察的所以我们也没必要去学。 大家有兴趣的可以自己查找相关资料进行学习可以参考《算法导论》或者《STL源码剖析》
4. 红黑树与AVL树的比较 红黑树和AVL树都是高效的自平衡搜索二叉树增删改查的时间复杂度都是O(l o g 2 N log_2 Nlog2N)。 红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍所以AVL树的插入和删除操作比红黑树更耗时。 因为AVL树在插入和删除节点后会进行更多的旋转操作以维持一个较为严格的平衡所以插入和删除操作的时间复杂度更高。 相对而言红黑树对平衡的控制比较宽松降低了插入删除时需要旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 在实际应用中红黑树的使用更广泛。许多编程语言和库都使用红黑树作为基础数据结构例如C STL中的std::map和std::set就是基于红黑树实现的。 5. 源码分享
5.1 含有迭代器版本 RBTreeNode.h #pragma onceenum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}Self operator(){if (_node-_right){// 右不为空中序下一个访问的节点是右子树的最左(最小)节点Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else{// 右为空祖先里面孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent cur-_parent;}_node parent;}return *this;}Self operator--(){if (_node nullptr) // --end(){// --end()特殊处理走到中序最后一个结点整棵树的最右结点Node* rightMost _root;while (rightMost rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else if (_node-_left){// 左子树不为空中序左子树最后一个Node* rightMost _node-_left;while (rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else{// 孩子是父亲右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent cur-_parent;}_node parent;}return *this;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator! (const Self s) const{return _node ! s._node;}bool operator (const Self s) const{return _node s._node;}
};templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, const T, const T* ConstIterator;Iterator Begin(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* cur _root;while (cur cur-_left){cur cur-_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}pairIterator, bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;//return pairIterator, bool(Iterator(_root, _root), true);return { Iterator(_root, _root), true };}KeyOfT kot;Node* parent nullptr;Node* cur _root;while (cur){if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else{return { Iterator(cur, _root), false };}}cur new Node(data);Node* newnode cur;cur-_col RED;if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_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// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(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 { Iterator(newnode, _root), 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;}else{pParent-_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;}}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;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}private: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;
}; test.cpp //#define _CRT_SECURE_NO_WARNINGS 1
//
//#includeiostream
//#includevector
//#includetime.h
//using namespace std;
//
//#includeRBTreeNode.h
//
//void TestTree2()
//{
//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);
//}
//size_t begin2 clock();
//AVLTreeint, int t;
//for (auto e : v)
//{
// t.Insert(make_pair(e, e));
//}
// size_t end2 clock();
//
// size_t begin22 clock();
// RBTreeint, int rbt;
// for (auto e : v)
// {
// rbt.Insert(make_pair(e, e));
// }
// size_t end22 clock();
//
// cout AVL Insert: end2 - begin2 endl;
// cout RB Insert: end22 - begin22 endl;
//
// cout AVL IsBalance: t.IsBalanceTree() endl;
// cout RB IsBalance: rbt.IsBalance() endl;
//
//
// cout AVL Height: t.Height() endl;
// cout AVL Size: t.Size() endl;
//
// cout RB Height: rbt.Height() endl;
// cout RB Size: rbt.Size() endl;
//
// size_t begin1 clock();
// // 确定在的值
// for (auto e : v)
// {
// t.Find(e);
// }
// // 随机值
// /*for (size_t i 0; i N; i)
// {
// t.Find((rand() i));
// }*/
// size_t end1 clock();
// cout AVL Find: end1 - begin1 endl;
//
// size_t begin11 clock();
// // 确定在的值
// for (auto e : v)
// {
// rbt.Find(e);
// }
// // 随机值
// /*for (size_t i 0; i N; i)
// {
// t.Find((rand() i));
// }*/
// size_t end11 clock();
// cout RB Find: end11 - begin11 endl;
//}
//
//int main()
//{
// TestTree2();
//
// return 0;
//}5.2 不含有迭代器版本 RBTreeNode.h #pragma onceenum Colour
{RED,BLACK
};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:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点必须为黑色节点return true;}Node* parent nullptr;Node* cur _root;//与AVL树一样左小右大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){// g// p uNode* uncle grandfather-_right;if (uncle uncle-_col RED){//如果g的⽗亲还是红⾊那么就还需要继续处理如果g的⽗亲是⿊⾊则处理结束//了如果g就是整棵树的根再把g变回⿊⾊// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_left){//p必须变⿊才能解决连续红⾊结点的问题u不存在或者是⿊⾊的这⾥单纯的变⾊⽆法解//决问题需要旋转 变⾊// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// c//p必须变⿊才能解决连续红⾊结点的问题u不存在或者是⿊⾊的这⾥单纯的变⾊⽆法解//决问题需要旋转 变⾊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;}else{pParent-_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){// 前序遍历走到空时意味着一条路径走完了//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);}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;
}; test.cpp #define _CRT_SECURE_NO_WARNINGS 1#includeiostream
using namespace std;#includeRBTreeNode.hvoid TestRBTree1()
{RBTreeint, 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;
}
