将 AVL 树转换为红黑树

Question

我在某处读到这样的说法，任何 AVL 树 T 的节点都可以着色 \xe2\x80\x9cred\xe2\x80\x9d 和 \xe2\x80\x9cblack\xe2\x80\x9d ，这样 T 就成为红黑树。

\n\n

这个说法看起来很有说服力，但我不明白如何正式证明这个说法。

\n\n

根据维基百科，红黑树应该满足以下五个属性：

\n\n

a 节点要么是红色，要么是黑色。

\n\n

b.根部呈黑色。这条规则有时会被省略。由于根总是可以从红色变为黑色，但不一定反之亦然，

\n\n

C。所有叶子 (NIL) 都是黑色的。

\n\n

d.如果一个节点是红色的，那么它的两个子节点都是黑色的。

\n\n

e.从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点。

\n\n

四个条件很简单，我被困住了如何证明陈述5

\n

Answer 1

首先，定义树的高度（用于 AVL 树）：

height(leaf) = 1
height(node) = 1 + max(height(node.left), height(node.right))

另外，将路径的深度（如用于红黑树的路径是从给定节点到某个叶子的后代链）定义为路径上黑色节点的数量。

正如您所指出的，将 AVL 树着色为红黑树的棘手之处在于确保每条路径具有相同的深度。您将需要使用 AVL 不变量：任何给定节点的子树的高度最多可以相差 1。

直观上，技巧是使用一种着色算法，其深度对于给定高度是可预测的，这样您就不需要进行任何进一步的全局协调。然后，您可以在本地调整着色，以确保每个节点的子节点具有相同的深度；这是可能的，因为 AVL 条件严格限制了它们的高度差。

这个树着色算法可以解决这个问题：

color_black(x):
  x.color = black;
  if x is a node:
    color_children(x.left, x.right)

color_red(x):  // height(x) must be even
  x.color = red
  color_children(x.left, x.right)  // x will always be a node

color_children(a,b):
  if height(a) < height(b) or height(a) is odd:
    color_black(a)
  else:
    color_red(a)
  if height(b) < height(a) or height(b) is odd:
    color_black(b)
  else:
    color_red(b)

对于AVL树的根，调用color_black(root)以确保b。请注意，树是按深度优先顺序遍历的，同时也确保了 a。

请注意，红色节点的高度都是均匀的。叶子的高度为 1，因此它们将被染成黑色，确保 c。红色节点的子节点要么具有奇数高度，要么比其兄弟节点矮，并且将被标记为黑色，以确保 d。

最后，展示e。（从根开始的所有路径都具有相同的深度），使用归纳法n>=1来证明：

• 对于奇数height = 2*n-1,
  • color_black() 创建一棵红黑树，具有深度n
• 对于偶数height = 2*n,
  • color_red() 将所有路径设置为深度n
  • color_black() 创建一棵有深度的红黑树n+1

基本情况，对于n = 1：

• 对于 odd height = 1，树是一片叶子；
  • color_black() 将叶子设置为黑色；唯一路径的深度为 1，
• 对于 Even height = 2，根是一个节点，两个子节点都是叶子，如上标记为黑色；
  • color_red() 将节点设置为红色；两条路径的深度均为 1
  • color_black() 将节点设置为黑色；两条路径的深度均为 2

归纳步骤是我们使用 AVL 不变量的地方：兄弟树的高度最多可以相差 1。对于具有给定 的节点height：

• 子情况 A：两个子树都是(height-1)
• 子情况 B：一个子树是(height-1)，另一个是(height-2)

归纳步骤：假设假设对于 成立n，证明它对于 成立n+1：

对于奇数height = 2*(n+1)-1 = 2*n+1,

• 子情况 A：两个子树的高度相等2*n
  • color_children() 为两个孩子调用 color_red()，
  • 通过归纳假设，两个孩子都有深度n
  • 对于父级， color_black() 添加一个黑色节点，用于深度n+1
• 子情况 B：子树具有高度2*n和2*n-1
  • color_children() 分别调用 color_red() 和 color_black()；
  • 对于均匀高度2*n， color_red() 产生深度n（归纳 hyp。）
  • 对于奇数 height 2*n-1， color_black() 产生深度n（归纳 hyp。）
  • 对于父级， color_black() 添加一个黑色节点，用于深度n+1

对于甚至height = 2*(n+1) = 2*n + 2

• 子情况 A：两个子树的高度均为奇数2*n+1 = 2*(n+1)-1
  • color_children() 为两个子级调用 color_black() 以获取深度n+1
  • 从上面奇数高度的情况来看，两个孩子都有深度n+1
  • 对于父级， color_red() 添加一个红色节点，以保持深度不变n+1
  • 对于父级， color_black() 添加一个黑色节点，用于深度n+2
• 子情况 B：子树具有高度2*n+1 = 2*(n+1)-1和2*n
  • color_children() 为两个子级调用 color_black() 以获取深度n+1
  • 对于奇数高度2*n+1， color_black() 产生深度n+1（见上文）
  • 对于均匀高度2*n， color_black() 产生深度n+1（归纳 hyp。）
  • 对于父级， color_red() 添加一个红色节点，用于深度n+1
  • 对于父级， color_black() 添加一个黑色节点，用于深度n+2 = (n+1)+1