每个有效的红黑树都可以存在吗？
假设您有一个红黑树,它是一个有效的二叉搜索树,并且不违反任何这些规则:
- 节点为红色或黑色.
- 根是黑色的.
- 所有叶子(NIL)都是黑色的.
- 每个红色节点的两个孩子都是黑色的.
- 从给定节点到其任何后代叶子的每个简单路径都包含相同数量的黑色节点.
这样的红黑树看起来像这样:
是否每个可能满足这些限制的树都有一系列插入和删除,以便生成红黑树？
我问这个问题,因为我想写一篇关于红黑树的博客文章,我想举几个例子.
如果你想测试一个反例:这是python中的一个红黑树实现,带有一个实现的函数来生成图像.
澄清问题:我们制作游戏.
- 我画了一棵红黑树,满足了所有的限制.
- 您必须找到一系列插入和删除,以便最终得到我的红黑树.
我可以画一棵红黑树让你无法获胜吗？
颜色很重要!如果树具有不同的形状或不同的颜色,则它不是相同的红黑树.
你应该至少知道如何生成这两个红黑树:
请注意,这只是一个检查,如果它可以工作.如果你只知道如何获得这两棵红黑树,你就无法回答这个问题!
我相信在广度优先(水平顺序)遍历中插入节点将产生任何红黑树.
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都是红色),这就解决了是否需要删除的问题,如果有解决方案则需要删除.我现在的问题是,是否只有一种方法可以实现红黑树的插入/删除.如果存在多个树,并且如果它们产生不同的树,则游戏的玩家必须理解该实现,以便指定插入和删除的顺序以构造给定的红黑树.我不太了解红黑树的实施来回答是否只有一种方法来实施它们或者是否存在多种方法.
- 哦,我每当看到一个明显正确的答案时,我会感到一种令人不寒而栗的感觉.+1先生. (2认同)
- “因此，红黑插入的完全有效实现可以检测到树何时“完美”并将每个节点着色为黑色。”：不，它无法检测到。如果你想检测这棵树是否完美，你必须遍历这三个。那不在`O(log n)`中。所以你的插入和删除不会在`O(log n)`中，这是红黑树最重要的特征。获得正确的形状是显而易见的，但获得正确的颜色并不那么明显。如果您想获得所有可能的 RB 树与三个节点，则必须使用删除 (2认同)
- 我添加了两个红黑树的例子.无论您如何实现插入,如果按照建议的顺序插入节点,则只能通过使用插入来获取两个红黑树. (2认同)
我认为处理此类问题的数学分支是图论，并且研究了一些验证红黑树和其他平衡树的属性的图论论文，我得到了这篇论文：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，他们应该能够回答您对抽象属性的疑问。或者至少可以帮助您以一种可以带来更好资源的方式表达您的问题。