algorithm - 连接红黑树

Question

OCaml 标准库有一个很棒的Set实现，它使用一种非常有效的分治算法来计算union两个集合。我相信它从一组中获取整个子树（不仅仅是单个元素）并将它们插入到另一组中，并在必要时重新平衡。

我想知道这是否需要 OCaml 使用的 AVL 树中保存的高度信息，或者这是否也适用于红黑树。例如，与简单地遍历第二棵树并将其元素附加到第一棵树的末尾相比，是否可以更有效地连接一对红黑树？

Answer 1

如果您对集合联合或连接或两者感兴趣，或者您只对 OCaml 中常见的持久数据结构或临时结构感兴趣，我不确定您的问题的措辞。

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

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

另一方面，我认为 Booth 的分析可能表明即使持续使用，连接仍然是 O(lg (max (p,q)))。我对设定的联合约束不太乐观。

在功能设置中，具有渐近最优时间界限的集合操作是可能的。Hinze 和 Paterson 描述的那些在摊销（但持久）的意义上实现了边界，Blandford 和 Blelloch 描述的陷阱在随机意义上实现了边界，而Kaplan 和 Tarjan 描述的那些在最坏情况下实现了它们。后者还提供 O(lg lg (min(p,q))) 连接，尽管 Hinze 和 Paterson 对这种说法持怀疑态度。这些树不是您的问题的直接答案，这是特定于红黑树的问题，但它们希望能提供一种可能的味道，并且 H&P 论文包含代码，并已使用 Coq 验证正确，它可以提取到OCaml 代码。

您可能感兴趣的另外两个指针：Brodal 等人。即使在功能设置中，也提供了具有 O(lg n) 查找、插入和删除以及 O(1) 连接的搜索树。此外，Atallah 等人。声称描述了一个摊销了 O(1) concat 的红黑树（可能只是短暂的），但Buchsbaum 和 Goodrich 声称该结构存在几个缺陷。

关于红黑树效用的最后一点说明：在对这个问题的一个答案的评论之一中，您说：

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

还有其他优点。例如，计算几何中使用的一些数据结构基于二叉搜索树，但树旋转的成本很高。红黑树每次插入和删除最多可以重新平衡 3 次旋转，而AVL 树可以为这些操作进行 Ω(lg n) 次旋转。正如 Ralf Hinze 所注意到的，Okasaki 的红黑树再平衡方案（在ML、Haskell、Java 和 Ada中可用的代码）没有提供相同的界限，并且最终会在插入时进行 Ω(lg n) 旋转。（冈崎不存在删除。）

此外，可以存储高度平衡的搜索树（甚至 AVL 树），以便每个节点仅使用一位平衡信息。有些树在每个节点上只有两个可能的平衡位置，例如单边高度平衡树，但是每个节点最多有四个可能的平衡位置的树可以在每个子节点中存储一位平衡信息，正如Brown和后来所解释的那样Haeupler 等人对其进行了扩展。

编辑：

在回答您问题末尾的特定查询时，这里是对连接两个红黑树的算法的描述。它需要 O(lg(max(|L|,|R|))) 时间，这对于我上面描述的渐近最优联合时间来说太长了。为了比较，我希望在 OCaml 的 stdlib 中设置 AVL 的“加入”实现获得 O(h1-h2) 性能，其中 h1 是较高树的高度，尽管它实际上加入了两个 AVL 树，给定一个适合它们之间的元素，而下面的算法必须从其中一个中找到并删除该砂浆元素论据。您可以通过仅将元素存储在叶子中来避免这种情况，就像在 B+ 树中一样，但这会带来空间损失，即必须在非叶子节点中保留一堆指向元素的指针来指导搜索。无论如何，它不会像 OCaml 标准库中的 AVL 连接代码那样使相同高度的树的连接时间保持不变，因为您仍然需要计算每棵树的黑色高度，如下所述。

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

首先，从 L, c 中删除最大的元素。接下来，找到 L 和 R 的黑色高度。“黑色高度”是指从根到叶的任何路径上的黑色节点数。通过红黑树不变量，这在任何给定树的所有路径上都是恒定的。称 L 的黑色高度 p 和 R 的黑色高度 q，并假设 wlog 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 的根之间一直应用冈崎的再平衡方案。

有两种可能的情况。如果 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) 个节点。最后，标记不需要重新平衡的脊柱其余部分，以便稍后必要时进行延迟重新着色。

Answer 2

由于您似乎在谈论 Concatenate + 添加到末尾，因此您似乎遇到了以下问题：

Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2,
find union of the two.

这称为树上的连接操作，在这种情况下，可以在 O(log n) 时间内完成树的连接，请查看：http ://www.cs.tau.ac.il/~ wein/publications/pdfs/rb_tree.pdf

另请查看： http: //net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm，习题 14.2。

Answer 3

在连接而不是用每个节点中的高度信息扩充树时，可以比 O(log^2(n)) 做得更好。您可以在 2* [log(n1) + log(n2)] 中连接，其中 n1 和 n2 表示要连接的树中的节点数。在计算 O(log(n)) 中的高度后，在沿着树向下查找正确的连接点时使用每个节点中的平衡信息！

Answer 4

You may win something when you'll combine tree with low overlap, but in general you'll have to reorgainze nodes. With balancing you have worse situation as there probably rules for rotating after touching only one node.