TreeSet이란?

 JDK 1.2부터 제공되고 있는 TreeSet은 HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있습니다. 하지만 HashSet과는 달리 TreeSet은 이진 탐색 트리(BinarySearchTree) 구조로 이루어져 있습니다. 이진 탐색 트리는 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조입니다. 그렇기에 HashSet보다 데이터의 추가와 삭제는 시간이 더 걸리지만 검색과 정렬에는 유리합니다. TreeSet은 데이터를 저장할 시 이진탐색트리(BinarySearchTree)의 형태로 데이터를 저장하기에 기본적으로 nature ordering를 지원하며 생성자의 매개변수로 Comparator객체를 입력하여 정렬 방법을 임의로 지정해 줄 수도 있습니다. 

 

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

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));//초기값 지정

TreeSet을 생성하기 위해서는 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 됩니다. 생성하는 명령어는 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에 값을 추가하려면 add(value) 메소드를 사용하면 됩니다. 입력되는 값이 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에 값을 삭제하려면 remove(value) 메소드를 사용하면 됩니다. 매개변수 value의 값이 존재한다면 그 값을 삭제한 후 true를 반환하고 없으면 false를 반환합니다. 모든 값을 제거하려면 clear() 메서드를 사용하면 됩니다.

 

TreeSet 크기 구하기

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

TreeSet의 크기를 구하려면 size() 메소드를 사용하면 됩니다.

 

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을 그냥 pirnt하게 되면 대괄호 []로 묶어서 전체 값이 출력됩니다. 그리고 TreeSet에는 값을 리턴하는 다양한 메서드가 있는데 first() 메서드는 최솟값, last()는 최댓값, higher(value)은 입력값보다 큰 데이터중 최솟값, lower(value)은 입력값보다 작은 데이터중 최대값을 리턴합니다. TreeSet에는 객체 전체를 대상으로 한 번씩 반복해서 가져오는 반복자(Iterator)를 제공합니다. 반복자 이터레이터는 iterator() 메서드를 호출하면 얻을 수 있습니다. iterator에서 하나의 객체를 가져올 때에는 next() 메서드를 사용합니다. next() 메서드를 사용하기 전에 먼저 가져올 객체가 있는지 hasNext() 메서드를 활용하여 먼저 확인하는 것이 좋습니다. hasNext() 메서드는 가져올 객체가 있으면 true, 없으면 false를 리턴합니다.

 

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