HashSet과 마찬가지로 Set인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다.
하지만 HashSet과는 달리 TreeSet은 이진 탐색 트리(BinarySearchTree)구조로 이루어져 있다.
이진 탐색 트리(BinarySearchTree)는 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조 이다.
그렇기에 HashSet보다 데이터의 추가/삭제는 시간이 더 걸리지만 검색과 정렬에는 유리하다.
레드-블랙 트리(Red-Black Tree)
TressSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리(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의 모든 값을 가진 TressSet생성
TreeSet<Integer> set4 = new TreeSet<Integer>(Arrays.asList(1,2,3)); //초기값 지정
선언시 크기를 지정할 수 없다.
TreeSet 값 추가
TreeSet<Integer> set = new TreeSet<Integer>(); //TreeSet 생성
set.add(7); //값추가
set.add(4);
set.add(9);
set.add(1);
set.add(5);
TreeSet에 값이 추가되는 과정
TreeSet 값 삭제
TreeSet<Integer> set = new TressSet<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 값 출력
TressSet<Integer> set = new TressSet<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)는 입력값보다 작은 데이터 중 최대값을 리턴한다.
