TreeSet, TreeMap

개요

TreeSet을 이해하기 위해서는 NavigableSet과 SortedSet을, TreeMap을 이해하기 위해서는 NavigableMap과 SortedMap을 이해할 필요가 있다.

TreeSet<E>

SortedSet<E>

SortedSet이 NavigableSet보다 상위 클래스이므로 먼저 살펴보자.

객체들이 정렬되어 있는 Set을 말한다. SortedSet에서 객체들을 정렬하기 위해서는 객체들의 타입인 클래스 E에서 Comparable<E> 인터페이스를 구현하거나, Comparator<E> 인터페이스를 구현한 클래스의 객체를 SortedSet 생성자의 매개변수로 넣어줘야 한다.

특정 객체 검색 메서드

메서드	설명
E first()	정렬 시 첫번째 객체를 반환한다.
E last()	정렬 시 마지막 객체를 반환한다.

부분 Set 반환 메서드

메서드	설명
SortedSet<E> headSet(E toElement)	toElement와 비교했을 때 -1을 반환하는 객체들의 SortedSet을 반환
SortedSet<E> tailSet(E fromElement)	fromElement와 비교했을 때 0이나 1을 반환하는 객체들을 반환
SortedSet<E> subSet(E fromElement, E toElement)	tailSet(fromElement)와 headSet(toElement)의 교집합을 반환

NavigableSet<E>

SortedSet에서 lower(), floor(), ceiling(), higher() 등의 검색 기능과, descendingIterator(), descendingSet() 등의 역순 기능을 추가한 인터페이스이다.

특정 객체 검색 메서드

메서드	설명
ceiling(E e)	e와 비교하여 0이나 양수를 반환하는 객체들 중 가장 앞에 있는 객체를 반환 없으면 null 반환
floor(E e)	e와 비교하여 0이나 음수를 반환하는 객체들 중 가장 뒤에 있는 객체를 반환 없으면 null 반환
higher(E e)	e와 비교하여 양수를 반환하는 객체들 중 가장 앞에 있는 객체를 반환 없으면 null 반환
lower(E e)	e와 비교하여 음수를 반환하는 객체들 중 가장 뒤에 있는 객체를 반환 없으면 null 반환

부분 Set 반환 메서드

메서드	설명
NavigableSet<E> headSet(E toElement, boolean inclusive)	SortedSet의 headSet과 기능 동일, 동등한 객체 포함 여부를 boolean 값으로 결정
NavigableSet<E> tailSet(E fromElement, boolean inclusive)	SortedSet의 tailSet과 기능 동일, 동등한 객체 포함 여부를 boolean 값으로 결정
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	SortedSet의 subSet 기능 동일, 동등한 객체 포함 여부를 boolean 값으로 결정

추가, 제거 메서드

메서드	설명
E pollFirst(), pollLast()	첫번째, 마지막 객체 제거하고 반환 없으면 null 반환

역순 메서드

메서드	설명
Iterator<E> descendingIterator()	역순으로 순회하는 iterator 반환
NavigableSet<E> descendingSet()	역순으로 나열한 Set 반환

TreeSet<E>

NavigableSet을 구현한 클래스이다. 결국 SortedSet도 구현한 것이기 때문에 객체들이 정렬되게 된다. Binary Tree를 기반으로 하기 때문에 각 노드가 왼쪽, 오른쪽 자식 노드를 참조하기 위한 변수를 가진다.

TreeMap<K, V>

SortedMap<K, V>

Map.Entry<K, V>가 정렬되어 있는 Map을 말한다. 정렬을 위해 Key의 타입에 해당하는 클래스를 정렬할 때 사용할 Comparable 이나 Comparator 인터페이스를 구현해야 한다.

Set, Collection 반환 메서드

메서드	설명
Set<Map.Entry<K, V>> entrySet()	Map.Entry들을 Set에 담아 반환
Set<K> keySet()	key들을 모은 Set을 반환
Collection<V> values()	모든 value를 모은 Collection 반환

특정 key 검색 메서드

메서드	설명
K firstKey()	가장 앞에 있는 Entry의 key를 반환
K lastKey()	가장 마지막 Entry의 key를 반환

부분 Map 반환 메서드

메서드	설명
SortedMap<K, V> headMap(K toKey)	toKey와 비교했을 때 음수를 반환하는 Map.Entry들을 SortedMap으로 반환
SortedMap<K, V> tailMap(K fromKey)	toKey와 비교했을 때 0이나 양수를 반환하는 Map.Entry들을 SortedMap으로 반환
SortedMap<K, V> subMap(K fromKey, K toKey)	headMap(toKey)와 tailMap(fromKey)의 교집합

NavigableMap<K, V>

SortedMap에서 특정 key나 entry의 검색 기능과 역순 반복 기능 등을 추가한 인터페이스이다.

특정 key 검색 메서드

메서드	설명
K ceilingKey(K key)	key와 비교했을 때 0 또는 양수를 반환하는 key들 중 가장 앞에 있는 것을 반환
K floorKey(K key)	key와 비교했을 때 0 또는 음수를 반환하는 key들 중 가장 앞에 있는 것을 반환
K higherKey(K key)	key와 비교했을 때 양수를 반환하는 key들 중 가장 앞에 있는 것을 반환
K lowerKey(K key)	key와 비교했을 때 음수를 반환하는 key들 중 가장 앞에 있는 것을 반환

특정 Entry 검색 메서드

메서드	설명
Map.Entry<K, V> firstEntry(), lastEntry()	맨 앞 혹은 뒤에 있는 Entry 반환 없으면 null 반환
Map.Entry<K, V> ceilingEntry(K key)	ceilingKey와 동일한 기능
Map.Entry<K, V> floorEntry(K key)	floorKey와 동일한 기능
Map.Entry<K, V> higherEntry(K key)	higherKey와 동일한 기능
Map.Entry<K, V> lowerEntry(K key)	lowerKey와 동일한 기능

부분 Map 반환 메서드

메서드	설명
NavigableMap<K, V> headMap(K toKey, boolean inclusive)	SortedMap의 headMap과 기능 동일, 경계값 포함 여부를 boolean 값으로 결정
NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)	SortedMap의 headMap과 기능 동일, 경계값 포함 여부를 boolean 값으로 결정
NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	SortedSet의 subMap과 동일한 기능, 경곗값 포함 여부를 boolean 값으로 결정

Entry 추가, 제거 메서드

메서드	설명
Map.Entry<K, V> pollFirstEntry(), pollLastEntry()	첫번째 마지막 Entry 제거하고 반환 없으면 null 반환

역순 메서드

메서드	설명
NavigableSet<K> descendingKeySet()	key들을 역순으로 담은 NavigaableSet을 반환
NavigableMap<K, V> descendingMap()	모든 Entry를 역순으로 나열한 NavigableMap 반환

TreeMap<K, V>

Navigable 인터페이스를 구현한 클래스이다. TreeSet과 마찬가지로 Binary Tree를 기반으로 하며, 각 node가 양쪽 자식의 참조값을 저장하는 변수를 가진다.