java - Java 中 TreeSet 方法的计算复杂度

Question

Java中TreeSet方法的计算复杂度和AVLTree一样吗？

具体来说，我想知道以下方法的计算复杂度： 1.add 2.remove 3.first 4.last 5. floor 6.higher

用于方法描述的 Java Doc：http: //docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

对于 AVL 树，所有的 O(logn)？上述 TreeSet 方法的复杂性是什么？

Answer 1

对单个元素起作用的操作都是 O(ln n) 比较，除了第一个和最后一个是 O(1) 比较或 O(ln N) 节点搜索时间。

比较器（），迭代器（），清除（），第一（），isEMpty（），大小（），最后（），pollFirst（），pollLast（）是O（1）

add(), ceiling(), contains(), floor(), headSet(), Higher(), lower(), remove(), subSet(), tailSet() 是 O(ln N)

clone()、equals()、hashCode()、toArray() 和 toString() 是 O(n)