#
红黑树（上）
一、平衡条件
- 节点非黑既红
- 根节点是黑色
- 叶子（NIL）结点是黑色
- 红色节点下面接两个黑色节点
- 从根节点到叶子结点路径上，黑色节点数量相同
平衡条件的认识
第4条和第5条条件，注定了，红黑树中最长路径是最短路径的长度的 2 倍。
本质上，红黑树也是通过树高来控制平衡的。
红黑树比 AVL 树树高控制条件要更松散，红黑树在发生节点插入和删除以后，发生调整的概率，比 AVL 树要更小。
二、学习诀窍
- 理解红黑树的插入调整，要站在==祖父节点==向下进行调整
- 理解红黑树的删除调整，要站在==父节点==向下进行调整
- 插入调整，主要就是为了解决双红情况
- 新插入的节点一定是红色，插入黑色节点一定会产生冲突，违反条件5，插入红色节点，不一定产生冲突
- 把每一种情况，想象成一棵大的红黑树中的局部子树
- 局部调整的时候，为了不影响全局，调整前后的路径上黑色节点数量相同
三、插入策略
- 叔叔节点为红色的时候，修改三元组小帽子，改成红黑黑
- 叔叔节点为黑色的时候，参考 AVL 树的失衡情况，分成 $LL,LR,RL,RR$, 先参考 AVL 树的旋转调整策略，然后再修改三元组的颜色，有两种调整策略：红色上浮，红色下沉。
- 两大类情况，包含 8 种小情况
四、代码演示
- 插入调整，发正在递归的回溯阶段
- 插入调整代码中，使用 goto 语句，8行代码，变成了4行
- 处理根节点一定是黑色，通过代码封装，$insert->__insert$