java - 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;
}

---

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