TreeSet 클래스 메서드 총 정리

Hierarchy of Java Collections

 

TreeSet 클래스 선언부

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable

 

메서드/설명	예제	결과
import java.util.TreeSet;
TreeSet() TreeSet 생성 ( 기본 : 오름차순 )	TreeSet<Integer> set = new TreeSet<>(); set.add(3); set.add(1); set.add(2); System.out.println(set);	[1, 2, 3]
TreeSet(Collection<? extends E> c) 주어진 컬렉션을 저장하는 TreeSet 생성 ( 기본 : 오름차순 )	List<String> list = Arrays.asList("banana", "apple", "cherry"); TreeSet<String> set = new TreeSet<>(list); System.out.println(set);	[apple, banana, cherry]
TreeSet(Comparator<? super E> comparator) 지정된 비교자(Comparator)를 기준으로 정렬되는 TreeSet을 생성한다.	TreeSet<String> set = new TreeSet<>(Comparator.reverseOrder()); set.add("apple"); set.add("banana"); set.add("cherry"); System.out.println(set);	[cherry, banana, apple]
TreeSet(SortedSet<E> s) 주어진 SortedSet의 요소들을 포함하는 TreeSet을 생성한다.	SortedSet<Integer> sortedSet = new TreeSet<>(); sortedSet.add(100); sortedSet.add(50); TreeSet<Integer> set = new TreeSet<>(sortedSet); System.out.println(set);	[50, 100]
boolean add(E e) 주어진 객체(o)를 추가	TreeSet<String> set = new TreeSet<>(); System.out.println(set.add("A")); System.out.println(set.add("A")); System.out.println(set);	true   false   [A]
boolean addAll(Collection<? extends E> c) 컬렉션 c의 모든 요소를 TreeSet에 추가한다. 중복은 무시된다.	TreeSet<String> set = new TreeSet<>(); List<String> list = Arrays.asList("A", "C", "B"); set.addAll(list); System.out.println(set);	[A, B, C]
E ceiling(E e) 주어진 값 이상인 가장 작은 값을 반환. 없으면 null.	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); System.out.println(set.ceiling(15));  // 20 System.out.println(set.ceiling(30));  // 30 System.out.println(set.ceiling(35));  // null	20   30   null
Comparator<? super E> comparator() TreeSet의 정렬기준을 반환	TreeSet<Integer> set = new TreeSet<>(); System.out.println(set.comparator());  // null (기본 정렬) TreeSet<Integer> custom = new TreeSet<>(Comparator.reverseOrder()); System.out.println(custom.comparator());  // java.util.Comparator$$Lambda...	null   (Comparator 객체 정보 출력)
Iterator descendingIterator() TreeSet의 요소들을 내림차순으로 순회할 수 있는 Iterator를 반환한다.	TreeSet<Integer> set = new TreeSet<>(); set.add(1); set.add(2); set.add(3); Iterator<Integer> it = set.descendingIterator(); while (it.hasNext()) {     System.out.print(it.next() + " "); }	3 2 1
NavigableSet descendingSet() 요소들을 내림차순으로 정렬하여 NavigableSet으로 반환한다.	TreeSet<Integer> set = new TreeSet<>(); set.add(1); set.add(2); set.add(3); NavigableSet<Integer> desc = set.descendingSet(); System.out.println(desc);	[3, 2, 1]
E floor(E e) 주어진 값 이하인 가장 큰 값을 반환. 없으면 null.	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); System.out.println(set.floor(25));  // 20 System.out.println(set.floor(5));   // null	20   null
SortedSet headSet(E toElement) 지정된 값보다 작은 요소들만 포함된 SortedSet 반환 (exclusive)	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); SortedSet<Integer> head = set.headSet(20); System.out.println(head);	[10]
NavigableSet headSet(E toElement, boolean inclusive) 지정된 값보다 작거나 같으면 inclusive = true, 보다 작을 경우 inclusive = false로 설정하여 NavigableSet 반환.	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); System.out.println(set.headSet(20, true));   // [10, 20] System.out.println(set.headSet(20, false));  // [10]	[10, 20]   [10]
E higher(E e) 지정된 값보다 큰 값 중 가장 작은 값 반환. 없으면 null.	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); System.out.println(set.higher(20));  // 30 System.out.println(set.higher(30));  // null	30   null
Iterator iterator() TreeSet을 오름차순으로 순회할 수 있는 Iterator 반환.	TreeSet<String> set = new TreeSet<>(); set.add("A"); set.add("B"); set.add("C"); Iterator<String> it = set.iterator(); while (it.hasNext()) {     System.out.print(it.next() + " "); }	A B C
E lower(E e) 주어진 값보다 작은 값 중 가장 큰 값 반환. 없으면 null.	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); System.out.println(set.lower(20));  // 10 System.out.println(set.lower(10));  // null	10   null
E pollFirst() TreeSet에 저장된 요소 중 가장 작은 값(첫 번째 요소)을 꺼내서 반환하고, 해당 요소를 Set에서 제거한다.	TreeSet<Integer> set = new TreeSet<>(); set.add(5); set.add(1); set.add(3); System.out.println(set.pollFirst());  // 1 System.out.println(set); // [3, 5]	1   [3, 5]
E pollLast() TreeSet에 저장된 요소 중 가장 큰 값(마지막 번째 요소)을 꺼내서 반환하고, 해당 요소를 Set에서 제거한다.	TreeSet<Integer> set = new TreeSet<>(); set.add(5); set.add(1); set.add(3); System.out.println(set.pollLast());   // 5 System.out.println(set); // [1, 3]	5   [1, 3]
Spliterator spliterator() TreeSet을 순회할 수 있는 Spliterator를 반환한다. (병렬 처리에도 활용 가능)	TreeSet<String> set = new TreeSet<>(); set.add("A"); set.add("B"); set.add("C"); Spliterator<String> spliterator = set.spliterator(); spliterator.forEachRemaining(System.out::println);	A   B   C
NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) 범위 검색: 시작값과 끝값 포함 여부를 지정하여 해당 구간의 요소만 반환.( fromInclusiver가 true면 시작값 포함,toInclusive가 true면 끝 값 포함. )	TreeSet<Integer> set = new TreeSet<>(); set.add(1); set.add(2); set.add(3); set.add(4); set.add(5); System.out.println(set.subSet(2, true, 4, true));   // 2~4 포함 System.out.println(set.subSet(2, false, 4, false)); // 2,4 제외	[2, 3, 4]   [3]
SortedSet subSet(E fromElement, E toElement)) fromElement 이상, toElement 미만의 범위 요소를 반환한다. (끝 범위는 미포함)	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); set.add(40); SortedSet<Integer> subset = set.subSet(15, 35); System.out.println(subset);	[20, 30]
SortedSet tailSet(E fromElement) 지정된 객체보다 큰 값의 객체들을 반환	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); SortedSet<Integer> tail = set.tailSet(20); System.out.println(tail);	[20, 30]
NavigableSet tailSet(E fromElement, boolean inclusive) fromElement 이상을 포함할지 여부를 지정해 반환. inclusive = false면 제외됨.	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(20); set.add(30); System.out.println(set.tailSet(20, true));   // 포함 System.out.println(set.tailSet(20, false));  // 제외	[20, 30]   [30]
boolean contains(Object o) 지정된 객체(o)가 포함되어 있는지 확인	TreeSet<String> set = new TreeSet<>(); set.add("apple"); System.out.println(set.contains("apple")); System.out.println(set.contains("banana"));	true   false
boolean containsAll(Collection<?> c) 주어진 컬렉션의 객체들이 모두 포함되어 있는지 확인	TreeSet<String> set = new TreeSet<>(); set.addAll(Arrays.asList("A", "B", "C")); List<String> test = Arrays.asList("A", "C"); System.out.println(set.containsAll(test));	true
boolean isEmpty() TreeSet이 비어있는지 여부를 반환한다.	TreeSet<Integer> set = new TreeSet<>(); System.out.println(set.isEmpty()); set.add(1); System.out.println(set.isEmpty());	true   false
boolean remove(Object o) 지정된 객체를 삭제	TreeSet<String> set = new TreeSet<>(); set.add("A"); set.add("B"); set.remove("A"); System.out.println(set);	[B]
void clear() 지정된 모든 객체 삭제	TreeSet<Integer> set = new TreeSet<>(); set.add(1); set.add(2); set.clear(); System.out.println(set);	[]
Object clone() TreeSet을 얕은 복사(clone)하여 새로운 TreeSet 객체를 반환한다.	TreeSet<String> set = new TreeSet<>(); set.add("X"); TreeSet<String> copy = (TreeSet<String>) set.clone(); System.out.println(copy);	[X]
E first() 정렬된 순서에서 첫 번째 객체 반환	TreeSet<Integer> set = new TreeSet<>(); set.add(30); set.add(10); set.add(20); System.out.println(set.first());	10
E last() 정렬된 순서에서 마지막 객체 반환	TreeSet<Integer> set = new TreeSet<>(); set.add(10); set.add(40); set.add(20); System.out.println(set.last());	40
int size() TreeSet에 저장된 객체 수 반환	TreeSet<String> set = new TreeSet<>(); set.add("A"); set.add("B"); System.out.println(set.size());	2
boolean retainAll(Collection c) 주어진 컬렉션과 공통된 요소만을 남기고 삭제 ( 교집합 )	TreeSet<String> set = new TreeSet<>(); set.addAll(Arrays.asList("A", "B", "C")); List<String> keep = Arrays.asList("A", "C"); set.retainAll(keep); System.out.println(set);	[A, C]
Object[] toArray() 지정된 객체를 Object 객체배열로 반환	TreeSet<String> set = new TreeSet<>(); set.add("apple"); set.add("banana"); Object[] arr = set.toArray(); System.out.println(Arrays.toString(arr));	[apple, banana]
<T> T[] toArray(T[] a) 저장된 객체를 주어진 객체배열에 저장하여 반환	TreeSet<String> set = new TreeSet<>(); set.add("apple"); set.add("banana"); String[] arr = set.toArray(new String[0]); System.out.println(Arrays.toString(arr));	[apple, banana]

 

