트리 맵 lastKey 조회 시간

TreeMap.lastKey 시간 복잡도는의 SortedMap 인터페이스() 부분 무엇인가?트리 맵 lastKey 조회 시간

오라클 문서는 트리 맵에 대해이 언급 :

이 구현 넣고 작업을 제거 할 수는 containsKey에 보증 끝난 log (n) 시간 비용을 제공합니다. TreeMap (이것은처럼) containsKey()에 대한 O (로그 (N))를 보장 할 수있는 경우

출처

2014-12-08 Arjun Patel

O (log (n)) 여야합니다. 그것은 대부분 균형을 이루며 항상 우익으로 나아가 야합니다. –

소스 코드를보고 구현 방법을 확인할 수도 있습니다. 그 대답은 꽤 간단합니다. –

알겠습니다. 지도에서 객체를 삭제 한 후에도 마지막 키/값을 항상 추적 할 수있는 우아한 방법이 있습니까? 맵 entrySet과 함께 있을까요? –

은 오픈 JDK의 구현에 따르면, O (N 로그)입니다. 구현은 트리를 균형 잡힌 상태로 유지하므로 반복 횟수는 O (log N)입니다.

출처

2014-12-08 19:01:40 dasblinkenlight

, 뿐만 아니라 (로그 (N)) O에 lastKey()을 할 수 있어야합니다. O (log (n)) 키 룩업을 생성 할 수있는 트리 구조는 O (log (n))에서 최대 키를 찾는 것을 지원할 수도 있습니다. 아무것도 본질적으로 나쁜 않는 뇌사 구현을 배제하지 않지만

, 나는 그것이 java.util.TreeMap에 대해 그 가능성을 할인하는 매우 안전하다고 생각합니다.

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(), 취할 더 이상의 노드가 없을 때까지 오른쪽 서브 트리를 가지고 계속 :

출처

2014-12-08 19:01:11

답변

관련 문제