10.红黑树

特性：

1. 节点非红即黑
2. 根节点是黑
3. 叶子节点都是黑
4. 红节点的子节点或父节点都是黑
5. 从任一节点到叶子节点的所有路径都包含相同个数的黑节点
6. 红黑树等价4阶B树，由黑色节点与它的红色子节点合并成为一个节点

下图非红黑树，因为38节点有一条隐藏的路径往右空节点，此路径不满足特性5

添加操作：

节点共有4种情况，添加操作一共有12种情况

所有添加的节点默认为红色节点

不用做处理的情况

需要做处理的情况

LL/RR：单旋

LR/RL：双旋

LL+上溢

RR+上溢

LR+上溢

RL+上溢 参照 LR + 上溢

删除操作：

B树中，最后真正被删除的元素都在叶子节点中

删除红色节点不需要做处理

1. 拥有两个红色节点的黑色节点（不能直接删除，需要使用前驱或者后继节点替代删除）

2. 拥有一个红色节点的黑节点

   • 将替代的节点染黑

3. 单独一个黑节点（88）

   • 替代的子节点是黑色（空的黑色节点，不要再直接根据度来判断）

     • 当前节点没有元素，发生下溢，旋转，继承颜色，独立的B树节点染黑

     • 三种情况为兄弟为黑色节点，且有红色子节点可借

       
       

     • 两种情况为兄弟为黑色节点但无节点可借，区分点为父节点为红节点还是为黑节点

一种情况为兄弟是红色节点，那么先通过旋转达到上面的情况，再处理

红黑树的平衡：没有一条路径会大于其他路径的2倍，最短路径为全部黑节点，最长路径为黑节点=红节点，因为黑节点数量一致，所以不可能超过2倍

AVL树、红黑树对比