logo标签列表

AVL树是否总是红黑树的子集？

data-structuresavl-treered-black-tree
3
我在寻找一个证明，即所有AVL树都可以像红黑树一样被着色的证据。谁能提供这个证明？
我不理解这个问题。 - yfeldblum
虽然我们愿意提供帮助，但我们不会替你完成作业。所以先尝试一下，如果遇到困难，再回来问一个具体的问题。 - Toon Krijthe
@Justice，他正在寻找证明所有AVL树都可以用两种颜色着色，而不会出现相邻节点颜色相同的情况。 - Toon Krijthe
颜色（节点）=如果is_even（depth（node））则“黑色”否则“红色”...那真的是问题吗？还是他在问AVL树是否可以着色，以使其遵守红黑树的所有属性？ - yfeldblum
@Justice：我认为是后者。 - jpalecek
4个回答
1
按照定义，红黑树可以比AVL树略微不平衡，因为对于AVL树，|maxPath - minPath|必须小于等于1，而对于R/B树，maxPath <= 2 * minPath，因此并非每个R/B树都是AVL树，但另一方面AVL树不需要有空子树。
     4
    / \
   3   6
  /\   /\
 1  E 5  8

这是一个完全合法的 AVL 树，它不是 R/B 树，因为 R/B 树不能包含叶子节点，必须以颜色为黑色的空树结束-因此你无法对树进行着色。

要使其成为 R/B 树，您可以将每个叶子 x 转换为节点 E x E，然后遵循以下规则：

R/B 树： 必须是 BST 只能包含颜色为黑色或红色的节点和空树 每个红色节点都有黑色子节点 所有空树都是黑色的 给定一个节点，所有通往空树的路径必须具有相同数量的黑色节点 任何叶子都可以被替换为左右子树为空的节点 最大路径 T ≤ 2 * 最小路径 T

顺便说一下，我刚意识到我的节点和叶子节点被着成了红色-这不是我的本意。 卡罗尔

当然，你可以将上面的树染成红黑色。将3、4、6染成黑色，将1、5、8染成红色。根节点为黑色。每个方向上的黑色路径计数为2。并且没有父子节点都是红色的情况。所有属性都得到了满足。 - SJHowe
0
红黑树通过红色节点调整分支高度，因此如果高度差有限，则始终可以从最短的黑色分支开始调整所有分支。但这需要非常大的代价，因为您必须计算所有分支的高度。
红黑树的最大局部高度差界限为2。
-2

答案是肯定的，每个AVL树都可以被着色为红黑树，但反过来不成立。

我还没有确切地弄清楚如何做到这一点，也在寻求证明。

Hugo - 看看我上面说的话。 - SJHowe
-2

我怀疑答案是否定的。

AVL树比红黑树更好地平衡，这意味着它们的平衡方式不同，这也意味着你不能将每个AVL树都涂成有效的红黑树。

这是不正确的。唯一实质性的区别在于AVL树的平衡更加严格，没有任何一棵树因为太平衡而不能成为红黑树。 - Graphics Noob
有没有可能拥有一棵AVL树，如果你对它进行着色，那么它的状态将无效于红黑树？这是我的担忧。 - user82238
user82238：我认为Graphics Noob是正确的。如果你给AVL树着色，你只需要放置黑色节点，使得黑色路径计数在任何地方都相同，而AVL树的卓越平衡将会帮助你。这样就留下了将奇数个红色节点放置为“填充物”的情况，以防你无法完全使黑色路径计数相同。假设从根到叶子的最短AVL路径为9，偶尔为10。那么将黑色路径计数设置为9，在10条路径上，将叶节点设置为红色。事实上恰恰相反。有些红黑树不能成为AVL树。 - SJHowe
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接