검색 기능에 좋은 컬렉션 TreeSet, TreeMap

 

검색 기능 강화한 컬렉션

컬렉션 프레임워크는 검색 기능 강화한 TreeSet과 TreeMap을 제공합니다. 이진트리를 사용해 계층구조를 가지면서 객체를 저장합니다.

 

이진트리 구조

여러 노드가 트리 형태로 연결된 구조입니다. 루트 노드로 불리는 하나의 노드로 시작해 각 노드는 최대 2개의 노드를 연결할 수 있습니다. 첫 번째 저장 값은 루트, 두 번째 값은 루트 노드부터 시작해 크기를 비교하면서 트리를 내려갑니다. 작은 값은 왼쪽 큰 값은 오른쪽에 저장합니다. 숫자가 아닌 문자를 저장하는 경우 문자 유니코드 값으로 비교합니다. 왼쪽 마지막 노드가 가장 작은 값이, 오른쪽 마지막 노드가 가장 큰 값이 됩니다. 

 

TreeSet

이진트리를 기반으로 하는 Set 컬렉션으로 하나의 노드는 노드값 value와 왼쪽과 오른쪽 자식 노드를 참조하기 위한 두 개의 변수로 구성 됩니다. TreeSet에 객체를 저장하면 자동으로 정렬되는데 부모값과 비교해 낮은 것은 왼쪽 자식 노드로 높은 것은 오른쪽 자식 노드로 저장합니다.

 

부모노드 객체 : left / value / right

자식노드 왼쪽 객체 : left / value / right

자식노드 오른쪽 객체 : left / value / right

 

TreeSet 생성을 위해 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 됩니다.

TreeSet<E> treeSet = new TreeSet<E>();

 

String 객체를 저장하는 TreeSet은 다음과 같습니다.

TreeSet<String> treeSet = new TreeSet<String>();

 

Set 인터페이스 타입 변수에 대입해도 되지만 TreeSet 클래스 타입으로 대입하는 이유는 객체를 찾거나 범위 검색 메서드를 사용하기 위해서 입니다. TreeSet 가지고 있는 검색 관련 메서드

리턴 타입	메서드	설명
E	first()	제일 낮은 객체를 리턴
E	last()	제일 높은 객체를 리턴
E	lower(E e)	주어진 객체보다 바로 아래 객체 리턴
E	higher(E e)	주어진 객체보다 바로 위 객체 리턴
E	floor(E e)	주어진 객체와 동등한 객체가 있으면 리턴 만약 없다면 주어진 객체 바로 아래 객체 리턴
E	ceiling(E e)	주어진 객체와 동등한 객체가 있으면 리턴 만약 없다면 주어진 객체 바로 아래 객체 리턴
E	pollFirst()	제일 낮은 객체 꺼내오고 컬렉션에서 제거
E	pollLast()	제일 높은 객체 꺼내오고 컬렉션에서 제거

 

TreeSet이 갖고 있는 객체 정렬과 관련된 메서드

리턴타입	메서드	설명
Iterator<E>	descendingIterator()	내림차순으로 정렬된 Iterator 리턴
NavigableSet<E>	descendingSet()	내림차순으로 정렬된 NavigableSet 반환

 

NavigableSet<E> descendingSet = treeSet.descendingSet();
NavigableSet<E> ascendingSet = descendingSet.descendingSet();

 

 

TreeSet이 갖고 있는 범위 검색과 관련된 메서드

리턴 타입	메서드	설명
NavigableSet<E>	headSet(     E toElement,     boolean inclusive )	주어진 객체보다 낮은 객체들을 NavigableSet으로 리턴, 주어진 객체 포함 여부는 두 번째 매개값에 따라 달라진다
NavigableSet<E>	tailSet(     E fromElement,     boolean inclusive )	주어진 객체보다 높은 객체들을 NavigableSet으로 리턴, 주어진 객체 포함 여부는 두번째 매개값에 따라 달라진다
NavigableSet<E>	subSet(     E fromElement,     boolean fromInclusive,     E toElement,     boolean toInclusive )	시작과 끝으로 주어진 객체 사이의 객체들을 NavigableSet으로 리턴, 시작과 끝 객체의 포함 여부는 두번째, 네번째 매개값에 따라 달라진다

