java - TreeMap lastKey 查找时间

Question

SortedMap 接口(interface)的 TreeMap.lastKey() 部分的时间复杂度是多少？

oracle 文档提到了有关 TreeMaps 的内容:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

Answer 1

根据Open JDK中的实现，是O(log N):

public K lastKey() {
    return key(getLastEntry());
}
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

lastKey() 调用 getLastEntry()，它会继续获取正确的子树，直到没有其他节点可以获取为止。由于实现将树保持在平衡状态，因此迭代次数为 O(log N)。