Java 中 TreeSet 操作的计算复杂性？

Computational complexity of TreeSet operations in Java?

提问by Andreas K.

I am trying to clear up some things regarding complexity in some of the operations of TreeSet. On the javadoc it says:

我试图澄清一些关于 TreeSet 某些操作中的复杂性的事情。在javadoc上它说：

"This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains)."

“此实现为基本操作（添加、删除和包含）提供了有保证的 log(n) 时间成本。”

So far so good. My question is what happens on addAll(), removeAll() etc. Here the javadoc for Set says:

到现在为止还挺好。我的问题是在 addAll()、removeAll() 等上会发生什么。这里 Set 的 javadoc 说：

"If the specified collection is also a set, the addAll operation effectively modifies this set so that its value is the union of the two sets."

“如果指定的集合也是一个集合，addAll 操作会有效地修改这个集合，使其值是两个集合的并集。”

Is it just explaining the logical outcome of the operation or is it giving a hint about the complexity? I mean, if the two sets are represented by e.g. red-black trees it would be better to somehow join the trees than to "add" each element of one to the other.

它只是解释了操作的逻辑结果还是暗示了复杂性？我的意思是，如果这两个集合由例如红黑树表示，那么以某种方式连接树会比将一个的每个元素“添加”到另一个更好。

In any case, is there a way to combine two TreeSets into one with O(logn) complexity?

在任何情况下，有没有办法将两个 TreeSet 组合成一个复杂度为 O(logn) 的树集？

Thank you in advance. :-)

先感谢您。:-)

采纳答案by bshields

You could imagine how it would be possible to optimize special cases to O(log n), but the worst case has got to be O(m log n)where mand nare the number of elements in each tree.

你能想象它怎么会是可以优化的特殊情况来O(log n)，但最坏的情况一定是O(m log n)哪里m和n在每个树元素的数量。

Edit:

编辑：

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

Describes a special case algorithm that can join trees in O(log(m + n))but note the restriction: all members of S1must be less than all members of S2. This is what I meant that there are special optimizations for special cases.

描述了一种特殊情况的算法，它可以连接树，O(log(m + n))但要注意限制： 的所有成员S1必须小于 的所有成员S2。这就是我的意思，对特殊情况进行特殊优化。

回答by Karel Petranek

According to this blog post:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
it's O(n log n). Because the documentation gives no hints about the complexity, you might want to write your own algorithm if the performance is critical for you.

根据这篇博客文章：
http: //rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
它是 O(n log n)。由于文档没有给出有关复杂性的提示，如果性能对您至关重要，您可能需要编写自己的算法。

回答by Kiersten Arnold

Looking at the java source for TreeSet, it looks like it if the passed in collection is a SortedSet then it uses a O(n) time algorithm. Otherwise it calls super.addAll, which I'm guessing will result in O(n logn).

查看 TreeSet 的 java 源代码，如果传入的集合是 SortedSet，则它看起来像是使用 O(n) 时间算法。否则它会调用 super.addAll，我猜这会导致 O(n logn)。

EDIT - guess I read the code too fast, TreeSet can only use the O(n) algorithm if it's backing map is empty

编辑 - 猜我读代码太快了，如果支持映射为空，TreeSet 只能使用 O(n) 算法

回答by user855

It is not possible to perform merging of trees or join sets like in Disjoint-set data structures because you don't know if the elements in the 2 trees are disjoint. Since the data structures have knowledge about the content in other trees, it is necessary to check if one element exists in the other tree before adding to it or at-least trying to add it into another tree and abort adding it if you find it on the way. So, it should be O(MlogN)

无法像在 Disjoint-set 数据结构中那样执行树的合并或连接集，因为您不知道 2 棵树中的元素是否不相交。由于数据结构知道其他树中的内容，因此有必要在添加到另一棵树之前检查一个元素是否存在于另一棵树中，或者至少尝试将其添加到另一棵树中并在找到它时中止添加道路。所以，它应该是 O(MlogN)