3

我正在寻找所有 AVL 树都可以像红黑树一样着色的证据？任何人都可以提供证据吗？

4

4 回答 4

1

根据定义，R/B 树的平衡可能比 AVL-s 稍差，如 |maxPath - minPath| 对于 AVL 必须 <= 1 并且 maxPath <= 2 * minPath 对于 R/Bs 以便不是每个 R/B 都是 AVL，但另一方面，AVL-s 不需要有空子树，所以

     4
    / \
   3   6
  /\   /\
 1  E 5  8

是完全合法的 AVL，它不是 R/B，因为 R/B 不能包含叶子，并且必须由始终为黑色的空树终止 - 这样您就无法为上面的树着色。要使其成为 R/B，您可以将每个叶子 x 转换为节点 E x E，然后遵循以下规则： R/B 树：必须是 BST 必须仅包含节点和空树，其颜色为黑色或红色 每个红色节点有黑色子节点所有空树都是黑色给定一个节点，到空树的所有路径必须具有相同数量的黑色节点任何叶子都可以替换为左右子树为空的节点最大路径 T ≤ 2 * 最小路径 T

顺便说一句，它刚刚意识到它把我的节点和叶子染成红色——这不是故意的。卡罗尔

于 2011-03-24T13:05:39.647 回答
0

红黑树通过红色节点调整分支高度，因此如果高度差有界，则始终可以调整所有分支，从最短的黑色分支开始。但这需要非常大的成本，因为你必须计算所有的分支高度。

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

于 2021-10-23T22:49:38.557 回答
-2

答案是肯定的，每棵 AVL 树都可以着色为红黑，反之则不成立。

我还没有完全弄清楚如何做到这一点，并且也在寻找证据。

于 2009-04-15T18:19:58.620 回答
-2

I suspect the answer is no.

AVL trees balance better than RB trees, which means they balance differently, which would rather imply that you could not colour every AVL tree as a valid RB tree.

于 2009-03-24T21:19:29.790 回答