连接红黑树

从你的问题的措辞来看,我不确定你是否对集合并集或连接或两者都感兴趣,或者你是否只对OCaml中常见的持久数据结构感兴趣,或者对临时结构感兴趣。

red-black trees with fingers is described by Heather D. Booth in a chapter from her thesis . 用手指,大小为n的红黑树可以在O(lg(min(p,q)))时间内分成大小为p和q的两棵树,大小为p和q的两棵红黑树可以在同一个界限内连接起来。此外,可以在rb树的任意一端添加或删除元素,时间为0(1)。通过这些操作,可以实现摊销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&帕特森对此说法表示怀疑。这些树并不能直接回答你的问题,这是红黑树特有的,但它们希望能给人一种可能的味道,以及H&P文件包括代码和 has been verified correct using Coq

另外两个你可能感兴趣的建议: 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.

编辑:

the "join" implementation for AVL sets in OCaml's stdlib 获取O(h1-h2)性能,其中h1是较高的树的高度,尽管它实际连接两个AVL树,但给定一个适合它们的元素,而下面的算法必须从它的一个参数中找到并删除该mortar元素。您可以通过只在叶子上存储元素来避免这种情况,就像在B+树中一样,但是这样会有一个空间代价,即必须保留一堆指向非叶子节点中元素的指针来指导搜索。在任何情况下,它都不会像OCaml stdlib中的AVL join代码那样使相同高度的树的join时间保持不变,因为您仍然需要计算每个树的黑色高度,如下所述。

给定两个非空的红黑树L和R,我们将产生一个新的红黑树,它是L和R的串联。这将需要与O(lg)成比例的时间

首先,从L,c中去掉最大的元素。下一步,找出L和R的黑色高度。我所说的“黑色高度”是指从 w、 l.o.g.p.公司≤ 问。

从R的根开始,跟随左边的子节点,直到到达高度为p的黑色节点R′。用根元素C、左子元素L和右子元素L创建一个新的红色树C 是p。

新的连接树。

第二,如果R'不是根,它可能有一个红色的父级。红色的父母不允许生红色的孩子,所以我们必须重新平衡。这里我们只应用冈崎的再平衡 从脊柱一直到R'(现在用C代替)和R的根部。

如果C有一个祖父母,它一定是黑色的,并且是黑色的高度p+1,因为C的父母是红色的。用一棵新的红树代替C的祖父母,红树的根是C的父母的根 那个命令。这并不会增加C的祖父母的黑色身高,但它会将颜色变为红色,这可能会使它成为红色的根或红色的孩子 家长,所以我们必须重新平衡,一直到树上

• 求两棵树的黑色高度:O(lg | L |)+O(lg | R |)
• 追踪R到右点:O(lg | R |-lg | L |)

这些都不大于O(lg | R |+lg | L |)=O(lg(max(| L |,| R |)))

要使这个O(lg(min(| L |,| R |)),首先反转脊椎指针。然后你不需要更大的树的黑色高度,你只需要数黑色的脊椎节点,直到一棵树的脊椎用完为止。然后,使用原始的(不是Okasaki的)重新平衡方案来确保只重新平衡O(1)个节点。最后,标记脊椎的其余部分,如果以后需要的话,这些部分不需要重新平衡。

既然您似乎在谈论连接+添加到末尾,那么您似乎有以下问题:

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

这称为对树的连接操作,在这种情况下,可以在O(logn)时间内对树进行连接,请检查: 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。

在每个节点中用高度信息连接和不扩充树时,可以比O(log^2(n))做得更好。 您可以在2*[log(n1)+log(n2)]中连接,其中n1和n2表示要连接的树中的节点数。在以O(log(n))为单位计算高度之后,在向下遍历树时使用每个节点中的平衡信息来找到正确的连接点!

当您将树与低重叠相结合时,您可能会赢得一些东西,但一般来说,您必须重新调整节点。使用平衡时,情况会更糟,因为可能存在只接触一个节点后旋转的规则。