111. TreeSet - 패스트캠퍼스 백엔드 부트캠프 3기

1. TreeSet - 범위 탐색, 정렬

• 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리
• 이즌 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
• 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

2. 이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
• 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

3. TreeSet - 주요 생성자와 메서드

생성자 또는 메서드	설 명
TreeSet()	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬기준으로 정렬하는 TreeSet을 생성
Object first()	정렬된 순서에서 첫 번째 객체를 반환한다.
Object last()	정렬된 순서에서 마지막 객체를 반환한다.
Object ceiling(Object o)	지정된 개겣와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
Object floor(Object o)	지정된 객체와 같은 객체를 반환, 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
SortedSet subSet(Object fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다. (끝 범위인 toElement는 범위에 포함되지 않음)
SortedSet headSet(Obejct toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.

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(50));	// [10,35,45]
System.out.println("50보다 큰 값: " + set.tailSet(50));	// [50,65,80,95,100]
System.out.println("45~80사이의 값: " + set.subSet(45,80);	// [45,50,65]

 

4. 트리 순회(tree traversal)

• 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
• 전위순회
• 후위순회
• 중위순회 : 오름차순으로 정렬된다.
• 레벨순회