连接红黑树

Question

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

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

Answer 1

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

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

这称为树上的连接操作，在这种情况下，可以在O(log )时间内完成树的连接，请查看：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 2

在每个节点中连接和不增加树的高度信息时，可以比O(log^2(n))做得更好。您可以在2* log( n1 ) + log( n2 )中进行连接，其中n1和n2表示要连接的树中的节点数。在计算了O(log(n))中的高度之后，在向下搜索树时使用每个节点中的平衡信息来找到正确的连接点！

Answer 3

当你将低重叠的树组合在一起时，你可能会赢得一些东西，但通常你必须重新组织节点。使用平衡时，你会遇到更糟糕的情况，因为可能只有一个节点接触后才会有旋转规则。