C++进阶 红黑树
一.红黑树的概念
红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路 径⻓出2倍，因⽽是接近平衡的。
二.红黑树的规则
1. 节点非红即黑
2. 根节点必须黑
3. 红红不能相连
4. 任意路径黑节点数相同
红黑树如何确保最长路径不超过最短路径的2倍的？
由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径 就就是全是⿊⾊结点的路径，假设最短路径⻓度为bh(blackheight)。
由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀ ⿊⼀红间隔组成，那么最⻓路径的⻓度为2*bh。
综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都 存在的。假设任意⼀条从根到NULL结点路径的⻓度为h，那么bh<=h<=2*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：根节点必须是黑色
规则3：NIL节点为黑色
nullptr默认视为黑色，天然满足。
规则4：红节点不能有红孩子
规则5：所有路径黑节点数相同
先求出最左路径黑节点数作为标准值。
递归检查
完整验证函数：