Computational Complexity of TreeSet methods in Jav

问题:

Is the computational complexity of TreeSet methods in Java, same as that of an AVLTree?

Specifically, I want to know the computational complexity of the following methods: 1.add 2.remove 3.first 4.last 5. floor 6. higher

Java Doc for method description: http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

For an AVL Tree, there are all O(logn)? Whats the complexity of the above TreeSet Methods?

回答1:

Operations which work on a single element are all O(ln n) comparisons except first and last which are O(1) comparisons or O(ln N) node search time.

comparator(), iterator(), clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast() are O(1)

add(), ceiling(), contains(), floor(), headSet(), higher(), lower(), remove(), subSet(), tailSet() are O(ln N)

clone(), equals(), hashCode(), toArray() and toString() are O(n)