网站在百度无法验证码怎么办啊,wordpress 文章目录插件,网站备案正常多久,健身俱乐部网站建设方案设计#x1f493;博主CSDN主页:杭电码农-NEO#x1f493; ⏩专栏分类:C从入门到精通⏪ #x1f69a;代码仓库:NEO的学习日记#x1f69a; #x1f339;关注我#x1faf5;带你学习C #x1f51d;#x1f51d; 红黑树 1. 前言2. 红黑树的概念以及性质3. 红黑… 博主CSDN主页:杭电码农-NEO ⏩专栏分类:C从入门到精通⏪ 代码仓库:NEO的学习日记 关注我带你学习C 红黑树 1. 前言2. 红黑树的概念以及性质3. 红黑树为什么更实用?4. 红黑树模拟实现代码框架5. 红黑树的插入操作初步分析6. 红黑树的插入操作详解(一)7. 红黑树的插入操作详解(二)8. 红黑树的插入代码实现9. 总结以及拓展 1. 前言
如果说发明AVL树的人是天才,那么 发明红黑树的人可以称为天才中的 精英!为什么AVL树这么强大但是没啥 人用呢?就是因为红黑树比你还好!
本章重点: 本篇文章着重讲解红黑树的概念以及 性质,以及为了维护红黑树这种性质而 做的限制条件.最后模拟实现红黑树的 插入,带大家熟悉变色和旋转规则! 2. 红黑树的概念以及性质
红黑树的概念:
首先红黑树是一颗二叉搜索树每个节点都有颜色,红色或黑色最长路径最多是最短路径的二倍 红黑树的性质:
每个结点不是红色就是黑色根节点是黑色的 如果一个节点是红色的 则它的两个孩子结点是黑色的每条路径上的黑色节点数相同每个叶子结点都是黑色的 (此处的叶子结点指的是空结点)
为啥满足了以上性质的红黑树就一定
能做到最长路径最多是最短路径的二倍?
下面我画一个极限情况来分析一下!3. 红黑树为什么更实用?
现在将AVL数和红黑树做一个对比:
AVL树阐析: AVL树是一颗高度平衡二叉树, 它的高度差不能大于1,所以AVL 树的查找是妥妥的O(logn),但是 由于AVL树严格的标准,使得在使用 AVL树时会经常旋转,反而增加了时间! 红黑树阐析: 红黑树是一颗接近平衡的二叉树 它最长路径最多是最短路径的二倍 所以查找的效率是:logn~2logn, 然而2logn和logn是一个量级的, 并且红黑树的规则没有这么严格, 不会涉及到更多旋转和变色! 综上所述,红黑树的效率虽然比
AVL树差一点,但是总体来说红黑树胜!4. 红黑树模拟实现代码框架
首先,每个节点都要存一个颜色, 这里我们使用枚举enum来实现 并且和AVL一样也是三叉链! 请看代码:
enum Colour
{RED,BLACK
};
templateclass K,class V
struct RBTreeNode
{RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv; Colour _col;
};templateclass K, class V
struct RBTree
{
typedef RBTreeNodeK, V Node;
private:Node* _root nullptr;
};有了代码框架后,现在来看看插入 5. 红黑树的插入操作初步分析
和AVL树很相似,红黑树的插入 也是分为两步走:
按照二叉搜索树的规则插入值插入后根据颜色或高度做旋转或变色
众所周知啊,第一步很简单 甚至可以将之前的代码抄过来:
bool insert(const pairK, V kv)//第一步:按照二叉搜索树的方式插入值
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;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);if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;//此时new出来的节点的parent还指向空cur-_parent parent;///前面的过程和AVL树一致
}走到这步后,有个问题,新插入的节点 是选择插入红色还是黑色? 对于这个问题,我们要思考两个点, 一是如果插入的是黑色节点,我们 可能会打破哪个规则?如果是插入 红色节点又可能会打破哪个规则? 插入黑色节点,打破规则四,很难办 因为每个路径检查起来很难! 插入红色节点,打破规则三,比打破 四要好一些,因为只用看父亲是否为红
综上所述,插入红色更优!
换句话说,你犯错肯定宁愿犯轻一点
的错误被妈妈打一顿,也不愿意犯很重
的错直接被家族除名了对吧[doge]6. 红黑树的插入操作详解(一)
如果插入的节点的父亲是黑色节点, 那么正是我们想看见的,不用管它了!
那么如果插入的节点的父亲是红色呢? 很明显,这违反了规则三,有连续的红色 节点,所以此时需要做处理了!
先来看一个最简单的情况: 其实红黑树插入节点后的变色和 旋转规则主要是看叔叔,叔叔的情况 不同,那么对应的处理手段就不同,这里 只通过简单变色手段就可以满足规则了! 并且在上图中,将爷爷变成红色后可能会 出现问题,因为爷爷的父亲不知道是红色 还是黑色,所以要不断向上做判断 若不向上更新,可能会有这种情况: 7. 红黑树的插入操作详解(二)
当讲解完最简单的情况后,还剩下两种 情况,这两种情况内部又可细分出几种 情况,请同学们耐心学习!
情况二:cur为红.p为红.g为黑.u不存在/为黑 (并且cur和p都是左或右) p为g的左孩子,cur为p的左孩子,则右单旋 p为g的右孩子,cur为p的右孩子,则左单旋 p,g变色—p变黑g变红 情况三:cur为红.p为红.g为黑.u不存在/为黑 (并且若p是g的左,cur就是p的右) p为g的左孩子,cur为p的右孩子,则做左单旋 p为g的右孩子,cur为p的左孩子,则做右单旋 则转换成了情况二 至此,红黑树的插入的所有情况都 讲解完毕,接下来就是代码实现了! 8. 红黑树的插入代码实现
在整个大情况分类中,可以归为两类 一是叔叔为红色,二是叔叔为黑色或者 叔叔不存在,我们围绕着这两个大方向写!
//走到这一步后,就已经找到cur和parent了!
while (parent parent-_col RED)//当parent为黑就不用往上更新了
{if (parent _root){_root-_col BLACK;break;}Node* grandf parent-_parent;assert(grandf);assert(grandf-_col BLACK);Node* uncle nullptr;if (parent grandf-_left)//判断叔叔在par的左还是右uncle grandf-_right;else uncle grandf-_left;if (uncle nullptr || uncle-_col BLACK)//uncle为空或为黑有四种情况来变色旋转{if (parent grandf-_left cur parent-_left)//左左-右旋变色{RotateR(grandf);parent-_col BLACK;grandf-_col RED;break;}else if (parent grandf-_right cur parent-_right)//右右-左旋变色{RotateL(grandf);parent-_col BLACK;grandf-_col RED;break;}else if (parent grandf-_left cur parent-_right)//左右-先左旋再右旋再变色{RotateL(parent);RotateR(grandf);cur-_col BLACK;grandf-_col RED;break;}else if (parent grandf-_right cur parent-_left)//右左-先右旋再左旋再变色{RotateR(parent);RotateL(grandf);cur-_col BLACK;grandf-_col RED;break;}}else if (uncle uncle-_col RED)//叔叔为红,直接变色,不旋转{parent-_col BLACK;uncle-_col BLACK;grandf-_col RED;cur grandf;parent cur-_parent;//将parent更新后往上传!}_root-_col BLACK;
}可以发现一个问题,只要是叔叔的颜色 是黑色或叔叔不存在的情况下,执行完 旋转变色后都直接break了,这是因为 在这种情况下,父亲节点都被变成了黑色, 也就没必要继续往上了!并且在红黑树的 左旋和右旋中,代码其实和AVL树的旋转是 一模一样的,所以直接copy一份就行了! 若你不清楚旋转的代码,请看这篇文章:
AVL树模拟实现! 9. 总结以及拓展
AVL树和红黑树的代码实现都只讲解 了插入操作,因为删除操作太复杂了, 并且就算实现了删除操作也没有太大 的实际意义,所以只需要了解插入即可!
并不是需要你真正的会手撕!
拓展阅读:
红黑树的删除图解 下期预告:哈希表,哈希桶
