TreeSet中有序操作的时间复杂度是多少？

Question

java.util.TreeSet以下操作的时间复杂度是多少？

• first()
• last()
• lower()
• higher()

我会假设，这些都是固定的时间，但API不作任何保证。

Answer 1

其实，我一直认为这些操作都将是O(logN)的一般实现。

• 为first()和last()是O(1) TreeSet实现将需要在树分别维持指针最左和最右叶节点。保持这些增加了每次插入的固定成本，并且每次删除都至少保持不变的成本。实际上，这个实现可能会在运行中找到左/右最右节点，这是一个O(logN)操作。

• lower()和higher()方法必须做与get相同的工作，因此O(logN)。

当然，您可以自己检查源代码以查看实际发生的情况。

Answer 2

API不作任何保证，因为它们基于trie的标准模型。最好的情况是O（1），平均情况是O（log n），最坏的情况是O（n）。

从文档：

此实现提供了基本的操作保证的log（n）的时间成本（添加，删除和包含）。

这些不是您要求的功能，而是考虑Java如何遍历TreeSet。

Answer 3

这将取决于实施。我对JAVA并不是非常熟悉，但似乎所有这些操作都是遍历操作（获取最低元素，获得最高元素，获得更高或更低的元素）。

如果该树实现为Self-Balancing Binary Search Tree（如AVL Tree）或任何其他类型的平衡树结构，那么您将分别查看每个平均树和最坏情况O（log n）时间的操作，以及O（1）的最佳案例。

Answer 4

看起来像两个第一（）和last（）将是O（log n）的，而不是O（1）基于其使用TreeSet的默认树形图Implentation（太阳JDK 1.6.0_23）：

/** 
* Returns the first Entry in the TreeMap (according to the TreeMap's 
* key-sort function). Returns null if the TreeMap is empty. 
*/ 
final Entry<K,V> getFirstEntry() { 
    Entry<K,V> p = root; 
    if (p != null) 
     while (p.left != null) 
      p = p.left; 
    return p; 
} 

/** 
* Returns the last Entry in the TreeMap (according to the TreeMap's 
* key-sort function). Returns null if the TreeMap is empty. 
*/ 
final Entry<K,V> getLastEntry() { 
    Entry<K,V> p = root; 
    if (p != null) 
     while (p.right != null) 
      p = p.right; 
    return p; 
} 

Answer 5

我居然抬头看看源代码， 在http://developer.classpath.org/doc/java/util/TreeSet-source.html，first（）调用贴图。firstKey（） 然后 http://developer.classpath.org/doc/java/util/TreeMap-source.html

393: public K firstKey() 
394: (
395: if (root == nil) 
396: throw new NoSuchElementException(); 
397: return firstNode().key; 
398:) 

和firstNode（），它while循环一路向左

952: final Node<K, V> firstNode() 
953: (
954: // Exploit fact that nil.left == nil. 
955: Node node = root; 
956: while (node.left != nil) 
957: node = node.left; 
958: return node; 
959:)