[Java] TreeSet

TreeSet이란?

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

하지만 HashSet과는 달리 TreeSet은 이진 탐색 트리(BinarySearchTree)구조로 이루어져 있다.

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

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

---

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

출처 : https://coding-factory.tistory.com/555

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

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

데이터의 값이 트리에 잘 분산되어 있다면 효율성에 큰 문제가 없으나 데이터가 들어올 때 값이 편향되게 들어올 경우

한 쪽으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 낸다.

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

레드 블랙 트리는 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여

데이터의 추가나 삭제 시 트리가 한 쪽으로 치우쳐지지 않도록 균형을 맞추어준다.

---

TreeSet 사용법

TreeSet 선언

TreeSet<Integer> set1 = new TreeSet<Integer>();//TreeSet생성

TreeSet<Integer> set2 = new TreeSet<>();//new에서 타입 파라미터 생략가능

TreeSet<Integer> set3 = new TreeSet<Integer>(set1);//set1의 모든 값을 가진 TreeSet생성

TreeSet<Integer> set4 = new TreeSet<Integer>(Arrays.asList(1,2,3));//초기값 지정

HashSet과 크게 다르지 않으나 선언 시 크기를 지정할 수 없다.

---

TreeSet 값 추가

TreeSet<Integer> set = new TreeSet<Integer>();//TreeSet생성
set.add(7); //값추가
set.add(4);
set.add(9);
set.add(1);
set.add(5);

TreeSet에 값이 추가되는 과정

출처 : https://coding-factory.tistory.com/555

---

TreeSet 값 삭제

TreeSet<Integer> set = new TreeSet<Integer>();//TreeSet생성
set.remove(1);//값 1 제거
set.clear();//모든 값 제거

---

TreeSet 크기 구하기

TreeSet<Integer> set = new TreeSet<Integer>(Arrays.asList(1,2,3));//초기값 지정
System.out.println(set.size());//크기 : 3

---

TreeSet 값 출력

TreeSet<Integer> set = new TreeSet<Integer>(Arrays.asList(4,2,3));//초기값 지정
System.out.println(set); //전체출력 [2,3,4]

System.out.println(set.first());//최소값 출력

System.out.println(set.last());//최대값 출력

System.out.println(set.higher(3));//입력값보다 큰 데이터중 최소값 출력 없으면 null

System.out.println(set.lower(3));//입력값보다 작은 데이터중 최대값 출력 없으면 null
		
Iterator iter = set.iterator();	// Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
    System.out.println(iter.next());
}

TreeSet을 그냥 print하면 대괄호 [ ]로 묶여서 전체 값이 출력된다.

TreeSet에는 값을 리턴하는 다양한 메소드가 있는데 first() 메소드는 최소값, last()는 최대값,
higher(value)는 입력값보다 큰 데이터 중 최솟값, lower(value)는 입력값보다 작은 데이터 중 최대값을 리턴한다.

---

Reference : coding-factory.tistory.com/555