TreeSet

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

하지만 HashSet과는 다르게 TreeSet은 이진 탐색 트리(BST)구조로 이루어져있다. BST는 추가, 삭제에는 시간이 좀 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조이다.

 

레드-블랙 트리(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));//초기값 지정

TreeSet을 생성하기 위해서는 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출한다. 선언 시 크기 지정은 불가하다. 

 

TreeSet 값 추가

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

입력되는 값이 TreeSet 내부에 존재하지 않는다면 그 값 추가하고 true 반환하고, 존재하면 false 반환한다. 

 

TreeSet에 값이 추가되는 과정

7, 4, 9, 2, 5를 차례로 TreeSet에 저장하는 과정이다.

 

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 하면 대괄호로 묶여서 전체 값 출력된다.