一、概念

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

2、红黑树规则

a、每个节点不是红色就是黑色

b、根节点是黑色的

c、如果一个节点是红色的，则它的两个节点必须是黑色的，也就是说一条路径不会右连续的红色节点

d、对应任意一个节点，从该节点到其他所有NULL节点的简单路径上，均包含相同数量的黑色节点

3、效率是logN

4、如何确保最长路径不超过最短路径的2倍

a、由规则4，从根到NULL节点的每条路径都有相同数量的黑色节点，所以极端场景下，最短路径就是全黑节点的路径，假设为bh

b、由规则2和3可知，任意一条路径不会由连续的红色节点，所以极端场景下，最长路径就是一黑一红间隔组成，那么最长路径就是2*bh

c、综合4点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每颗红黑树都存在的。假设任意一条从根到NULL节点路径的长度为x，那么bh<=h<=2*bh

 

二、红黑树的实现

1、红黑树的结构

2、红黑树插入

a、插入一个值安二叉搜索树规则插入，插入后我们只需观察是否符合红黑树的4条规则

b、如果空树插入，新增节点是黑色节点。如果是非空树插入，新增节点必须红色节点，因为非空树插入，新增节点就破坏了规则4，规则4很难维护

c、非空树插入，新增节点必须是红色，如果父亲节点是黑色，则没有违反规则，擦汗如结束

d、非空树插入后，新增节点必须红色节点，如果父亲节点是红色，则违反规则3。进一步分析，c是红色，p是红，g必是黑，这3个颜色就固定了，关键看u的变化，需要根据u分为以下几种情况分别处理

3、情况一：变色不旋转

c为红，p为红，g为黑。u存在且为红，则将p和u变黑，g变红。把g当做新的c，继续往上更新。

如图

情况2：单选+变色

c为红，p为红，u不存在或者存在且为黑；u不存在，则c一定是新增节点；u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入。

情况3：双旋+变色

c红，p为红，g为黑，u不存在或者u存在且为黑；u不存在，则c一定新增节点；u存在且为黑，则c一定不是新增，c之前是黑色，是在z子树中插入

三、红黑树验证

a、规则1枚举颜色类型，天然得证就是红黑树

b、规则2直接检查根

c、规则3前序遍历检查，遇红查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了

d、规则4，遍历过程中用形参记录跟前节点blackNum，前序遍历遇到黑就++bNum，走到空就计算出了一条路径的黑个数，再任意一条路径黑数量作参考依次比较即可。

 

trying to do better！