将 AVL 树转换为红黑树

Question

我在某处读到过这样的说法，任何 AVL 树 T 的节点都可以着色为“红色”和“黑色”，以便 T 成为 red-black 树。

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

根据wiki，红黑树应该满足这五个属性：

a.A 节点为红色或黑色。

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

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

d.If一个节点是红色的，那么它的两个children都是黑色的。

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

四个条件很简单，我卡住了如何证明语句5

Answer 1

好吧，#5 的简单情况是单个后代，它是一片叶子，被#3 染黑。

否则后代节点为红色，#4要求有2个黑色后代。

然后这两种情况递归地应用于每个节点，所以你在每条路径中总是有相同数量的黑色节点。

Answer 2

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

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

此外，定义路径的深度（用于red-black树，路径是链从给定节点到某个叶子的后代）是路径上黑色节点的数量。

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

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

这个 tree-coloring 算法可以解决问题：

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。注意树是按depth-first顺序遍历的，同时保证a.

注意红色节点的高度都是偶数。叶子的高度为 1，因此它们将被染成黑色，确保 c。 Children 个红色节点要么具有奇数高度，要么比它们的兄弟节点短，并且将被标记为黑色，确保 d.

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

为奇数 height = 2*n-1,
- color_black() 创建一个 red-black 树，深度为 n
偶数 height = 2*n,
- color_red() 将所有路径设置为深度 n
- color_black() 创建一个深度为 n+1

基本情况，n = 1：

对于奇数height = 1，树是叶子；
- color_black() 将叶子设置为黑色；唯一路径的深度为 1，
对于偶数height = 2，根是一个节点，children都是叶子，如上标黑；
- 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() 为 children、
- 通过归纳假设，children都具有深度n
- for parent, color_black() 添加黑色节点，深度为n+1
子情况 B：子树的高度为 2*n 和 2*n-1
- color_children() 调用 color_red() 和 color_black()，相应地；
- 对于偶数高度 2*n，color_red() 产生深度 n（归纳法）
- 对于奇数高度 2*n-1，color_black() 产生深度 n（归纳法）
- for parent, color_black() 添加黑色节点，深度为n+1

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

子情况A：两个子树的高度都是奇数2*n+1 = 2*(n+1)-1
- color_children() 为两个 children 调用 color_black()，深度为 n+1
- 从上面奇数高度的情况来看，两个children都有深度n+1
- for parent, color_red() 添加一个红色节点，深度不变n+1
- for parent, color_black() 添加黑色节点，深度为n+2
子情况 B：子树的高度为 2*n+1 = 2*(n+1)-1 和 2*n
- color_children() 为两个 children 调用 color_black()，深度为 n+1
- 对于奇数高度 2*n+1，color_black() 产生深度 n+1（见上文）
- 对于偶数高度 2*n，color_black() 产生深度 n+1（归纳法）
- for parent, color_red() 添加一个红色节点，深度为n+1
- for parent, color_black() 添加黑色节点，深度为n+2 = (n+1)+1

Answer 3

即使能把AVL树转成红黑树，代价也很大。树的形状与内部结构无关，需要彻底重建。

红黑树局部最大高差界为2

将 AVL 树转换为红黑树

Convert AVL Trees to Red Black tree

algorithm

data-structures

tree

avl-tree

red-black-tree