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:)