Java 컬렉션 : TreeSet
Set : TreeSet
TreeSet
은 이진 탐색 트리로 구현되어 있다. 이진 탐색 구조는 범위 탐색과 정렬에 유리한 구조이며 모든 노드가 최대 2개의 하위 노드를 갖는 특성이 있다. LinkedList
처럼 하나의 노드가 이전 노드와 다음 노드의 주소를 저장하고 있는 구조이다.
class TreeNode {
TreeNode left; // 왼쪽 자식노드
Object element; // 저장할 객체
TreeNode right; // 오른쪽 자식노드
}
이진 탐색 트리
첫 번째로 저장되는 값은 root가 되고 그 이후에 들어오는 값의 크기를 비교하며 트리 구조를 내려온다. 부모 노드보다 작은 값을 왼쪽, 큰 값을 오른쪽에 저장하게 된다. 저장할 때부터 비교를 하기 때문에 탐색과 정렬에 매우 용이하지만 데이터가 많아질 수록 추가, 삭제하는 데 시간이 더 걸리는 특징이 있다.
트리 순회
이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
- 전위 순회 : root => 왼쪽 자식 => 오른쪽 자식
- 중위 순회 : 왼쪽 자식 => root => 오른쪽 자식
- 후위 순회 : 왼쪽 자식 => 오른쪽 자식 => root
- 레벨 순회 : 노드의 순서대로
TreeSet 생성자
TreeSet()
TreeSet(Collection c) // 해당 컬렉션을 저장하는 TreeSet 생성
TreeSet(Comparator comp) // 해당 정렬기준으로 정렬하는 TreeSet 생성
TreeSet 주요 메서드
객체의 반환
Object first()
Object last()
Object ceiling(Object O)
Object floor(Object O)
Object higher(Object O)
Object lower(Object O)
first()
,last()
: 정렬된 순서에서 첫 번째, 마지막 객체를 반환한다.ceiling()
,floor()
: 지정된 객체와 같은 객체를 반환한다. 객체가 없으면 가까운 값 중ceiling()
은 큰 값을,floor()
는 작은 값을 반환한다.higher()
,lower()
: 지정된 객체에서 가장 가까운 객체의 큰 값, 작은 값을 반환한다.
객체의 정렬
SortedSet subSet(Object fromElement, Object toElement)
SortedSet headSet(Object toElement)
SortedSet tailSet(Object fromElement)
subSet()
: 매개변수로 받은 범위의 결과를 반환한다.headSet()
,tailSet()
: 지정된 객체보다 작거나 큰 객체들을 반환한다.
예제 1 - 로또번호 생성기
Set set = new TreeSet();
for (int i = 0; i < 6; i++) {
set.add((int) (Math.random() * 45) + 1);
}
System.out.println(set.toString());
// 결과
[21, 29, 31, 34, 41] // 중복값 없이 정렬된 모습
[4, 30, 31, 39, 41]
예제 2 - 범위 검색
TreeSet set = new TreeSet();
String from = "b";
String to = "d";
set.add("abc");
set.add("alien");
set.add("bat");
set.add("car");
set.add("Car");
set.add("disc");
set.add("dance");
set.add("dZZZZ");
set.add("dzzzz");
set.add("elephant");
set.add("elevator");
set.add("fan");
set.add("flower");
System.out.println(set);
System.out.println("range search : from " + from +" to "+ to);
System.out.println("result1 : " + set.subSet(from, to));
System.out.println("result2 : " + set.subSet(from, to + "zzz"));
//결과
[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from b to d
result1 : [bat, car] // d는 포함되지 않는다
result2 : [bat, car, dZZZZ, dance, disc]
예제 3 - 기준 검색
TreeSet set = new TreeSet();
int[] score = {80, 95, 50, 35, 45, 65, 10, 100}; // 정렬이 안 된 배열
for(int i=0; i < score.length; i++)
set.add(new Integer(score[i]));
System.out.println("50보다 작은 값 :" + set.headSet(new Integer(50)));
System.out.println("50보다 큰 값 :" + set.tailSet(new Integer(50)));
// 결과
50보다 작은 값 :[10, 35, 45] // 50보다 작은 값만 정렬되어 출력된다
50보다 큰 값 :[50, 65, 80, 95, 100]
Author And Source
이 문제에 관하여(Java 컬렉션 : TreeSet), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chicori3/Java-컬렉션-TreeSet저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)