连接红黑树

Question

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

我想知道这是否需要保存在OCaml使用的AVL树中的高度信息，或者红黑树也可以这样做。例如，是否可以更有效地连接一对红黑树，而不是简单地迭代第二棵树，将其元素附加到第一棵树的末尾？

Answer 1

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

执行red-black trees with fingers is described by Heather D. Booth in a chapter from her thesis。用手指，一棵大小为n的红黑树可以分成两棵大小为p和q的树，按摊还O（lg（min（p，q）））的时间，两棵尺寸为p和q的红黑树可以是连接在同一个绑定中。此外，可以在分摊的O（1）时间内在rb树的任一端添加或删除元素。通过这些操作，可以实现平摊的O（p lg（q/p））时间设置联合（对于p < q），这是信息理论上最优的。也许获得这些界限的关键想法是逆转左侧和右侧脊柱上的子指针。

上述界限按传统意义摊销。对于像OCaml这样的函数式语言，人们可能希望在持久使用数据结构时应用边界。当这些树被持续使用时，我认为布斯的描述不会达到所有这些界限。例如，插入手指可以采用ω（1）重新着色。这可以通过lazy recolorings discussed in Driscoll et al.'s "Making Data Structures Persistent"来解决。另一方面，我认为Booth的分析可能表明即使在持续使用时级联仍然是O（lg（max（p，q）））。我对工会的界限不那么乐观。

在功能设置中可以设置具有渐近最优时间范围的运算。那些described by Hinze & Paterson达到分期付款（但持续）意义上的界限，treaps described by Blandford & Blelloch achieve the bounds in a randomized sense和那些described by Kaplan & Tarjan在最差情况下实现它们。后者也提供O（lg lg（min（p，q）））级联，但Hinze & Paterson对这种说法持怀疑态度。这些树不是你的问题的直接答案，这是针对红黑树的问题，但他们希望给出一种可能的风味，并且包括代码和has been verified correct using Coq，它们可以提取到OCaml代码。

您可能感兴趣的另外两个指针：Brodal et al. presented search trees with O(lg n) find, insert, and delete and O(1) concat even in a functional setting。此外，Atallah et al. claim to describe a red-black tree that has amortized O(1) concat (presumably ephemerally only)，但是Buchsbaum and Goodrich claim that there are several flaws in that structure。

一个关于红黑树的效用最后要注意的：在对这个问题的答案的一个一个评论，你说：

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

还有其他的优点。例如，计算几何中使用的一些数据结构是基于二叉搜索树的，但树的旋转成本很高。 Red-black trees can be rebalanced in at most 3 rotations per insert and delete，而AVL trees can take Ω(lg n) rotations for these operations。 As Ralf Hinze noticed,Okasaki's rebalancing scheme for red-black trees（代码可用于ML,Haskell,Java, and Ada）不提供相同的界限，并且最终可能在插入时做Ω（lg n）旋转。 （冈崎不存在删除）

此外，可以存储高度平衡的搜索树（甚至AVL树），以便每个节点仅使用一位余额信息。有些树木在每个节点上只有两个可能的平衡位置，如单侧高度平衡树木，但每个节点最多有四个可能的平衡位置的树木可以在每个孩子中存储一位平衡信息，如initially explained by Brown和更高版本expanded upon by Haeupler et al.

编辑：

在回答你的你的问题的最后具体的查询，这里是一个算法用于连接两个红黑树的描述。它需要O（lg（max（| L |，| R |）））时间，这对于我上面描述的渐近最优联合时间来说太长了。为了比较，我期望the "join" implementation for AVL sets in OCaml's stdlib获得O（h1-h2）性能，其中h1是较高树的高度，尽管它实际上连接两个AVL树，只要给出一个适合它们的元素，而下面的算法必须找到并删除来自其论据之一的迫击炮元素。您可以通过仅将元素存储在树叶中来避免这种情况，就像在B +树中一样，但是这样做会造成空间惩罚，必须在非叶节点中保留一堆指向元素的指针以指导搜索。在任何情况下，它都不会像OCaml stdlib中的AVL连接代码那样为树高度相同的树创建连接时间，因为您仍然必须计算每棵树的黑色高度，如下所述。给定两个非空红黑树L和R，我们将产生一个新的红黑树，它是L和R的连接。这将花费与O成正比的时间（lg（L（t）| L |，| R |））），其中| L |表示在L中的节点的数量。

首先，从L，c中除去最大的元素。接下来，找到L和R的黑色高度。“黑色高度”是指从根到叶子的任何路径上的黑色节点数。通过红黑树不变量，这在任何给定树的所有路径上都是不变的。调用L's黑色高度p和R的黑色高度q，并假设为 w.l.g.g q。

从R的根部，跟随左边的孩子，直到到达高度为p的黑色节点R'。用根元素c制作一棵新的红色树C，左边的小孩L和右边的小孩R'。由于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 | （lg（min（| L |，| R |）））），首先反转脊柱指针。然后，您不需要较大树的黑色高度，只需计算黑色脊椎节点，直到一棵树用完脊椎。然后，使用原始（不是冈崎的）重新平衡方案，以确保您只重新平衡O（1）个节点。最后，在稍后有必要的时候标记不需要重新平衡进行懒惰重新着色的脊柱的其余部分。

Answer 2

当你将树与低重叠结合时，你可能会赢得一些东西，但总的来说，你将不得不重新节点。平衡你有更糟糕的情况，因为有可能只有一个节点后触发旋转的规则。

Answer 3

因为你似乎在谈论连击+添加到年底，好像你有以下问题：

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 4

在连接时可以比O（log^2（n））做得更好，而不是在每个节点中增加具有高度信息的树。 您可以在2 * [log（n1）+ log（n2）]中连接，其中n1和n2表示您要连接的树中的节点数。在计算O（log（n））中的高度后，沿着树向下找到正确的连接点时，请在每个节点中使用Balance信息！