红黑树
红黑树
  定义
    根叶黑（根和叶子是黑色结点）
    不红红（两个红色结点不相邻）
    黑路同（简单路径黑结点同数量）
    转化为234树
  插入
    插入
      根结点黑色
      新节点红色
      下面讨论的
所有情况
    调整
      父结点为黑色
        不用调整
      1. 父结点红色
2. 无或黑色叔父结点
        RR
        LL
        RL
        LR
      1. 父结点红色
2. 红色叔父结点
        四种情况思路一样
  删除
    删除
      转化为删除最后一行元素
    调整
      删红结点
        直接删
      删黑结点
        有两个红色子结点
          不存在这种情况
会转化为对它子结点的删除
        有一个红色子结点
          用子结点替代（替代-删除-染色）
        无一个红色子结点
/黑色叶子结点
          删除结点为根结点，直接删除
          删除结点兄弟黑色
            兄弟结点有红色子结点
借用兄弟结点子结点修复
i. 删除结点后旋转
ii. 中心节点染为父结点颜色
iii. 两叶子结点黑色
              ①兄弟结点有红色子【1】个结点，LL（或RR）
              ②兄弟结点有红色子【1】个结点，LR（或RL）
              ③兄弟结点有红色子【2】个结点，转化为LL/RR
            兄弟结点【无】红色子结点
父结点向下合并
              ④红色父结点，不用旋转了，直接染色～
              ⑤黑色父结点（下边有个递归的案例）
              黑色父结点 - 递归的案例
          删除结点兄弟红色
（转变为兄弟黑色）
            旋转+变色