红黑树

特征

• 节点都有颜色
• 在插入和删除的过程中，要遵循保持这些颜色的不同排列规则

规则

• 每个节点不是红色就是黑色的
• 根节点总是黑色的
• 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）,(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

  注意：新插入的节点颜色总是红色的，这是因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小，原因是插入黑色节点总会改变黑色高度（违背规则4），但是插入红色节点只有一半的机会会违背规则3（因为父节点是黑色的没事，父节点是红色的就违背规则3）。

修正

插入新节点可能会破坏规则，有2种修正方法，变色跟旋转，旋转分左旋转跟右旋转

左旋转

• 子右节点Y上升为父节点
• 父节点X降级为子左节点
• 把旧子右节点Y的子左节点搞过来当子新左节点子X的子右节点

  X                                             Y
 / \              以X为轴旋转                  / \
a   Y              ------------->>            X   c
   / \                                       / \
  b   c                                     a   b

右旋转

• 子左节点Y上升为父节点
• 父节点X降级为子右节点
• 把旧子左节点Y的子右节点搞过来当新子右节点X的子左节点

    X                                             Y
   / \              以X为轴旋转                  / \
  Y   c              ------------->>            a   X
 / \                                               / \
a   b                                             b   c

多看几次就懂了，明白旋转规则即可