个人博客

红黑树

TIP

红黑树(red-black-tree)，一种较为平衡的二叉搜索树，也是开发中用得最多的一种平衡树

五条规则

红黑树除了符合二叉搜索树的基本规则外，还添加了以下特性：

  • 规则 1：节点是红色或黑色的
  • 规则 2：根节点是黑色的
  • 规则 3：每个叶子节点都是黑色的空节点（NIL 节点）
  • 规则 4：每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不可能有两个连续的红色节点）
  • 规则 5：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

如图，一颗红黑树：

tree

相对平衡

前面 5 条规则的约束确保了以下红黑树的关键特性：

  • 从根到叶子节点的最长路径，不会超过最短路径的两倍
  • 结果就是这棵树基本是平衡的
  • 虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，该树依然是高效的

为什么可以做到最长路径不超过最短路径的两倍呢？

  • 性质 4 决定了路径上不能有两个相连的红色节点
  • 所以，最长路径一定是红色节点和黑色节点交替而成的
  • 由于根节点和叶子节点都是黑色的，最短路径可能都是黑色节点，并且最长路径中一定是黑色节点多于红色节点
  • 性质 5 决定了所有路径上都有相同数目的黑色节点
  • 这就表明了没有路径能多于其他任何路径两倍长。

三种变换

插入一个新节点时，有可能树不再平衡，可以通过三种方式的变换使树保持平衡：

  • 变色
  • 左旋转
  • 右旋转

变色

  • 把红色节点变为黑色，或者把黑色节点变为红色

左旋转

以节点 X 为根逆时针旋转二叉搜索树，使得父节点原来的位置被自己的右子节点替代，左子节点的位置被父节点替代，如下图：

tree

旋转结果

  • 节点 X 取代了节点 a 原来的位置
  • 节点 Y 取代了节点 X 原来的位置；
  • 节点 X 的左子树 a 仍然是节点 X 的左子树（这里 X 的左子树只有一个节点，有多个节点时同样适用，以下同理）
  • 节点 Y 的右子树 c 仍然是节点 Y 的右子树
  • 节点 Y 的左子树 b 向左平移成为了节点 X 的右子树

二叉搜索树左旋转之后仍为二叉搜索树

tree

右旋转

以节点 X 为根顺时针旋转二叉搜索树，使得父节点原来的位置被自己的左子节点替代，右子节点的位置被父节点替代，如下图：

tree

旋转结果

  • 节点 X 取代了节点 a 原来的位置
  • 节点 Y 取代了节点 X 原来的位置；
  • 节点 X 的右子树 a 仍然是节点 X 的右子树（这里 X 的右子树虽然只有一个节点，但是多个节点时同样适用，以下同理）
  • 节点 Y 的左子树 b 仍然是节点 Y 的左子树
  • 节点 Y 的右子树 c 向右平移成为了节点 X 的左子树

二叉搜索树右旋转之后仍为二叉搜索树

tree

插入

  • 插入的新节点通常都是红色节点
    1. 当插入的节点为红色的时候，大多数情况不违反红黑树的任何规则
    2. 而插入黑色节点，必然会导致一条路径上多了一个黑色节点，这是很难调整的
    3. 红色节点虽然可能导致红红相连的情况，但是这种情况可以通过颜色调换和旋转来调整
  • 新插入节点为 N（Node），N 的父节点为 P（Parent），P 的兄弟节点为 U（Uncle），U 的父节点为 G（Grandpa）

tree

情况 1

  • 当插入的新节点 N 位于树的根上时，没有父节点
  • 这种情况下，只需要将红色节点变为黑色节点即可满足规则 2

tree

情况 2

  • 当新节点 N 的父节点 P 为黑色节点，此时不需要任何变化
  • 此时既满足规则 4 也满足规则 5。尽管新节点是红色的，但是新节点 N 有两个黑色节点 NIL，所以通向它的路径上黑色节点的个数依然相等，因此满足规则 5

tree

情况 3

  • 节点 P 为红色，节点 U 也为红色，此时节点 G 必为黑色，即父红叔红祖黑
  • 变换步骤
    1. 先将父节点 P 变为黑色
    2. 将叔叔节点 U 变为黑色
    3. 最后将祖父节点 G 变为红色
    4. 变化速记：父红叔红祖黑 -> 父黑叔黑祖红

tree

  • 可能出现的问题：
    1. N 的祖父节点 G 的父节点也可能是红色，需要递归来调整节点颜色
    2. 如果递归到根节点的时候，仍然有问题就需要旋转处理了

tree

情况 4

  • 节点 P 为红色，节点 U 为黑色，并且节点 N 为节点 P 的左子节点，此时节点 G 一定是黑色节点，即父红叔黑祖黑
  • 变换步骤
    1. 先变色：将父节点 P 变为黑色，将祖父节点 G 变为红色
    2. 后旋转：以祖父节点 G 为根进行右旋转
    3. 变化速记：父红叔黑祖黑 -> 父黑，祖红，右旋转

