三五互联网站管理登录地址是多少,网站建设遇到的问题及对策,wordpress 配置安装,电商平台排行榜【C笔记】红黑树(RBTree)深度剖析和AVL树的对比分析 #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;C笔记 文章目录 【C笔记】红黑树(RBTree)深度剖析和AVL树的对比分析前言一.红黑树的定义1.1 红黑树的概念1.2红黑树的规则1.3 红黑树对比A…【C笔记】红黑树(RBTree)深度剖析和AVL树的对比分析 个人主页大白的编程日记
专栏C笔记 文章目录 【C笔记】红黑树(RBTree)深度剖析和AVL树的对比分析前言一.红黑树的定义1.1 红黑树的概念1.2红黑树的规则1.3 红黑树对比AVL树 二.红黑树的插入2.1插入分析2.1变色2.2 旋转变色2.3 代码实现 三.红黑树的查找四.红黑树的验证4.1 思路分析4.2 代码实现 后言 前言 哈喽各位小伙伴大家好!上期我们讲了反向迭代器和计算器。今天我们来讲一下红黑树的深度剖析。话不多说我们进入正题向大厂冲锋 一.红黑树的定义
1.1 红黑树的概念 红黑树是⼀棵⼆叉搜索树他的每个结点增加⼀个存储位来表示结点的颜色可以是红色或者黑色。通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有⼀条路径会比其他路径长出2倍因而是接近平衡的。 1.2红黑树的规则 每个结点不是红色就是黑色 根节点是黑色的 如果⼀个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意⼀条路径不会有连续的红色结点。 对于任意⼀个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点 这些都是红黑树。 说明《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点而是我们说的空结点有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径《算法导论》在后续讲解实现的细节中也忽略了NIL结点所以我们知道⼀下这个概念即可。 这棵树我们看可能以为是四条路径。 但是其实他是八条路径。 规定空节点是黑的符合红黑树的规则并且方便我们观察红黑树的路径。
由中这几点规则我们可以推出红黑树的性质
最长路径2*最短路径 1.3 红黑树对比AVL树 红黑树的性能不如AVL树因为他没有那么严格地控制高度差。但是他的性能也不会太差因为他控制最长路径2*最短路径。所以他的性能还是在logN的量级 红黑树的表达相对AVL树要抽象⼀些AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束间接的实现了近似平衡他们效率都是同⼀档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格。 总结 查找 红黑树的性能稍逊一筹AVL树 因为他的高度控制没那么严格但都是logN量级。 插入 红黑树的性能要比AVL树好 虽然红黑树多了变色操作但是变色操作简单代价小。 并且红黑树高度控制没那么严格大量插入时旋转的调整次数比AVL树要少。所以插入是红黑树的性能更优秀。
二.红黑树的插入
2.1插入分析
插入⼀个值按⼆叉搜索树规则进行插入插入后我们只需要观察是否符合红黑树的4条规则。如果是空树插入新增结点是黑色结点。如果是非空树插⼊新增结点必须红色结点因为非空树插入新增黑色结点就破坏了规则4规则4是很难维护的。非空树插入后新增结点必须红色结点如果父亲结点是黑色的则没有违反任何规则插⼊结束非空树插入后新增结点必须红色结点如果⽗亲结点是红⾊的则违反规则3。进⼀步分析c是红色p为红g必为黑这三个颜色都固定了关键的变化看u的情况需要根据u分为以下几种情况分别处理。 说明下图中假设我们把新增结点标识为c (cur)c的父亲标识为p(parent)p的父亲标识为g(grandfather)p的兄弟标识为uuncle。
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变回黑色。 p是右子树也是一样的 所以p和cur在左还是在右我们并不关注。 只要u存在并且为红色我们都按照这种方式处理即可。
2.2 旋转变色
如果u不存在或u存在为黑。 我们需要根据cur和p的位置分类讨论
单旋
c为红p为红g为黑u不存在或者u存在且为黑u不存在则c⼀定是新增结点u存在且为黑则c⼀定不是新增c之前是黑色的是在c的子树中插入变色将c从黑色变成红色更新上来的。 分析p必须变黑色才能解决连续红色结点的问题u不存在或者是黑色的这里单纯的变色无法解决问题需要旋转变色。 如果p是左子树并cur是左子树 如果p是g的左c是p的左那么以g为旋转点进行右单旋再把p变黑g变红即可。p变成课这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则。 如果p是右子树并cur是右子树 如果p是g的右c是p的右那么以g为旋转点进行左单旋再把p变黑g变红即可。p变成课这颗树新的根这样i树黑色结点的数量不变没有连续的红结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则。 那就是以g进行左单旋 在把g变红 p变黑。
双旋
如果p是左子树cur是右子树 如果p是g的左c是p的右那么先以p为旋转点进行左单旋再以g为旋转点进行右单旋再把c变黑g变红即可。c变成课这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。 如果p是右子树cur是左子树 如果p是g的右c是p的左那么先以p为旋转点进行右单旋再以g为旋转点进行左单旋再把c变黑g变红即可。c变成课这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。 2.3 代码实现
bool Insert(const k x, const v v)
{if (_root nullptr)//插入根节点{_root new node(x, v);return true;}node* cur _root;node* parent nullptr;//保留父亲节点while (cur){/*介质不冗余*/if (x cur-_key){parent cur;cur cur-left;}else if (x cur-_key){parent cur;cur cur-right;}else{return false;}}cur new node(x, v);cur-col RED;if (x parent-_key){parent-right cur;}else//相等插入左子树{parent-left cur;}cur-parent parent;while (parentparent-parentparent-col RED){node* grandfather parent-parent;if (parent grandfather-left){node* uncle grandfather-right;// g// p u// c c//u存在且为红if (uncleuncle-colRED){parent-col uncle-colBLACK;grandfather-col RED;cur grandfather;parent cur-parent;}//u不存在或存在为黑else{// g// p // cif (cur parent-left){RoRateR(grandfather);parent-col BLACK;grandfather-col RED;}// g// p // celse{RoRateL(parent);RoRateR(grandfather);cur-col BLACK;grandfather-col RED;}break;}}else{node* uncle grandfather-left;// g// u p // c c//u存在且为红if (uncle uncle-col RED){parent-col uncle-col BLACK;grandfather-col RED;cur grandfather;parent cur-parent;}//u不存在或存在为黑else{// g// p // cif (cur parent-right){RoRateL(grandfather);parent-col BLACK;grandfather-col RED;}// g// p // celse{RoRateR(parent);RoRateL(grandfather);cur-col BLACK;grandfather-col RED;}break;}}}_root-col BLACK;//循环结束把根变黑return true;
}
三.红黑树的查找
红黑树的查找和AVL树的规则一样。 对比根节点和目标值的大小再取左子树或右子树查找。
node* Find(const k x)
{node* ret nullptr;node* cur _root;while (cur){if (x cur-_key){cur cur-left;}else if (x cur-_key){cur cur-right;}else{ret cur;//保留当前节点cur cur-left;//继续向左子树查找中序的第一个}}return ret;
}四.红黑树的验证
4.1 思路分析
我们检查红黑树主要检查是否满足红黑树的规则即可。
4.2 代码实现 bool check(node* cur,size_t tmp,size_t sum)
{if (cur nullptr){if (tmp ! sum){cout 存在⿊⾊结点的数量不相等的路径 endl;return false;}return true;}if (cur-col RED){if (cur-parent-col RED){cout cur-_key : 存在连续红节点 endl;return false;}}else{sum;}return check(cur-left, tmp, sum) check(cur-right, tmp, sum);
}
bool ISRBTree()
{return _ISRBTree(_root);
}
bool _ISRBTree(node* cur)
{if (cur nullptr){return true;}if (cur-col RED){return false;}size_t t 0;while (cur){if (cur-col BLACK){t;}cur cur-left;}return check(_root,t,0);
}这里我们通过几组数据来看一下AVL树和红黑树的性能。
void Test()
{const int N 100000;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();AVL::AVLTreeint, int t;for (auto e : v){t.Insert(e, e);}size_t end2 clock();size_t begin3 clock();RBTree::RBTreeint, int t1;for (auto e : v){t1.Insert(e, e);}size_t end3 clock();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();size_t begin4 clock();for (size_t i 0; i N; i){t1.Find((rand() i));}size_t end4 clock();cout AVLInsert: end2 - begin2 endl;cout AVLTree:t.IsBalanceTree() endl;cout AVLHeight: t.Height() endl;cout AVLSize: t.Size() endl;cout AVLFind: end1 - begin1 endl;cout RBInsert: end3 - begin3 endl;cout RBTree: t1.ISRBTree() endl;cout RBHeight: t1.Height() endl;cout RBSize: t1.Size() endl;cout RBFind: end4 - begin4 endl;
}Debug 10万数据 100万数据 1000万数据 Release 10万数据 100万数据 1000万数据
观察数据可以发现红黑树的查找比AVL要慢一些 在release下查找效率都一样因为CPU太快了。 但是红黑树在大量数据插入的情况下比AVL树要不少。
后言 这就是红黑树的深度剖析。大家自己好好消化今天就分享到这感谢各位的耐心垂阅咱们下期见拜拜~
