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

根据 TreeSet 默认使用的 TreeMap 的实现（sun jdk 1.6.0_23），看起来first()和last()都是O(log n)而不是O(1)：

 /**
 * 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;
}