logo标签列表

如何判断二叉树是否为红黑平衡树？

binary-tree
5

在以前的一次考试中，我们曾被要求通过观察树的形状来判断它是否是红黑平衡的。 我没有找到任何关于如何完成这个任务的信息，除了一个网站声称，如果最长路径不超过最短路径的两倍，则二叉树就是红黑平衡的，但我非常确定这也是空路径平衡树的要求。 那是否正确？ 有没有办法通过形状判断一棵树是否是红黑平衡的？

3个回答
1
1

我不是专家，但这是来自Cormen的书《算法导论》:

红黑树是一种满足以下红黑性质的二叉树:

  1. 每个节点要么是红色的，要么是黑色的。
  2. 根节点是黑色的。
  3. 每个叶子节点（NIL）都是黑色的。
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
  5. 对于每个节点，从该节点到后代叶子节点的所有简单路径都包含相同数量的黑色节点。
1
不要混淆概念。可能教授想让学生们意识到红黑树是什么样子的。
从维基百科来看，除了二叉搜索树所需满足的条件外，红黑树还必须满足以下条件：
1.节点为红色或黑色。 2.根节点为黑色。 3.所有叶子（NIL）都是黑色。（所有叶子与根节点颜色相同。） 4.每个红色节点必须有两个黑色子节点（因此它必须有一个黑色父节点）。 5.从给定节点到任何后代 NIL 节点的每条路径都包含相同数量的黑色节点。
这些约束强制实现了红黑树的一个关键特性：从根到最远叶子的路径长度不超过从根到最近叶子的路径长度的两倍。结果，树大致保持高度平衡。由于插入、删除和查找值等操作需要最坏情况下与树的高度成比例的时间，因此这种理论上界允许红黑树在最坏情况下高效，而普通的二叉搜索树则不行。

源代码

接下来是这个问题：将二叉树染成红黑树的颜色

还有这个问题：如何检查节点的黑高度，以及其到后代叶子的所有路径？，其中您可以找到一个解决方案。

以这棵树为例： enter image description here

如果测试中有一棵有颜色的树，则可以断言从维基百科中给出的属性。如果树没有颜色，我认为这将是情况，则将我上面链接的树写在纸上，并运行链接问题中提供的算法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接