我试图澄清一些有关 TreeSet 某些操作的复杂性的事情。在 javadoc 上它说：
“该实施提供了
保证 log(n) 时间成本
基本操作（添加、删除和
包含）”。
到目前为止，一切都很好。我的问题是 addAll()、removeAll() 等发生了什么。Set 的 javadoc 说：
“如果指定的集合也是
set、addAll操作有效
修改该集合，使其值为
两个集合的并集。”
它只是解释操作的逻辑结果还是暗示了复杂性？我的意思是，如果这两个集合由例如表示红黑树最好以某种方式连接树，而不是将其中一个元素“添加”到另一个树中。
无论如何，有没有一种方法可以将两个 TreeSet 合并为一个，复杂度为 O(logn) ？
先感谢您。 :-)
您可以想象如何优化特殊情况O(log n)，但最坏的情况一定是O(m log n) where m and n是每棵树中的元素数量。
Edit:
http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm
描述了一种特殊情况的算法，可以将树连接起来O(log(m + n))但请注意限制：所有成员S1必须小于所有成员S2。这就是我的意思，特殊情况有特殊优化。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
