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

Question

假设你有一个 red-black tree这是一个有效的 binary search tree并且不违反任何这些规则:

节点是红色或黑色。

根是黑色的。

所有叶子 (NIL) 都是黑色的。

每个红色节点的两个 child 都是黑色的。

从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

这样一棵红黑树看起来像这样:


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

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

如果你想测试一个反例:
这是 a red-black tree implementation in python具有生成图像的已实现功能。

澄清问题 : 我们做游戏。

我画了一棵满足所有限制的红黑树。

你必须找到一个插入和删除的序列，这样你才能得到我的红黑树。

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

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

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



请注意，这只是检查您是否可行。如果你只知道如何得到这两棵红黑树，你是无法回答这个问题的!

Answer 1

我相信在广度优先(级别顺序)遍历中插入节点将产生任何红黑树。

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