red-black-tree - 每棵有效的红黑树都存在吗？

Question

假设你有一棵红黑树，它是一个有效的二叉搜索树并且不违反任何这些规则：

一个节点要么是红色的，要么是黑色的。
根是黑色的。
所有叶子 (NIL) 都是黑色的。
每个红色节点的两个孩子都是黑色的。
从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

这样一棵红黑树看起来像这样：在此处输入图像描述

满足这些限制的每棵可能的树是否都有插入和删除的序列，从而生成红黑树？

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

如果你想测试一个反例：这是一个在 python 中实现的红黑树，其中实现了生成图像的函数。

澄清问题：我们制作游戏。

我画了一棵符合所有限制的红黑树。
你必须找到插入和删除的序列，这样你才能得到我的红黑树。

我可以画一棵红黑树，让你赢不了吗？

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

您至少应该知道如何生成这两个红黑树：在此处输入图像描述

请注意，这只是对您的检查，如果它可以工作。如果你只知道如何得到这两个红黑树，你是无法回答这个问题的！

score 5 · Accepted Answer

我相信以广度优先（级别顺序）遍历插入节点将产生任何红黑树。

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 均为红色），这就解决了是否需要删除的问题，如果有解决方案，则需要删除。我现在想到的问题是是否只有一种方法可以实现红黑树插入/删除。如果有不止一个，并且如果它们产生不同的树，那么游戏玩家将必须了解实现，以便指定插入和删除的顺序来构造给定的红黑树。我对红黑树的实现知之甚少，无法回答是否只有一种实现它们的方法或是否有多种方法的问题。

score 4 · Accepted Answer

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

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

黑节点
- 没有父母
  - 左孩子为空
    - 右孩子 null
    - 右孩子不为空
  - 左孩子不为空
    - 右孩子 null
    - 右孩子不为空
- 是左孩子
  - 和上面一样
- 是正确的孩子
  - 和上面一样
红色节点（不能没有父节点）
- 是左孩子
  - 和上面一样
- 是正确的孩子
  - 和上面一样

然后您必须创建一个归纳步骤，表明任何任意树都是上述情况的排列。当我这样说时，这似乎很简单，但就像我在评论中提到的那样，我太生疏了，无法处理实际的证明。

score 3 · Accepted Answer

我认为处理这类问题的数学分支是图论，并研究了一些验证红黑树和其他平衡树的属性的图论论文，我被引导到这篇论文：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，他们应该能够回答您对抽象属性的查询。或者至少可以帮助您以一种可以带来更好资源的方式来表达您的问题。

score 2 · Accepted Answer

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

一个节点要么是红色的，要么是黑色的。
根是黑色的。
所有叶子 (NIL) 都是黑色的。
每个红色节点的两个孩子都是黑色的。
从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

它将是一棵平衡二叉树，可以称为红黑树。

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

score 0 · Accepted Answer

我不确定答案是否定的，我将在下面说明原因。如果完全可以做到，则有必要插入比需要更多的节点，然后删除其他节点。

您可以删除任意红色叶子节点，树不会改变形状或重新着色。您可以在树底部的黑色父节点下插入任意红色叶子节点，而不会改变树的形状。

如果您需要使树的一侧更茂密，则在该位置插入节点就足够了。这将首先导致树上的重新着色，然后最终重新平衡。

我认为它无法完成的原因是删除具有 2 个子节点的节点，完成的方式是将节点与后继节点或前驱节点交换（任何一个都有效），然后删除它移动到的节点。有继任者或前任者的选择，产生的树会有所不同。因此，您需要控制删除的这一方面并到达某个树，可能需要说“删除节点 A 使用后继”，现在“删除节点 B 使用前任”

score -1 · Accepted Answer

红黑树被分解为灵活的红色缓存和不变的黑色支持。为了保持黑色高度不变，您必须将红色缓存移动到顶部，这样您就可以调整高度。粗略地说，不移动真实节点就可以轻松移动红色容量。红色容量必须不断换出到黑色树顶，从而生成全局红色瀑布。

红色容量向下移动，黑色分支向上移动。

red-black-tree - 每棵有效的红黑树都存在吗？

6 回答 6

Related

Reference