java - TreeMap lastKey 查找时间

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

oracle 文档提到了关于 TreeMaps 的这一点:

最佳答案

根据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)。