컬렉션 프레임워크는 검색 기능을 강화시킨
TreeSet
과TreeMap
을 제공하고 있다.
TreeSet
은 Set
컬렉션이고, TreeMap
은 Map
컬렉션이다. 이 컬렉션들은 이진 트리(binary tree
)를 이용해서 계층적 구조(Tree
구조)를 가지면서 객체를 저장한다.
이진 트리(
binary tree
)는 여러 개의 노드가 트리 형태로 연결된 구조로, 루트 노드라고 불리는 하나의 노드에서부터 시작해서 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다.
첫 번째로 저장되는 값은 루트 노드가 되고, 두 번째 값은 루트 노트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다. 숫자가 아닌 문자를 저장할 경우에는 문자의 유니코드 값으로 비교한다. 이렇게 트리를 구성하면, 왼쪽 마지막 노드가 제일 작은 값이 되고 오른쪽 마지막 노드가 가장 큰 값이 된다.
왼쪽 마지막 노드에서부터 오른쪽 마지막 노드까지 왼쪽 노드 → 부모 노드 → 오른쪽 노드
순으로 값을 읽으면 오름차순으로 정렬된 값을 얻을 수 있고, 반대로 오른쪽 마지막 노드에서부터 왼쪽 마지막 노드까지 오른쪽 노드 → 부모 노드 → 왼쪽 노드
순으로 값을 읽으면 내림차순으로 정렬된 값을 얻을 수 있다.
이진 트리가 범위 검색을 쉽게할 수 있는 이유는 값들이 정렬되어 있어 그룹핑이 쉽기 때문이다.
TreeSet
은 이진 트리를 기반으로 한Set
컬렉션이다.
Red-Black tree
)로 구현한다.
TreeSet
을 생성하기 위해서는 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.TreeSet<E> treeSet = new TreeSet<E>();
TreeSet<String> treeSet = new TreeSet<String>();
Set
인터페이스 타입 변수에 대입해도 되지만 TreeSet
클래스 타입으로 대입한 이유는 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위해서이다. 다음은 TreeSet이 가지고 있는 검색 관련 메소드들이다.
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<Integer> scores = new TreeSet<Integer>();
scores.add(87);
scores.add(98);
scores.add(75);
scores.add(95);
scores.add(80);
Integer score = null;
score = scores.first();
System.out.println("가장 낮은 점수: " + score);
score = scores.last();
System.out.println("가장 높은 점수: " + score + "\n");
score = scores.lower(95);
System.out.println("95점 아래 점수: " + score);
score = scores.higher(95);
System.out.println("95점 위의 점수: " + score + "\n");
score = scores.floor(95);
System.out.println("95점 이거나 바로 아래 점수: " + score);
score = scores.ceiling(95);
System.out.println("95점 이거나 바로 위의 점수: " + score + "\n");
while (!scores.isEmpty()) {
score = scores.pollFirst();
System.out.println(score + " (남은 객체 수: " + scores.size() + ")");
}
}
}
가장 낮은 점수: 75
가장 높은 점수: 98
95점 아래 점수: 87
95점 위의 점수: 98
95점 이거나 바로 아래 점수: 95
95점 이거나 바로 위의 점수: 95
75 (남은 객체 수: 4)
80 (남은 객체 수: 3)
87 (남은 객체 수: 2)
95 (남은 객체 수: 1)
98 (남은 객체 수: 0)
descendingIterator()
메소드는 내림차순으로 정렬된 Iterator 객체를 리턴한다.descendingSet()
메소드는 내림차순으로 정렬된 NavigableSet 객체를 리턴한다.first()
, last()
, lower()
, higher()
, floor()
, ceiling()
메소드를 제공하고, 정렬 순서를 바꾸는 descendingSet()
메소드도 제공한다.descendingSet()
메소드를 두 번 호출하면 된다.NavigableSet<E> descendingSet = treeSet.descendingSet();
NavigableSet<E> ascendingSet = descendingSet.descendingSet();
세 가지 메소드 중에서 subSet()
메소드의 사용 방법을 자세히 살펴보도록 하자. subSet()
메소드는 네 개의 매개 변수가 있는데, 시작 객체
와 끝 객체
, 그리고 이 객체들을 포함할지 여부의 boolean 값
을 받는다.
NavigableSet<E> set = treeSet.subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
E fromElement
: 시작 객체boolean fromInclusive
: 시작 객체의 포함 여부E toElement
: 끝 객체boolean toInclusive
: 끝 객체의 포함 여부이것이 자바다 책
http://tcpschool.com/java/java_collectionFramework_set