java - Java TreeMap firstEntry() 方法的 Big O 的运行时复杂度是多少？

Question

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

谢谢!

Answer 1

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

您可以看到它是如何在 OpenJDK 中实现的 here .

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

---

如果您正在寻找支持恒定时间查找最小值的结构，也许可以考虑使用 binary min heap ，其中根节点对应于最小值。请注意，这是具有不同语义的完全不同的数据结构。