红黑树的本质依然是二叉搜索树，认为不存在相同的节点。
最近在学map、set，二者的底层数据结构都是红黑树。所以复习一下红黑树。
对于一颗红黑树，插入节点的大致流程是：插入新节点-判断当前状态是否失衡-失衡调节-插入完成。
一颗红黑树，需要满足以下基本条件
- 只有红黑节点（顾名思义）
- 根节点是黑节点
- 黑同路：树上每个节点，到它的任意叶子节点，黑色节点的数量相同
- 红孤单：红节点不允许连续
- 路径长度：从根节点到某个叶子节点的所有路径里，不存在一条路径，长度大于另一条路径的2倍
关于黑同路，其实就是在红黑树上任选2个点，分别作为起点和终点，那么两点之间的任何路径，经过的黑色节点都是一样的。
补充的：黑色节点是可以连续的；且一个节点的孩子可以一个是红、一个是黑。
只是插入新节点之前，还有两个问题需要澄清一下：
- 新节点插入到哪个地方？
- 插入的新节点，选择什么颜色？
新节点插入在什么地方？
只要哪个节点的子节点没满，那都可以插入。
插入的新节点，选什么颜色？
那就分类讨论一下：
- 插入的新节点是黑色
根据红黑树的黑同路性质，一颗正常、未失衡的红黑树，必定满足黑同路，也即——每个节点到任一叶子节点的路径，黑节点相同。
那么，如果插入一个新的黑节点，那必定会导致所有经过它的路径，都多了1个黑节点，破坏了性质，就需要失衡调节。- 插入的新节点是红色
如果新节点的父亲是黑色，那么插入之后，依然不会破坏红黑树的性质。总而言之一句话：如果插入的是黑节点，那么必定需要失衡调节；如果插入的是红节点，至少有时候可以不用调节。
对于插入节点，我们给与它相关的节点都取个名字，方便后续表示。
[这里要插一张图]
- cur：current，表示插入的新节点
- par：parent，cur节点的父节点
- unc：uncle，cur节点的叔叔，或者说是par节点的兄弟
- gra：grand，cur节点的爷爷，也是par和unc的父节点
根据插入节点的位置和颜色情况，一共有3种分类方向，每种分类有2个可能，组合起来就是2×2×2=82 \times 2 \times 2 = 82×2×2=8种情况。
3种分类方向是：
- par节点在gra节点的左边还是右边，左边是L（left），右边是R（right）
- cur节点在par节点的左边还是右边，左边是L，右边是R
- cur节点的unc节点是红色还是黑色，黑色是B（black），红色是R（Red）
注：空节点视作黑节点，所以如果爷爷节点只有1个孩子，那么cur节点的叔叔视作黑色
接下来开始分类讨论如何失衡调节。
大类1：叔叔是红色（XXR）
叔叔是红色，那么一共就有如下情况：LLR、LRR、RLR、RRR
LLR
来确认一下图中情况是否是LLR：
- L：父亲在爷爷的左边
- L：自己在父亲的左边
- R：叔叔的颜色是红色
调节方式是：
- 父亲、叔叔染黑
- 爷爷染红
调节之后如图，可判断是否满足红黑树的基本性质。
看上去挺简单的，那么把情况扩展成一般情况：
用相同方式调节之后，可以发现爷爷gra和自己的父节点都是红色，破坏了红黑树“红节点不能连续”的性质。
对于这种情况，就需要把爷爷视作cur，相应的，也就有了新的par、unc、gra。
此时，再次按照父亲、叔叔染黑；爷爷染红的方式调节。
如此不断往上调整。
那什么时候调整结束呢？
- 当
cur是根节点时，红黑树平衡，结束调整。 - 或者当
cur的父节点是黑色，也结束调整。
最后，还得注意把根节点给涂黑。因为当cur是根节点的孙子时，调节时会把爷爷gra给染红，那不就是把根节点给染红了嘛。
LRR
- L：父亲在爷爷的左边
- R：自己在父亲的右边
- R：叔叔是红色
调节：
- 父亲、叔叔染黑；爷爷染红
- 接着
cur标签移到爷爷处，以同样的方式进行失衡调节 - 当
cur的父亲是黑色，或者自己本身是根节点时，结束循环，红黑树已平衡 - 将根节点染黑
RLR
- R：父亲在爷爷的右边
- L：自己在父亲的左边
- R：叔叔是红色
调节：
- 父亲、叔叔染黑；爷爷染红
cur移动到爷爷处，继续失衡判断- 当
cur父亲是黑色，或者自己是根节点时，结束循环 - 将根节点染黑
RRR
- R：父亲在爷爷的右边
- R：自己的爷爷的右边
- R：叔叔是红色
调节：同上
大类2：叔叔是黑色（XXB）
叔叔是黑色，当我把四种情况都画出来后，发现新插入节点的父亲是红色，且没有兄弟，空节点视为黑色。
LLB
- L：父亲在爷爷的左边
- L：自己在父亲的左边
- B：叔叔是黑色
调节：父黑爷红爷旋转
- 父亲染黑
- 爷爷染红
- 爷爷右旋
关于左右旋，我的理解是类似以前的手机游戏《吃糖果》。
节点右旋：说明该节点位于其子节点右上角，那么该节点就往右旋转”落下来“，变成了自己子节点的右孩子。如果碰到了子节点的右孩子，那就顶替它，把那条连线撞上去。
节点左旋：该节点位于其子节点的左上角，左旋就是它往左旋转”掉落“，变成自己子节点的左孩子。碰到子节点原本的左孩子，就顶替它。
