logo标签列表

连接红黑树

algorithmdata-structuresred-black-tree
21

OCaml标准库提供了一个出色的Set实现，使用非常高效的分治算法来计算两个集合的union。 我认为它可以从一个集合中获取整个子树（而不仅仅是单个元素），并将其插入到另一个集合中，在必要时进行重新平衡。

我想知道这是否需要AVL树中保留的高度信息，或者在红黑树中也可以实现。例如，是否可以更有效地连接一对红黑树，而不仅仅是迭代第二个树将其元素附加到第一个树的末尾？

12
有人投票将我的问题标记为“不相关”。自从什么时候RB树在Stack Overflow上成为了不相关的话题？！ - J D
4个回答
46

我不确定你的问题措辞是否涉及集合并或连接，或者两者都涉及，或者你只对OCaml中常见的持久数据结构或非持久结构感兴趣。

在她的论文一章中，Heather D. Booth描述了带指针的红黑树的实现。使用指针，大小为n的红黑树可以被分成大小为p和q的两棵树，其摊销时间为O(lg(min(p,q)))，并且两棵大小为p和q的红黑树可以在相同的限制下连接。此外，元素可以在rb树的任一端点以摊销O(1)时间添加或删除。通过这些操作，可以实现摊销O(p lg(q/p))时间的集合并（对于p < q），这是信息理论上最优的。也许获得这些界限的关键思想是在左右脊柱上翻转子指针。

上述界限在传统意义上是摊销的。对于像OCaml这样的函数语言，人们可能希望在数据结构被持久使用时应用这些界限。当树被持久使用时，我认为Booth的描述无法实现所有这些界限。例如，在指针处插入可能需要ω(1)次重新着色。这可以通过Driscoll等人在“使数据结构持久”中讨论的惰性重新着色来解决。

另一方面，我认为 Booth 的分析可能表明，即使在持久化使用时，串联仍然是 O(lg(max(p,q)))。我对集合并的上界持悲观态度。

在函数式环境中，可以实现具有渐进最优时间复杂度的集合操作。Hinze＆Paterson描述的方法在摊销（但持久化）意义下达到了这些界限，Blandford＆Blelloch描述的treaps在随机意义下达到这些界限，而Kaplan＆Tarjan描述的方法则以最坏情况时间实现这些界限。后者还提供O(lg lg(min(p,q)))的连接操作，尽管Hinze＆Paterson对此表示怀疑。这些树并不直接回答你的问题，这是特定于红黑树的问题，但它们希望给出一个可能性，H&P 论文包括代码，并已经使用Coq进行验证 正确性 , 可以将其提取到OCaml代码。

你可能会对以下两个指针感兴趣：Brodal等人提出了具有O（lg n）查找，插入和删除以及在功能设置中具有O（1）连接的搜索树。此外，Atallah等人声称描述了一种红黑树，其摊销O（1）连接（可能仅是暂时的）,但Buchsbaum和Goodrich声称该结构存在几个缺陷。

关于红黑树实用性的最后一个说明：在回答此问题的评论中，您说：

红黑树唯一的优点是每个分支的辅助信息（红色或黑色）只有1位。通过添加高度，您已经失去了这个优势，最好使用平衡树。

还有其他的优点。例如，计算几何中使用的一些数据结构基于二叉搜索树，但旋转树的代价很高。红黑树可以在插入和删除时重新平衡，最多只需3次旋转, 而AVL树对于这些操作可能需要Ω(lg n)次旋转。正如Ralf Hinze所指出的那样, Okasaki的红黑树重新平衡方案（代码可在ML, Haskell, Java和Ada中获得）没有提供相同的界限，并且在插入时可能需要Ω(lg n)次旋转。（Okasaki没有介绍删除。）

此外，高度平衡的搜索树（甚至是AVL树）可以存储为每个节点仅使用一位平衡信息。有些树在每个节点上只有两个可能的平衡位置，例如单侧高度平衡树，但每个节点最多有四个可能的平衡位置的树可以在每个孩子中存储一位平衡信息，正如Brown最初解释的，后来Haeupler等人进一步扩展了。
在您问题的最后特定查询的答案中，这里是一种合并两个红黑树的算法描述。它需要O(lg(max(|L|,|R|)))的时间，这太长了，无法获得我上面描述的渐进最优联合时间。相比之下，我希望OCaml stdlib中AVL集合的“join”实现能够获得O(h1-h2)的性能，其中h1是更高树的高度，尽管它实际上是将给定一个适合它们之间的元素连接两个AVL树，而下面的算法必须找到并从它的参数中删除那个沙浆元素。您可以通过仅在叶子处存储元素来避免这种情况，就像B+树一样，但这会导致空间惩罚，必须保留非叶节点中指向元素的一堆指针以指导搜索。在任何情况下，与OCaml stdlib中AVL join代码一样，它不会使具有相同高度的树的联接成为恒定时间，因为您仍然必须计算每个树的黑高度，如下所述。

