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)个比较,除了第一个和最后一个是O(1)比较或O(ln N)个节点搜索时间.

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

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

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

Answer 2

first()、last()、pollFirst()、pollLast()：O(lgn)，而不是 O(1)。