[Java] Class TreeSet
JavaCollection Framework
데이터 군을 저장하는 클래스들을 표준화한 설계
컬렉션 Collection : 다수의 데이터. 데이터 그룹
프레임웍 Framework : 표준화된 프로그래밍 방식.
Class TreeSet
이진 검색 트리 형태로 데이터를 저장하는 컬렉션 클래스.
이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현되어 있다.
데이터의 중복 저장이 불가능하며 저장 순서를 유지하지 않는다.
이진 트리 Binary Tree
링크드리스트처럼 여러 개의 노드(Node)가 서로 연결된 구조.
루트(Root)라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다.
위 아래로 연결된 두 노드를 '부모-자식 관계'에 있다고 한다. (상대적)
각 노드에 최대 2개의 노드(자식 노드)를 연결할 수 있다.
- 트리(Tree)
각 노드 간의 연결된 모양이 나무와 같다고 해서 붙여진 이름.
이진 검색 트리 Binary Search Tree
정렬, 검색, 범위 검색(Range Search)에 높은 성능을 보이는 자료 구조.
부모 노드의 왼쪽에는 부모 노드의 값보다 작은 값의 자식 노드를,
오른 쪽에는 큰 값의 자식 노드를 저장하는 이진 트리.
데이터를 순차적으로 저장하는 것이 아니라서 데이터 추가/삭제에 시간이 걸린다.
- ex) 5, 1, 9, 4의 순서로 값을 저장할 경우
| Left | Element | Right | |
|---|---|---|---|
| Root | 0x100 | 5 | 0x200 |
| 0x100 | null | 1 | 0x300 |
| 0x200 | null | 9 | null |
| 0x300 | null | 4 | null |
첫 번째로 저장되는 값은 루트가 되고,
두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다.
저장되는 객체가 Comparable을 구현하거나, Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다.
그렇지 않으면 두 번째 객체를 저장할 때 예외가 발생한다.
Public constructors
| 생성자 | 설명 |
|---|---|
| TreeSet() | 기본 생성자 |
| TreeSet(Comparator<? super E> comparator) | 주어진 정렬조건으로 정렬하는 TreeSet 생성 |
| TreeSet(Collection<? extends E> c) | 주어진 컬렉션을 저장하는 TreeSet 생성 |
| TreeSet(SortedSet s) | 주어진 SortedSet을 구현한 컬렉션을 저장하는 TreeSet 생성 |
Public methods
| 반환타입 | 이름 | 설명 |
|---|---|---|
| boolean | add(E e) | 지정된 객체를 추가 (중복되지 않는 경우) |
| boolean | addAll(Collection<? extends E> c) | 지정된 Collection의 객체들을 Collection에 추가 |
| E | ceiling(E e) | 지정된 객체와 같은 객체 반환. 같은 객체가 없으면 큰 값 중 가장 가까운 값의 객체 반환 가까운 객체도 없으면 null |
| void | clear() | 저장된 모든 객체 삭제 |
| Object | clone() | TreeSet 복제하여 반환 |
| Comparator<? super E> | comparator() | TreeSet의 정렬 기준 반환 |
| boolean | contains(Object o) | 지정된 객체가 포함되어 있는 지 확인 |
| NavigableSet | descendingSet() | TreeSet에 저장된 요소들을 역순으로 정렬해서 반환 |
| E | first() | 정렬된 순서에서 첫 번째 객체 반환 |
| E | floor(E e) | 지정된 객체와 같은 객체 반환. 같은 객체가 없으면 작은 값 중 가장 가까운 값의 객체 반환 가까운 객체도 없으면 null |
| NavigableSet | headSet(E toElement, boolean inclusive) | 지정된 객체보다 작은 값의 객체들을 반환 inclusive가 null이면 같은 값의 객체도 포함 |
| SortedSet | headSet(E toElement) | 지정된 객체보다 작은 값의 객체들을 반환 |
| E | higher(E e) | 지정된 객체보다 큰 값을 가진 객체 중 가장 가까운 값의 객체 반환. 없으면 null |
| boolean | isEmpty() | TreeSet이 비어 있는 지 확인 |
| Iterator | iterator() | TreeSet의 Iterator 반환 |
| E | last() | 정렬된 순서에서 마지막 객체 반환 |
| E | lower(E e) | 지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체 반환. 없으면 null |
| E | pollFirst() | TreeSet의 첫 번째 요소(가장 작은 값의 객체) 반환 |
| E | pollLast() | TreeSet의 마지막 번째 요소(가장 큰 값의 객체) 반환 |
| boolean | remove(Object o) | 지정된 객체 삭제 |
| int | size() | 저장된 객체의 개수 반환 |
| Spliterator | spliterator() | TreeSet의 spliterator 반환 |
| NavigableSet | subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) | 범위 검색(fromElement과 toElement 사이)의 결과 반환 fromInclusive가 true면 시작 값 포함. toInclusive가 true면 끝 값 포함 |
| SortedSet | subSet(E fromElement, E toElement) | 범위 검색(from과 to 사이)의 결과 반환. 끝 범위는 불포함 |
| SortedSet | tailSet(E fromElement) | 지정된 객체보다 큰 값의 객체들을 반환 |
subSet()
범위 검색.
끝 범위를 포함하지 않는다.
대소문자가 섞여 있으면 의도한 것과 다른 결과를 얻을 수 있으므로 가능하면 대문자/소문자로 통일해서 저장하는 것이 좋다.
package blog;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
TreeSet<String> set = new TreeSet<>();
String from = "b";
String to = "d";
set.add("abs");
set.add("alien");
set.add("battle");
set.add("cat");
set.add("Cat");
set.add("design");
set.add("dance");
set.add("dZ");
set.add("dzz");
set.add("elevator");
set.add("event");
set.add("family");
set.add("flower");
System.out.println(set); // [Cat, abs, alien, battle, cat, dZ, dance, design, dzz, elevator, event, family, flower]
System.out.println(set.subSet(from, to)); // [battle, cat]
System.out.println(set.subSet(from, to + "zzzzz")); // [battle, cat, dZ, dance, design, dzz]
}
}대소문자가 섞여 있어야 하거나, 다른 방식으로 정렬해야 할 경우 Comparator를 이용한다.
- 문자열의 정렬 순서
- 문자의 코드값 순
- 오름차순 : 공백, 숫자, 대소문자, 소문자 순.
headSet()/tailSet()
저장된 객체 중 지정된 기준 값보다 작은/큰 값의 객체들을 반환한다.
package blog;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
int score[] = { 15, 27, 49, 60, 88, 91, 73 };
for (int i = 0; i < score.length; i++) {
set.add(new Integer(score[i]));
}
System.out.println(set.headSet(50)); // [15, 27, 49]
System.out.println(set.tailSet(50)); // [60, 73, 88, 91]
}
}참고 서적: 자바의 정석 3판 2