给定两个非空红黑树L和R，我们将生成一个新的红黑树，该树是L和R的连接。这将花费的时间与O(lg(max(|L|,|R|)))成正比，其中| L |表示L中节点的数量。

首先，从L中删除最大的元素c。接下来，找到L和R的黑色高度。所谓“黑色高度”，是指从根节点到叶子节点的任意路径上的黑色节点数目。根据红黑树的不变式，这在给定树的所有路径上都保持不变。将L的黑色高度称为p，R的黑色高度称为q，并假设w.l.o.g. p ≤ q。

从R的根节点开始，沿着左孩子一直走，直到到达一个高度为p的黑色节点R'。用c作为根元素、L作为左孩子、R'作为右孩子构建一个新的红色树C。由于L本身就是红黑树，其根节点是黑色的，因此在或以下的C中不会违反颜色不变式。此外，C的黑色高度为p。

然而，我们不能简单地将C插入到R中替换R'。首先，如果p=q，则R'就是R，但C具有红色根。在这种情况下，只需将C的根重新涂成黑色即可。这就是您的新连接树。

其次，如果R'不是根节点，则它可能有一个红色父节点。不允许红色父节点有红色子节点，因此我们必须重新平衡。在R'（现在用C替换）和R的根节点之间的脊柱上应用Okasaki的重新平衡方案。

有两种可能的情况。如果C没有祖父节点，则将C的父节点涂成黑色。树现在是有效的。

如果C有祖父，则其必须为黑色且黑高度为p+1，因为C的父节点为红色。用一个新的红树替换C的祖父，其根为C的父节点的根，左孩子为被重新染成黑色的C，右孩子为由C的兄弟、C的祖先的根和C的叔叔组成的黑树，按照上述顺序。这不会增加C的祖父的黑高度，但它将其颜色更改为红色，这可能使其成为根或红色父节点的红色子节点，因此我们必须再次重新平衡，以此类推，一直到整棵树的根部。
找到两棵树的黑高度：O(lg |L|) + O(lg |R|) 追踪R到正确位置：O(lg |R| - lg |L|) 旋转回到根部：O(lg |R| - lg |L|) 以上所有操作的时间复杂度均不大于O(lg |R| + lg |L|) = O(lg (max(|L|,|R|)))
为了将其变为O(lg (min(|L|,|R|)))，首先要反转脊柱指针。然后您不需要更大树的黑高度，只需计算黑色脊柱节点数，直到一棵树的脊柱用完为止。然后，使用原始（非Okasaki）重新平衡方案，以确保您只重新平衡O(1)个节点。最后，如果需要，将不需要重新平衡的脊柱的剩余部分标记为懒惰颜色化。
1
点赞已经解决了你的Karma问题。有没有可能回来编辑一下呢？这似乎是一个潜在的好答案，可以通过可点击的链接显著改进。 - clstrfsck
2
@spong：是的，我现在就去做。谢谢你提醒我。 - jbapple
4
看起来他们只是通过在每个节点中添加高度信息来增强树，使其不再是普通的红黑树，从而将其复杂度控制在O(log n)。 - J D
1
@Jon。即使有这些信息，我们仍然可以将其视为红黑树。这并不改变插入/删除等操作仍然是O(logn)的事实，而节点颜色遵循rb树的不变量。无论如何，我不知道还有什么其他方式 :-) - Aryabhatta
@Moron：红黑树唯一的优点是辅助信息（红色或黑色）每个分支只有1位。通过添加高度，您已经失去了这个优势，最好使用平衡树代替。 - J D
1
@Jon：如果Tarjan和Sleator认为这很重要并发表了一篇论文，我不能轻易地将其驳回 :-）。无论如何，如果不维护高度信息，你仍然可以在O(log^2(n))的时间内完成它，这仍然比线性时间更快。 - Aryabhatta
1
@Jon：我没有深入研究算法的细节，但每当你需要高度时，只需在O(logn)时间内重新计算即可。最坏情况下，这将使算法变为O(log^2(n))。 - Aryabhatta
显示剩余2条评论
1
可以在不用在每个节点中添加高度信息的情况下，比O(log^2(n))更好地进行连接。您可以在2*[log(n1)+log(n2)]中连接，其中n1和n2表示您要连接的树中的节点数。在用O(log(n))计算出高度后，在从树上往下走时使用每个节点中的平衡信息来找到正确的连接点！
0
当你将树与低重叠组合时，可能会获得一些好处，但通常需要重新组织节点。通过平衡，情况会更糟，因为可能存在仅触及一个节点后旋转的规则。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接