TreeSet

TreeSet

TreeSet 이란?

• 자바의 SortedSet 인터페이스 중 하나

• HashSet과의 공통점과 차이점

  공통점	차이점
  - Set 인터페이스를 구현 -> 중복 데이터를 저장하지 않음 / 저장 순서를 유지하지 않음	- TreeSet : 이진 탐색 트리 구조 중에서도 성능을 향상시킨 레드-블랙 트리로 구현됨

📌 이진 탐색 트리와 레드-블랙 트리

• 이진 탐색 트리 (Binary Search Tree)
  • 아래 조건을 만족하는 이진 트리
    1. 모든 노드는 유일한 값을 가짐
    2. 루트 노드의 왼쪽 서브 트리는 루트 노드보다 작은 값을 갖는 노드들로 이루어짐
    3. 루트 노드의 오른쪽 서브 트리는 루트 노드보다 큰 값을 갖는 노드들로 이루어짐
    4. 모든 서브 트리도 모두 이진 탐색 트리
  • 추가와 삭제에는 시간이 더 걸리지만, 검색 성능이 높음
• 레드-블랙 트리
  • 부모 노드보다 작은 값을 갖는 노드는 왼쪽 자식으로, 큰 값을 갖는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한 쪽으로 치우치지 않도록 균형을 맞춤

TreeSet 사용하기

TreeSet 선언하기

import java.util.Collections;
import java.util.TreeSet;

public class TreeSetTest {
	public static void main(String[] args)  {
		TreeSet<Integer> ts = new TreeSet<>(); // 오름차순
		TreeSet<Integer> ts2 = new TreeSet<>(Collections.reverseOrder()); // 내림차순
    TreeSet<Integer> ts3 = new TreeSet<Integer>(set1);//set1의 모든 값을 가진 TreeSet생성
    TreeSet<Integer> ts4 = new TreeSet<Integer>(Arrays.asList(1,2,3));//초기값 지정
}

• 선언 시 크기는 지정할 수 없음
• 기본은 오름차순. 내림차순은 Collections.reverseOrder()

TreeSet 메소드

ts.add(5); // 값 추가

ts.remove(4); // 4를 삭제. 없으면 false
ts.pollFirst();
ts.pollLast();
ts.clear(); // 모두 삭제

ts.first(); // 첫번째 노드 peek
ts.last(); // 마지막 노드 peek

ts.size(); // 크기 구하기

• 값 출력하기

  1. 향상된 for문 사용

      for (Integer t : ts) System.out.println(t + " ");
     

  2. Iterator 이용해서 출력

      Iterator iter = ts.iterator();
      while (iter.hasNext()) System.out.priint(iter.next() + " ");
     

---

참고자료

• [JAVA] TreeSet 개념과 사용법 정리
• [Java] 자바 TreeSet 사용법 & 예제 총정리
• [자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해
• [자료구조] 레드-블랙 트리(Red-Black Tree)란?