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

---

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