TreeSet이란?

TreeSet은 HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다. 

 

하지만 HashSet과는 달리 TreeSet은 이진 탐색 트리의 성능을 향상시킨 "레드-블랙 트리(Red-Black tree)"로 구현되어 있다. 

 

이진 탐색 트리는 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색, 범위 검색(range search)에 높은 성능을 보이는 자료구조이다. 

 

그렇기에 HashSet보다 데이터의 추가/삭제는 시간이 더 걸리지만 검색과 정렬에는 유리하다.

 

레드-블랙 트리(Red-Black Tree)

Red-Black Tree

TreeSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리(Red-Black Tree)로 구현되어 있다.

 

일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸린다.

 

데이터의 값이 트리에 잘 분산되어 있다면 효율성에 큰 문제가 없으나 데이터가 들어올 때 값이 편향되게 들어올 경우 한 쪽으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 낸다.

 

이 문제를 보완하기 위해 레드 블랙 트리가 등장했다.

 

Red-Black Tree(RBT)는 이진 탐색 트리의 일종이기 때문에 작은 값은 왼쪽, 큰 값은 오른쪽으로 노드를 배치하는 규칙은 동일하지만 이 규칙을 유지하면서도, 데이터의 추가나 삭제 시 트리가 한 쪽으로 치우쳐지지 않도록 즉, 트리의 균형을 강맞추기 위한 "색상 규칙"과 "회전 연산"이 추가된것이다.