TreeSet
TreeSet은 이진 검색 트리binary search tree라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스다. 이진 검색 트리는 정렬, 검색, 범위 검색Range Search에 높은 성능을 보인다. TreeSet은 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리Red-Black tree로 구현 되었다.
Tree는 여러 개의 node가 서로 연결된 구조다. 가장 상위에 있는 노드를 root라고 한다.
위 아래로 연결된 두 노드를 부모-자식 관계라고 한다. 각 노드에 최대 2개의 노드를 연결할 수 있다.
출처 : 자바의 정석 기초편 요약집
위 표는 TreeSet에 7,4,9,1,5를 순서대로 저장한다고 했을 때 진행과정이다.
- 맨 처음 저장되는 데이터 7이 루트root가 된다.
- 그 다음 저장되는 값은 루트와 비교해서 루트보다 크면 오른쪽, 작으면 왼쪽에 저장된다.
이처럼 Tree구조는 검색이나 정렬에는 뛰어난 성능을 보이지만 데이터의 추가나 삭제에서는 효율이 떨어진다.
특징을 정리하면 이렇다.
- 모든 노드는 최대 두 개의 자식 노드를 가질 수 있다.
- 왼쪽 자식 노드는 부모 노드 값보다 작고, 오른쪽 자식 노드는 부모노드의 값보다 커야 한다.
- 노드의 추가, 삭제에 시간이 걸린다.
- 검색, 정렬에 유리하다.
- 중복값 저장하지 않는다.
TreeSet의 메서드
| method | 설명 |
|---|---|
| TreeSet(Collection c) | 지정한 컬렉션을 가지는 TreeSet 생성 |
| TreeSet(Comparator comp) | 지정한 정렬조건으로 정렬하는 TreeSet생성 |
| TreeSet(SortedSet s) | 주어진 SortedSet을 구현한 컬렉션을 저장하는 객체 Tree Set생성 |
| boolean add(Object o) boolean addAll(Collecton c) |
지정한 객체o 또는 Collection의 객체를 추가 |
| Object ceiling(Object o) | 지정한 객체와 같은 객체를 반환. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null |
| void clear() | 모든 객체 삭제 |
| Object clone() | 객체를 복제하여 반환 |
| Comparator comparator() | 정렬 기준을 반환 |
| boolean contains(Object o) boolean containsAll(Collection c) |
지정한 객체 또는 Collection의 객체를 포함하는지 확인 |
| NavigableSet descendingSet() | TreeSet에 저장된 요소를 역순으로 정렬해서 반환 |
| Ojbect first() | 정렬된 순서에 첫 번째 객체를 반환 |
| Object floor(Object o) | 지정한 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중에서 제일 가까운 값의 객체를 반환. 없으면 null |
| SortedSet headSet(Object toElement) | 지정한 객체보다 작은 값의 객체를 반환 |
| NavigableSet headSet(Object toElement, boolean inclusive) | 지정한 객체보다 작은 값의 객체를 반환 inclusive가 true면 같은 값 객체도 포함 |
| Object higher(Object o) | 지정한 객체보다 큰 값을 가진 객체 중 제일 가까운 객체를 반환, 없으면 null |
| boolean isEmpty() | TreeSet이 비었는지 확인 |
| Iterator iterator() | Iterator 반환 |
| Object last() | 정렬한 순서에서 마지막 객체를 반환 |
| Object lower(Object o) | 지정한 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null |
| Object pollFirst() | 첫 번째 요소(제일 작은 값의 객체)를 반환 |
| Object pollLast() | 마지막 번째 요소(제일 큰 값의 객체)를 반환 |
| boolean remove(Object o) | 지정한 객체를 삭제 |
| boolean retainAll(Collection c) | 주어진 컬렉션과 공통된 요소만 남기고 삭제 |
| boolean size() | 객체의 수 반환 |
| Spliterator spliterator() | Spliterator반환 |
| SortedSet subSet(Object fromElement, Object toElement) | 범위 검색 from~to사이의 결과를 반환. 끝 범위toElement은 포함되지 않음 |
| Navigable< E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) | 범위 검색. from-to사이를 반환. fromInclusvie가 true면 시작 값 포함, toInclusive가 true면 마지막값 포함 |
| SortedSet tailSet(Object fromElement) | 지정한 객체보다 더 큰 값의 객체를 반환 |
| Object[] toArray() | 저장한 객체를 객체배열로 반환 |
| Object[] toArrays(Object[] a) | 저장한 객체를 주어진 객체배열에 저장 |
package com.javaex.ch11;
import java.util.TreeSet;
public class TreeSetEx1 {
public static void main(String[] args) {
TreeSet set = new TreeSet();
String from = "b";
String to = "d";
set.add("abc");
set.add("ailen");
set.add("bat");
set.add("car");
set.add("Car");
set.add("disc");
set.add("dance");
set.add("dZZZZ");
set.add("dzzzz");
set.add("elephant");
set.add("elevator");
set.add("fan");
set.add("flower");
System.out.println(set);
System.out.println("range search : from " + from + " to : "+to);
System.out.println("result 1 : " + set.subSet(from, to));
System.out.println("result 2 : " + set.subSet(from,to+"zzz"));
}
}
/*
결과 :
[Car, abc, ailen, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from b to : d
result 1 : [bat, car]
result 2 : [bat, car, dZZZZ, dance, disc]
*/subSet("b", "d")로 지정하면
b~d사이의 문자로 시작하는 데이터를 출력한다.
마지막 문자인 d는 출력하지 않는다.