Java TreeMap firstEntry()方法的Big O中的运行时复杂性是多少？

Question

我知道这个类使用的是红黑树,但是这意味着它是O(log(n))来获得最少的元素还是O(1)或其他什么？

谢谢!

Answer 1

鉴于它是二叉搜索树,它必须遍历树的高度(即O(log n))才能到达第一个(即最少)条目,因此该方法确实是O(log n).

你可以在这里看到它是如何在OpenJDK中实现的.

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

如果您正在寻找支持常量时间查找最小值的结构,可以考虑使用二进制最小堆,其中根节点对应于最小值.请注意,这是一个完全不同的数据结构,具有不同的语义.