C++进阶 红黑树

一.红黑树的概念红⿊树是⼀棵⼆叉搜索树他的每个结点增加⼀个存储位来表⽰结点的颜⾊可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束红⿊树确保没有⼀条路径会⽐其他路 径⻓出2倍因⽽是接近平衡的。二.红黑树的规则1. 节点非红即黑2. 根节点必须黑3. 红红不能相连4. 任意路径黑节点数相同红黑树如何确保最长路径不超过最短路径的2倍的由规则4可知从根到NULL结点的每条路径都有相同数量的⿊⾊结点所以极端场景下最短路径 就就是全是⿊⾊结点的路径假设最短路径⻓度为bh(blackheight)。由规则2和规则3可知任意⼀条路径不会有连续的红⾊结点所以极端场景下最⻓的路径就是⼀ ⿊⼀红间隔组成那么最⻓路径的⻓度为2*bh。综合红⿊树的4点规则⽽⾔理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都 存在的。假设任意⼀条从根到NULL结点路径的⻓度为h那么bhh2*bh。三.红黑树的实现左旋和 AVL 树完全一样。右旋四.红黑树的插入1. 插入⼀个值按⼆叉搜索树规则进行插入插入后我们只需要观察是否符合红黑树的4条规则。2. 如果是空树插新增结点是黑色结点。如果是非空树插入新增结点必须红色结点因为⾮空树 插⼊新增黑色结点就破坏了规则4规则4是很难维护的。3. 非空树插入后新增结点必须红色结点如果父亲结点是黑色的则没有违反任何规则插入结束 4. 非空树插入后新增结点必须红黑、色结点如果父亲结点是红色的则违反规则3。进⼀步分析c是 红色p为红g必为黑这三个颜色都固定了关键的变化看u的情况需要根据u分为以下几种 情况分别处理。情况1叔叔存在且为红处理p变黑u变黑g变红处理完后继续把g替换为从c继续向上调整情况2叔叔黑且是直线如果p是g的左c是p的左那么以g为旋转点进行右单旋再把p变黑g变红即可。p变成课这颗树新 的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则如果p是g的右c是p的右那么以g为旋转点进行左单旋再把p变黑g变红即可。p变成课这颗树新 的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为p的父亲是黑色还是红色或者空都不违反规则情况3叔叔黑且是折线图1图2如果p是g的左c是p的右那么先以p为旋转点进行左单旋再以g为旋转点进行右单旋再把c变黑g变红即可。c变成课这颗树新的根这样⼦树黑色结点的数量不变没有连续的红色结点了且 不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则如果p是g的右c是p的左那么先以p为旋转点进⾏右单旋再以g为旋转点进行左单旋再把c变黑g变红即可。c变成课这颗树新的根这样⼦树黑色结点的数量不变没有连续的红色结点了且 不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则完整代码在文章最后五.红黑树的验证规则1节点非红即黑天然保证不需要检查。规则2根节点必须是黑色规则3NIL节点为黑色nullptr默认视为黑色天然满足。规则4红节点不能有红孩子规则5所有路径黑节点数相同先求出最左路径黑节点数作为标准值。递归检查完整验证函数六.插入完整代码