《红黑树实现》

引言：

上次我们学习了比二叉搜索树更高效的平衡二叉搜索树（AVL树），这次我们要学习的是另外一种对二叉搜索树的优化后的红黑树。

一：红黑树概念：

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

（1）红黑树规则：

1. 每个结点不是红色就是黑色。
2. 根结点是黑色的。
3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。

（2）思考：红黑树是如何确保最长路径不超过最短路径的2倍的？

1. 由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是黑色结点的路径，假设最短路径长度为bh(black height)。
2. 由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为2*bh。
3. 综合红黑树的4点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意⼀条从根到NULL结点路径的长度为x，那么bh <= h <= 2*bh。

（3）红黑树效率：

假设N是红黑树中节点的数量，h为最短路径的长度，那么2^h - 1 <= N < 2 ^ (2 * h) - 1 ，由此推出h ≈ logN ，也就是意味着红黑树的增删查改最坏情况下也就是走最长路径时的效率也是logN 。
但红黑树的表达相对于AVL树要抽象一些，AVL树是通过高度差来直观地控制，红黑树通过4条规则的颜色约束，间接实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

二：红黑树的实现

1. 红黑树的结构：

跟前面实现的AVL树相比，红黑树的结构只是将平衡因子变为了颜色记录。

2. 红黑树的插入：

（1）约定：

下面我们分析时的各节点命名：
下图中假设我们把新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为g(grandfather)，p的兄弟标识为u（uncle）。

（2）红黑树插入的大致流程：

1. 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则。
2. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须为红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的。
3. 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束。
4. 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进一步分析，c是红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。

（3）情况1：u存在且为红（只变色）

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的左还是右，都是上面的变色处理方式。

a. 具体示例：

b. 抽象示例：

情况1代码实现：

（4）情况2：u 不存在或者存在且为黑（单旋＋变色）

1. c为红，p为红，g为黑，u不存在或者u存在且为黑
2. 若u不存在，则c⼀定是新增结点，
3. u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
   分析：p必须变黑，才能解决连续红黑结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。

单旋＋变色代码实现：

情况2：u 不存在或者 u 存在且为黑（双旋＋变色）

1. c为红，p为红，g为黑，u不存在或者u存在且为黑。
2. u不存在，则c一定是新增结点，
3. u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
   分析：p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。

双旋＋变色 代码实现：

当 p u 位置反过来时的代码：

3. 红黑树的查找：

按二叉搜索树的逻辑实现即可，搜索效率为O(logN)。

4. 红黑树的验证

这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查4点规则，满足这4点规则，一定能保证最长路径不超过最短路径的2倍。

1. 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
2. 规则2直接检查根即可。
3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了。
4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。

5. 测试：

（1）插入及其合法性验证：

（2）性能测试：

完结！！！