tree

情况 5

  • 节点 P 为红色，节点 U 为黑色，并且节点 N 为节点 P 的右子节点，此时节点 G 一定是黑色节点，即父红叔黑祖黑
  • 情况 5 的变换步骤
    1. 先以节点 P 为根进行左旋转，旋转后如图(b)所示
    2. 随后将红色节点 P 和黑色节点 B 看成一个整体的红色节点 N1，将新插入的红色节点 N 看成红色节点 P1 如图(c)所示。此时整体就转换为了情况 4

tree

  • 情况 4 的变化步骤
    1. 先变色：将 N1 节点的父节点 P1 变为黑色，将祖父节点 G 变为红色
    2. 后旋转：以祖父节点 G 为根进行右旋转，旋转后如图(e)所示
    3. 最后将节点 N1 和 P1 变换回来，完成节点 N 的插入，如图(f)所示

tree

案例演示

在二叉树中依次插入节点：10，9，8，7，6，5，4，3，2，1

(1) 如果直接采用普通的二叉搜索树，节点全部插入后是一个严重的不平衡树，相当于一个链表，不能体现出二叉搜索树的高效率，结果如下图：

tree

(2) 如果按照红黑树的五条规则插入节点就能最大程度保证搜索二叉树是一棵平衡树，以下为过程详解：为了方便解释省略了部分红黑树的叶子节点（NIL）

插入 10

  • 符合情况 1 - 根节点为红
  • 插入节点 10
  • 将节点 10 的颜色变为黑色(变色)

tree

插入 9

  • 符合情况 2
  • 直接插入，不需要任何变化

tree

插入 8

  • 符合情况 4 - 当前为父红叔黑祖黑
  • 父黑(父节点 9 变成黑)，祖红(祖父节点 10 变为红) (变色)
  • 以祖父节点 10 为根进行右旋转(右旋转)

tree

插入 7

  • 符合情况 3 - 当前为父红叔红祖黑
  • 父黑(父节点 8 变成黑)，叔黑(叔节点 10 变成黑)，祖红(祖父节点 9 变为红) (变色)
  • 此时会出现问题：不符合规则 2，即根节点 9 不为红
  • 只需要把 9 变回黑色 (变色)

tree

插入 6

  • 符合情况 4 - 当前为父红叔黑祖黑
  • 父黑(父节点 7 变成黑)，祖红(祖父节点 8 变为红) (变色)
  • 以祖父节点 8 为根进行右旋转(右旋转)

tree

插入 5

  • 符合情况 3 - 当前为父红叔红祖黑
  • 父黑(父节点 6 变成黑)，叔黑(叔节点 8 变成黑)，祖红(祖父节点 7 变为红) (变色)

tree

插入 4

  • 符合情况 4 - 当前为父红叔黑祖黑
  • 父黑(父节点 5 变成黑)，祖红(祖父节点 6 变为红) (变色)
  • 以祖父节点 6 为根进行右旋转(右旋转)

tree

插入 3

第一次变换

  • 符合情况 3 - 当前为父红叔红祖黑
  • 父黑(父节点 4 变成黑)，叔黑(叔节点 6 变成黑)，祖红(祖父节点 5 变为红) (变色)
  • 变换之后发现 5 和 7 为相连的两个红色节点，于是把以 5 为根的整个子树看成一个新插入的节点 N1，再进行第二次变换

tree

第二次变换

  • 符合情况 4 - 当前为父红叔黑祖黑
  • 父黑(父节点 7 变成黑)，祖红(祖父节点 9 变为红) (变色)
  • 以祖父节点 9 为根进行右旋转(右旋转)
  • 最后将 N1 复原，如下：

tree

插入 2

  • 符合情况 4 - 当前为父红叔黑祖黑
  • 父黑(父节点 3 变成黑)，祖红(祖父节点 4 变为红) (变色)
  • 以祖父节点 4 为根进行右旋转(右旋转)

tree

插入 1

第一次变换

  • 符合情况 3 - 当前为父红叔红祖黑
  • 父黑(父节点 2 变成黑)，叔黑(叔节点 4 变成黑)，祖红(祖父节点 3 变为红) (变色)
  • 变换之后发现 3 和 5 为相连的两个红色节点，于是把以 3 为根的整个子树看成一个新插入的节点 N1，再进行第二次变换

tree

第二次变换

  • 符合情况 3 - 当前为父红叔红祖黑
  • 父黑(父节点 5 变成黑)，叔黑(叔节点 9 变成黑)，祖红(祖父节点 7 变为红) (变色)
  • 变换之后发现根节点 7 为红色不符合规则 2，所以把以 7 为根节点的红黑树看成一个新插入的节点 N2，再进行第三次变换

tree

第三次变换

  • 符合情况 1 - 根节点为红
  • 将节点 7 的颜色变为黑色(变色)

tree

完整图

tree