TreeMap lastKey查找时间

Question

SortedMap接口的TreeMap.lastKey（）部分的时间复杂度是多少？

oracle文档提到了有关TreeMap的信息：

此实现为containsKey，get，put和remove操作提供了保证的log（n）时间成本。

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）。