红黑树

特征

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

规则

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

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

修正

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

左旋转

  • 子右节点Y上升为父节点
  • 父节点X降级为子左节点
  • 把旧子右节点Y的子左节点搞过来当子新左节点子X的子右节点
1
2
3
4
5
  X                                             Y
/ \ 以X为轴旋转 / \
a Y ------------->> X c
/ \ / \
b c a b

右旋转

  • 子左节点Y上升为父节点
  • 父节点X降级为子右节点
  • 把旧子左节点Y的子右节点搞过来当新子右节点X的子左节点
1
2
3
4
5
    X                                             Y
/ \ 以X为轴旋转 / \
Y c ------------->> a X
/ \ / \
a b b c

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