3

如果我有一棵二叉树，并且想将黑色/红色属性添加到它的所有节点以形成一棵红黑树，如果我们知道二叉树是平衡的，有没有办法做到这一点？

4

2 回答 2

1

可能对红黑树最严格的条件是任何根空路径必须具有相同数量的黑色节点。因此，一种选择是首先从根运行 DFS 以确定最短根空路径的长度。该路径长度给出了树的“黑色高度”的上限，即任何根空路径上的黑色节点数。

一旦我们有了这个值，我们就可以尝试将黑色高度分配给节点，让我们确定哪些节点是红色或黑色。一个有用的观察结果如下：节点的任何子树的黑色高度必须相同，否则会有两个具有不同黑色高度的 root-NULL 路径。因此，对于每个节点，如果其当前的黑色高度为 h 并且所需的黑色高度为 H，我们可以

  • 将其着色为红色，在这种情况下，我们递归地为左右子树着色，使它们具有黑色高度 H。我们还强制下面这些子树的根为黑色。
  • 将其着色为黑色，在这种情况下，我们递归地为左右子树着色，使它们的黑色高度为 H - 1。这些树根部的节点可以是任何一种颜色。

我认为你可以通过使用动态编程来做到这一点。假设所需的目标黑色高度是 H，我们可以创建一个按节点/黑色深度/颜色三元组索引的表（这里，黑色高度是根在该节点的子树的黑色高度）存储是否可以着色以正确的方式结点。我们称它为 T[v, h, c]。我们可以这样填写：

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

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

希望这可以帮助！

于 2013-10-19T00:46:58.563 回答
0

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

由于使用红黑标记来防止出现不平衡的树，因此当然不可能为每棵搜索树着色 - 如果是这样，那么它什么也没做！一个反例是这棵树：

1
 \
  2
   \
    3

所有剩下的孩子都是空的。

于 2013-10-19T15:21:57.550 回答