들어가며

  • 해당 시리즈는 Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet에서 이어진다.
  • 이번엔 Associative Containers의 종류 중 하나인 TreeMap에 대하여 알아볼 것이다.

2023.01.15 - [Algorithm/Before Check] - Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet

 

Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet

들어가며 해당 시리즈는 Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - LinkedList에서 이어진다. 이번에는 데이터가 정렬된 상태를 유지하게 하는 자료구조인 Associative Containers에 대하여 알

sehun5515.tistory.com

 

 

Map의 정의

  • TreeSet을 알아보기 이전에 Set에 대하여 알아본 것 처럼 TreeMap을 이해하기 위해서는 Map에 대한 선행지식이 요구된다. 따라서 Map에 대하여 간략하게 알아보자.
  • Map <Key, Value>로 이루어진 한 쌍이 하나의 요소로 이 요소들로 이루어진 자료구조가 Map이다. 이 구조와 이에 필요한 연산을 정의한 것이 Map 인터페이스이다. Python을 한 적이 있는 사람이라면 딕셔너리가 이 Map이라고 할 수 있겠다.
  • Map에서 Key와 Value는 다음의 특징을 가진다.
    • Key는 해당 Map에서 유일하게 존재해야한다. 즉, 중복된 key가 Map에 존재해선 안된다.
    • Value는 해당 Map에서 유일하게 존재하지 않아도 된다. 즉, 중복된 Value가 서로 다른 Key에 존재할 수 있다.
  • C++에선 Key의 중복을 허용하는 std::multimap, std::multiset이 존재하나 Java는 자체적으로는 아직 존재하지 않고 google의 패키지에서 지원하는 구조가 있는 것으로 알고있다.
  • Java에서 바로 <Key, Value>쌍을 표현하기는 어렵기 때문에 Map의 내부요소들은 Map.Entry<>라는 인터페이스로 감싸지는 방식으로 <Key, Value>쌍을 표현하였다.

 

 

TreeMap의 정의

  • TreeMap은 이전에 TreeSet을 본 사람은 유추할 수 있겠지만 이진 검색 트리를 사용한 Map이다. 정렬되어 있고, 정렬된 순서를 유지한다는 것이 Map과의 차이점이다.
  • 동일하게 이진 검색 트리를 사용한 자료구조이기 때문에 연산 메서드의 이름도 비슷한 것들이 많다. TreeMap의 연산 종류는 다음과 같다.
메서드 메서드 타입 설명
TreeMap() constructor TreeMap 객체를 반환한다.
TreeMap(Comparator comp) constructor 지정된 비교방법으로 정렬하는 TreeMap 객체를 반환한다.
TreeMap(Map m) constructor Map의 모든 요소를 포함하고 있는 정렬된 TreeMap객체를 반환한다.
ceilingEntry(K k) Map.Entry<K, V> 지정된 키보다 크거나 같은 요소들 중 가장 가까운 엔트리를 반환한다.
ceilingKey(K k) K 지정된 키보다 크거나 같은 요소들 중 가장 가까운 엔트리의 키를 반환한다.
comparator() Comparator<> TreeMap이 현재 사용하는 Comparator 객체를 반환한다.
containsKey(Object key) boolean 지정된 키가 TreeMap에 존재하는지 확인한다.
containsValue(Object val) boolean 지정된 값이 TreeMap에 존재하는지 확인한다.
descendingKeySet() NavigableSet<K> TreeMap을 역순으로 정렬한 결과를 Set으로 반환한다.
descendingMap() NavigableMap<K, V> TreeMap을 역순으로 정렬한 결과를 Map으로 반환한다.
entrySet() Set<Map.Entry<K, V>> TreeMap의 모든 요소를 Set으로 변환하여 반환한다. TreeMap의 특성상 정순정렬한 결과를 반환하게 된다,
firstEntry() Map.Entry<K, V> TreeMap의 첫 번째 엔트리를 반환한다.
firstKey() K TreeMap의 첫 번째 엔트리의 키를 반환한다.
floorEntry(K k) Map.Entry<K, V> 지정된 키보다 작거나 같은 요소들 중 가장 가까운 엔트리를 반환한다.
floorKey(K k) K 지정된 키보다 작거나 같은 요소들 중 가장 가까운 엔트리의 키를 반환한다.
get(Object key) V 지정된 키에 존재하는 값을 가져온다.
headMap(K toKey) SortedMap<K, V> 지정된 키보다 작은 키를 가진 요소들의 Map을 반환한다.
headMap(K toKey, boolean inclusive) NavigableMap<K, V> 지정된 키보다 작은 키를 가진 요소들의 Map을 반환한다. Inclusive가 true라면 지정된 키도 포함된다.
higherEntry(K key) Map.Entry<K, V> 지정된 키보다 큰 키의 엔트리 중 가장 가까운 엔트리를 반환한다. 존재하지 않을 시 null을 반환한다.
higherKey(K key) K 지정된 키보다 큰 키의 엔트리 중 가장 가까운 엔트리의 키를 반환한다. 존재하지 않을 시 null을 반환한다.
keySet() Set<K> TreeMap의 모든 키를 Set으로 반환한다.
lastEntry() Map.Entry<K, V> TreeMap의 마지막 엔트리를 반환한다.
lastKey() K TreeMap의 마지막 엔트리의 키를 반환한다.
lowerEntry(K key) Map.Entry<K, V> 지정된 키보다 작은 키들 중 가장 가까운 키의 엔트리를 반환한다.
lowerKey(K key) K 지정된 키보다 작은 키들 중 가장 가까운 키를 반환한다.
put(K key, V value) V TreeMap에 <key, value>를 삽입한다.
putAll(Map m) void 지정된 Map의 모든 요소를 TreeMap에 삽입한다.
remove(Object key) V TreeMap에 지정된 key의 <key, value>를 삭제한다.
replace(K key, V value) V TreeMap에 지정된 key의 값을 value로 재지정한다.
replace(K key V oldVal, V newVal) boolean TreeMap에 지정된 key와 oldVal이 동일한 요소의 값을 newVal로 재지정한다.
subMap(K fromKey boolean fromInclusive, K toKey, boolean toInclusive) NavigableMap<K, V> fromKey부터 toKey사이의 요소들을 Map으로 담아 반환한다. 각 inclusive가 true이면 각 요소들도 포함된다.
subMap(K fromKey, K toKey) SortedMap<K, V> fromKey부터 toKey사이의 요소들을 Map으로 담아 반환한다. fromKey는 포함되고 toKey는 포함되지 않는다.
tailMap(K fromKey) SortedMap<K, V> fromKey보다 큰 요소들을 담아 Map으로 반환한다.
tailMap(K fromKey, boolean inclusive) NavigableMap<K, V> fromKey보다 큰 요소들을 담아 Map으로 반환한다. Inclusive가 true이면 fromKey도 포함된다.
values() Collection<V> TreeMap내의 모든 값을 Collection으로 반환한다.
pollFirstEntry() Map.Entry<K, V> TreeMap의 처음 엔트리를 제거하고 그 엔트리를 반환한다.
pollLastEntry() Map.Entry<K, V> TreeMap의 마지막 엔트리를 제거하고 그 엔트리를 반환한다.

 

 

복사했습니다!