红黑树问题

Question

如果我有一棵二叉树，并且想要添加黑色/红色属性到所有节点上，以形成红黑树，如果我们知道这个二叉树是平衡的，那么是否有方法可以实现这一点？

- user2896632

Answer 1

红黑树上最严格的条件可能是任何一个从根到NULL的路径上，黑色节点的数量都必须相同。因此，一种方法是从根节点开始运行DFS，以确定最短的根-NULL路径的长度。这个路径长度给出了树的“黑高度”的上限，即任何根-NULL路径上的黑色节点数量。

一旦我们有了这个值，就可以尝试以一种方式为节点分配黑高度，以便让我们确定哪些节点是红色或黑色。一个有用的观察是：任何节点的子树的黑高度必须相同，否则将会有两个具有不同黑高度的根-NULL路径。因此，对于每个节点，如果它当前的黑高度为h，期望的黑高度为H，则我们可以选择：

• 将其着为红色，然后递归地着色左右子树，使它们的黑高度为H。我们还需要强制下面的子树根节点为黑色。
• 将其着为黑色，然后递归地着色左右子树，使它们的黑高度为H-1。那些树根节点的颜色可以是任意的。

我认为你可以使用动态规划来完成这个问题。假设所需的目标黑色高度为H，我们可以制作一个表，索引为节点/黑深度/颜色三元组（这里，黑高度是该节点子树的黑高度），存储是否可以以适当的方式对该节点进行着色。让我们称之为T [v，h，c]。我们可以按照以下方式填写它：

• 将NULL视为黑色节点。 T [null，0，red] = false，T [null，0，black] = true。
• 对于每个节点，按照处理其子树l和r的顺序进行处理，执行以下操作：
  • T [v，h，red] = T [l，h，black] and T [r，h，black]
  • 对于任何颜色c，T [v，h，black] = T [l，h-1，c] and T [r，h-1，c]

一旦您评估了此内容，您就可以检查T [root，h，c]是否对于任何高度h或颜色c为true。这应该只需要多项式时间。

希望这可以帮助你！

- templatetypedef

Answer 2

Templatetypedef已经非常好地回答了您问题的主要部分。我只想为您的次要问题添加一个答案。

由于红黑标记用于防止树不平衡，因此肯定不可能对每棵搜索树都进行着色-如果是这样，那么它就没有实现任何目的！一个反例是这棵树：

1
 \
  2
   \
    3

所有左子节点都为空。

- Erik P.