每个有效的红黑树都可以存在吗？

Question

假设你有一个red-black tree，是一个有效binary search tree和不违反任何这些规则：

• 节点是红色或黑色。
• 根部是黑色的。
• 所有叶子（NIL）都是黑色的。
• 每个红色节点的两个孩子都是黑色的。
• 从给定节点到其任何后代树叶的每条简单路径都包含相同数量的黑色节点。

这样的红黑树是这个样子：

是否符合这些限制每一个可能的树有插入和缺失的序列，从而产生红黑树？

_{我在问这个问题，因为我想写关于红黑树的博客文章，我想举一些例子。}

如果你想测试一个反例： 这里是a red-black tree implementation in python与一个实现的功能来生成图像。

为了澄清问题：我们做一个游戏。

• 我绘制一棵红黑树，符合所有限制条件。
• 你必须找到一个插入和删除的序列，以便你最终得到我的红黑树。

我可以得出一个红黑树，让你不能赢？

颜色很重要！如果树具有不同的形状或不同的颜色，它不是相同的红黑树。

你至少应该知道如何产生这两个红黑树：

注意，这是只为你检查它是否能正常工作。如果你只知道如何获得这两棵红黑树，你不能回答这个问题！

Answer 1

我认为数学的，与这种类型的问题的分支是图论，并寻找到一些图论的论文是验证的红黑色等平衡树电学性能的研究，我导致了本文：http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf和http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf和本文http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1161&rep=rep1&type=pdf，他们应该能够回答您对抽象属性的查询。或者至少可以帮助你以一种导致更好的资源的方式来描述你的问题。

Answer 2

如果一棵树遵循下列规则：

• 节点是红色或黑色。
• 根部是黑色的。
• 所有叶子（NIL）都是黑色的。
• 每个红色节点的两个孩子都是黑色的。
• 从给定节点到其任何后代树叶的每条简单路径都包含相同数量的黑色节点。

这将是一个平衡的二叉树，可以称为红黑树。

红黑树的插入和删除有特殊的条件和规则。如果您的示例中的树遵循RB树插入和删除的算法，它将始终是RB树。 插入和删除期间，通过更改节点颜色，旋转节点或分支，不平衡二叉树将始终恢复为平衡树。

Answer 3

我想你在这里要求的是一个正式的证明，是否可以通过一系列的插入和删除来构造任意合法的红黑树，前提是树在每次操作后重新平衡。我不打算尝试这样的证明，但我想我有一个想法，可以如何构建这样的证明。

我会详尽地涵盖所有可能的子树，涉及单个节点周围的所有法律排列，并证明它可以构建。所以：

• 黑色节点
  • 没有父
    • 左子空
      • 右子空
      • 右孩子不为空
    • 左孩子不为空
      • 右子空
      • 右孩子不为空
  • 是左子
    • 同上
  • 的右子
    • 同上
• 红色节点（不能没有父）
  • 是左子
    • 同上
  • 被右子
    • 同上

然后你必须创建一个归纳步骤，显示任何任意树是上面所示情况的变换。当我这么说的时候，它看起来非常直截了当，但就像我在评论中提到的那样，我太生疏了，无法处理实际的证据。

Answer 4

我相信在广度优先（水平顺序）遍历中插入节点会产生任何红黑树。

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

因为你的水平以便你不能有一棵树比原树少平衡插入。不需要删除，插入时不需要旋转。在您的例子中，你应该把它们插入按以下顺序：

13,8,17,1,11,15,25,6,22,27 

编辑：虽然这将生成具有正确的价值观二叉搜索树和形状，这可能不会产生正确的颜色...这取决于实施的插入功能。原因是红黑树的定义允许当树有多个节点并且树已满并且所有树叶都处于相同深度时节点颜色的变化 - 根据维基百科的定义，这是一个“完美的”二叉树：

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

假设树具有带有值三个节点{1,2,3}其中“2”是根目录并且，根据定义，黑色。在不违反红黑规则的情况下，节点{1,3}既可以是黑色的也可以是红色的。因此，一个完全有效的红黑插入实现可以检测树何时是“完美”的，并且每个节点都是黑色的。这样的实施将防止能够构建例如在每个级别交替黑色和红色的树。

编辑2：鉴于两个红黑树都是可能的输入（所有三个节点都是黑色的，而节点1和3是红色的），这就解决了是否需要删除的问题，如果有解决方案，那么删除是必要的。现在我脑海中的问题是，是否只有一种方法来实施红黑树插入/删除。如果有多个树，并且它们产生不同的树，那么游戏的玩家必须理解实现，以便指定插入和删除的顺序来构建给定的红黑树。我对红黑树的实施知之甚少，无法回答是否只有一种方法来实施它们，或者是否有不止一种。