세 가지 메서드 중에 subSet() 메서드의 사용 방법을 알아보자. subSet() 메서드는 네 개의 매개변수가 있는데 시작 객체와 끝 객체, 그리고 이 객체들을 포함할지 여부의 boolean 값 입니다.

NavigableSet<E> set = treeSet.subSet(E fromElement, boolean fromInclusive // 시작객체, 시작객체 포함여부
E toElement, boolean toInclusive) // 끝 객체, 끝 객체의 포함여부

 

 

TreeMap

이진 트리를 기반으로 하는 Map 컬렉션입니다. TreeSet과의 차이점은 키와 값이 저장된 Map.Entry를 저장합니다. TreeMap 객체를 저장하면 자동으로 정렬되고 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에, 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장합니다.

 

부모 노드 객체 : left / Map.Entry (키, 값) / right

왼쪽 자식 노드 객체 : null / Map.Entry (키, 값) / null

오른쪽 자식 노드 객체 : null / Map.Entry (키, 값) / null

TreeMap을 생성하기 위해 키로 저장할 객체 타입과 값으로 저장할 객체 타입을 타입 파라미터로 주고 기본 생성자를 호출하면 됩니다.

TreeMap<K ,V> treeMap = new TreeMap<K, V>();

키로 String 타입을 사용하고 값으로 Integer 타입을 사용하는 TreeMap은 다음과 같이 생성할 수 있습니다.

TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();

 

Map 인터페이스 타입 변수에 대입해도 되지만 TreeMap 클래스 타입으로 대입한 이유는 특정 객체를 찾거나 범위 검색과 관련된 메서드를 사용하기 위해서 입니다.

리턴 타입	메서드	설명
Map.Entry<K, V>	firstEntry()	제일 낮은 Map.Entry 리턴
Map.Entry<K, V>	lastEntry()	제일 높은 Map.Entry 리턴
Map.Entry<K, V>	lowerEntry(K key)	주어진 키보다 바로 아래 Map.Entry 리턴
Map.Entry<K, V>	higherEntry(K key)	주어진 키보다 바로 위 Map.Entry 리턴
Map.Entry<K, V>	floorEntry(K key)	주어진 키와 동등한 키가 있으면 해당 Map.EEntry를 리턴, 없다면 주어진 키 바로 아래 Map.Entry 리턴
Map.Entry<K, V>	ceilingEntry(K key)	주어진 키와 동등한 키가 있으면 해당 Map.Entry 리턴, 없다면 주어진 키 바로 Map.Entry 리턴
Map.Entry<K, V>	pollFirstEntry()	제일 낮은 Map.Entry를 꺼내오고 컬렉션에서 제거한다
Map.Entry<K, V>	pollLastEntry()	제일 높은 Map.Entry를 꺼내오고 컬렉션에서 제거한다

 

TreeMap 가진 정렬 메서드

리턴 타입	메서드	설명
NavigableSet<K>	descendingKeySet()	내림차순 정렬된 키 NavigableSet리턴
NavigableMap<K, V>	descendingMap()	내림차순 정렬된 Map.Entry의 NavigableMap 리턴

 

TreeMap 범위 검색 메서드

리턴 타입	메서드	설명
NavigableMap<K, V>	headMap(     K toKey,     boolean inclusive )	주어진 키보다 낮은 Map.Entry들을 NavigableMap으로 리턴, 주어진 키의 Map.Entry 포함 여부는 두번째 매개값에 따라 달라진다
NavigableMap<K, V>	tailMap(     K fromKey,     boolean inclusive )	주어진 객체보다 높은 Map.Entry들을 NavigableMap으로 리턴, 주어진 객체 포함 여부는 두 번째 매개값에 따라 달라진다
NavigableMap<K, V>	subMap(     K fromKey,     boolean fromInclusive,     K toKey,     boolean toInclusive )	시작과 끝으로 주어진 키 사이 Map.Entry들을 NavigableMap 컬렉션으로 반환. 시작과 끝 키의 Map.Entry 포함 여부는 두번째, 네번째 매개값에 따라 달라진다.