1. java.util.TreeSet 개괄
- 이진 검색 트리를 기반으로 데이터를 저장하는 컬렉션 클래스
: 레드-블랙 트리로 구현- 정렬, 검색, 범위 검색에 특화됨
- 데이터 추가/삭제 시간이 느림
: 데이터 추가 시 저장 위치를 탐색하는 작업을 필요로 하고, 삭제 시에는 트리의 일부를 재구성해야 하기 때문- Set 인터페이스를 구현
: 중복된 데이터의 저장을 허용하지 않고, 저장순서도 유지하지 않음
(항상 정렬된 상태를 유지하기 때문)
연관된 인터페이스/클래스
java.util.TreeSet의 조상 인터페이스
java.util.Set인터페이스
- 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스(이하 집합 클래스)를 구현하는 데 사용되는 인터페이스
java.util.SortedSet인터페이스
- 저장된 객체들을 정렬한 집합 클래스를 다루는 데 필요한 기능들을 정의한 인터페이스
: 범위 검색 기능 정의- 이 인터페이스를 구현할 시 정렬 기준 설정 필수
: 이 인터페이스에 정의된comparator()메서드를 구현하거나,
이 클래스를 구현한 집합 클래스에 저장될 요소가Comparable인터페이스를 구현
java.util.NavigableSet인터페이스
java.util.SortedSet에 정의된 범위 검색 기능을 확장- 특정 값을 기준으로 한 탐색 기능과 역순 정렬 기능을 추가 정의
java.lang.Cloneable
- 이 인터페이스를 구현한 클래스의 인스턴스는
Object clone()메서드를 통해 복제될 수 있음
java.io.Serializable
- 이 인터페이스를 구현한 클래스의 인스턴스는 직렬화될 수 있음
cf) java.lang.Cloneable와 java.io.Serializable는 마커 인터페이스
java.util.TreeSet의 조상 클래스
java.util.AbstractSet추상 클래스
- 집합 클래스의 기본 골격을 제공하기 위한 추상 클래스
Set인터페이스에서 정의된 집합 클래스의 주요 기능을 구현
2. java.util.TreeSet의 주요 메서드
cf1) java.util.TreeSet의 모든 메서드는 여기에서 확인 가능
cf2) TreeSet의 주요 기능은 실제 저장하는 객체가 key, 더미 객체가 value인 key-value 쌍을 저장하는 NavigableMap을 사용하여 구현
(더미 객체로는 Object 타입의 객체를 사용)
TreeSet의 생성자
객체 생성 보조용 생성자
주요 생성자
TreeSet()
- 기본 생성자
- TreeMap을 사용하여 구현
TreeSet(Comparator comp)
- 주어진 정렬조건으로 정렬하는 TreeSet을 생성
TreeSet(Collection c)
- 주어진 컬렉션의 객체들을 저장하는 TreeSet을 생성
TreeSet(SortedSet s)
- 주어진 SortSet을 구현한 컬렉션을 저장하는 TreeSet을 생성
데이터 포함관계 확인
boolean contains(Object o)
- TreeSet이 지정된 객체를 포함하고 있는지를 확인
boolean containsAll(Collection c)
- 지정된 컬렉션에 저장된 모든 객체를 TreeSet이 포함하고 있는지를 확인
java.util.AbstractCollection에서 구현된 메서드를 그대로 사용
데이터 추가/삭제
객체 단위 추가/삭제
단일 객체 추가
boolean add(Object o)
- 지정한 객체를 TreeSet에 추가
단일 객체 삭제
boolean remove(Object o)
- 지정한 객체를 TreeSet에서 삭제
Object pollFirst()/Object pollLast()
- TreeSet의 첫번째/마지막 객체를 반환한 후 삭제
- TreeSet이 비어있다면 null을 반환
컬렉션 단위 데이터 추가/삭제
컬렉션 단위 데이터 추가
boolean addAll(Collection c)
- 지정한 컬렉션에 저장된 모든 객체들을 TreeSet에 추가(합집합 연산)
컬렉션 단위 데이터 삭제
boolean retainAll(Collection c)
- 주어진 컬렉션과 공통된 요소만 남기고 삭제(교집합 연산)
java.util.AbstractCollection추상 클래스에 구현된 메서드를 그대로 사용
boolean removeAll(Collection c)
- 주어진 컬렉션과 공통된 요소만 삭제(차집합 연산)
java.util.AbstractSet추상 클래스에 구현된 메서드를 그대로 사용
객체 검색
단일 객체 검색
찾는 객체와 동일한 값 탐색
Object floor(Object o)
- 지정된 객체와 같은 값을 TreeSet에서 찾아서 반환
- 찾는 객체가 없다면 TreeSet의 정렬 순서상 지정된 객체의 바로 앞에 오는 객체를 반환하고, 그래도 없다면 null을 반환
Object ceiling(Object o)
- 지정된 객체와 같은 값을 TreeSet에서 찾아서 반환
- 찾는 객체가 없다면 TreeSet의 정렬 순서상 지정된 객체의 바로 뒤에 오는 객체를 반환하고, 그래도 없다면 null을 반환
찾는 객체보다 작은 값 탐색
Object lower(Object o)
- 지정한 객체보다 작은 값을 갖는 객체 중 제일 가까운 값의 객체를 반환하고, 없다면 null을 반환
- TreeSet의 정렬 순서상 지정한 객체 바로 이전에 나열되는 객체를 탐색
찾는 객체보다 큰 값 탐색
Object higher(Object o)
- 지정한 객체보다 큰 값을 갖는 객체 중 제일 가까운 값의 객체를 반환하고, 없다면 null을 반환
- TreeSet의 정렬 순서상 지정한 객체의 바로 다음에 나열되는 객체를 탐색
최대값/최소값 탐색
Object first()/Object last()
- TreeSet의 정렬 순서상 첫번째/마지막 객체를 반환
- TreeSet이 비어 있으면
NoSuchElementException발생
범위 검색
SortedSet 인터페이스의 메서드 구현
SortedSet headSet(Object toElement)
- 지정된 객체보다 작은 값을 갖는 객체들을 반환
SortedSet tailSet(Object fromElement)
- 지정된 객체보다 큰 값을 갖는 객체들을 저장하는, TreeSet의 부분집합을 반환
SortedSet subSet(Object fromElement, Object toElement)
- fromElement와 toElement 사이의 값을 갖는 객체들을 반환
- toElement는 범위에 미포함
NavigableSet 인터페이스의 메서드 구현
NavigableSet headSet(Object toElement, boolean inclusive)
- 지정된 객체보다 작은 값을 갖는 객체들을 반환
inclusive가 true면toElement도 범위에 포함NavigableSet tailSet(Object fromElement, boolean inclusive)
- 지정된 객체보다 큰 값을 갖는 객체들을 반환
inclusive가 true면fromElement도 범위에 포함NavigableSet subSet(Object fromElement, boolean fromInclusive, Object toElement, boolean toInclusive)
fromElement와toElement사이의 값을 갖는 객체들을 반환fromInclusive가 true면 시작값을,toInclusive가 true면 끝값을 범위에 포함
Reference
- 자바의 정석 3판(남궁성 지음)
- Java 공식 문서 - TreeSet 클래스
