Jon*_*rop 19 algorithm red-black-tree data-structures
OCaml标准库有一个很棒的Set实现,它使用非常有效的分而治之算法来计算union两组.我相信它从一个集合中获取整个子树(不仅仅是单个元素)并将它们插入到另一个集合中,在必要时进行重新平衡.
我想知道这是否需要OCaml使用的AVL树中保存的高度信息,或者是否也可以使用红黑树.例如,是否可以更有效地连接一对红黑树,而不是简单地迭代第二棵树,将其元素附加到第一棵树的末尾？
jba*_*ple 42
我不确定你的问题的措辞,如果你对集合联合或连接或两者都感兴趣,或者你只对OCaml中常见的持久性数据结构感兴趣,或者对短暂结构感兴趣.
Heather D. Booth在她的论文的一章中描述了用手指实现红黑树.用手指,一个大小为n的红黑树可以分成两个大小为p和q的树,分摊的O(lg(min(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描述的treaps以随机意义实现了界限,而Kaplan和Tarjan描述的那些在最坏的情况下实现了它们.后者也提供O(lg lg(min(p,q)))串联,尽管Hinze和Paterson对这种说法持怀疑态度.这些树不是你的问题的直接答案,这是特定于红黑树的问题,但他们希望能够提供可能的风格,H&P论文包括代码,并且已经使用Coq进行了验证,Coq可以提取到OCaml代码.
您可能感兴趣的另外两个指点:Brodal等.使用O(lg n)查找,插入和删除以及O(1)concat呈现搜索树,即使在功能设置中也是如此.此外,Atallah等.声称描述了一个红色的黑树,它已经摊销了O(1)concat(大概只是短暂的),但是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连接代码那样使高度相同的树的连接保持时间,因为您仍然需要计算每棵树的黑色高度,如下所述.
给定两个非空的红黑树L和R,我们将产生一个新的红黑树,它是L和R的串联.这将花费时间与O成比例(lg(max | | L |,| R | ))),其中| L | 表示L中的节点数.
首先,从L,c中删除最大的元素.接下来,找到L和R的黑色高度."黑色高度"是指从根到叶子的任何路径上的黑色节点数.通过红黑树不变量,这在任何给定树的所有路径上都是恒定的.调用L's黑色高度p和R的黑色高度q,并假设wlogp≤q.
从R的根部开始,跟随左边的孩子,直到到达高度为p的黑色节点R'.使用根元素c,左子L和右子R'创建一个新的红色树C. 由于L本身是红黑树,其根是黑色的,并且在C或C以下不违反颜色不变量.此外,C的黑色高度为p.
但是,我们不能简单地将C拼接回R代替R'.首先,如果p = q,则R'为R,但C具有红色根.在这种情况下,只需重新着色C black的根.这是你的新连锁树.
其次,如果R'不是根,它可能有一个红色的父.红色父母不允许有红孩子,所以我们必须重新平衡.在这里,我们只是在R'(现在用C代替)和R的根之间的脊柱上应用Okasaki的再平衡方案.
有两种可能的情况.如果C没有祖父母,则颜色C为父母黑色.树现在有效.
如果C有祖父母,它必须是黑色和黑色高度p + 1,因为C的父母是红色的.用一棵新的红树取代C的祖父母,其中的根是C的父母的根,其左边的孩子是C,重新着黑,而右边的孩子是由C的兄弟,C的祖父母的根组成的黑树.和C的叔叔,按此顺序.这不会增加C的祖父母的黑色高度,但它会将其颜色更改为红色,这可能使其成为红色父母的根或红色子项,因此我们必须再次重新平衡,等等一直向上树
这些都不大于O(lg | R | + lg | L |)= O(lg(max(| L |,| R |)))
要使这个O(lg(min(| L |,| R |))),首先反转脊椎指针.然后你不需要较大树的黑色高度,你只需要计算黑色脊椎节点,直到一棵树用完脊椎.然后,使用原始(非Okasaki)重新平衡方案,以确保您只重新平衡O(1)节点.最后,如果有必要,稍后标记不需要重新平衡以进行延迟重新着色的脊椎的其余部分.