TreeSet 범위 탐색, 정렬

---

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

이진 트리 (binary tree)

class TreeNode {
		TreeNode left; // 왼쪽 자식 노드
		Object element; // 저장할 객체
		TreeNode right; // 오른쪽 자식 노드
}

이진 탐색 트리 (binary search tree)

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

class TreeNode {
		TreeNode left;
		Object element;
		TreeNode right;
}

TreeSet 데이터 저장 과정

boolean add(Object o)

• 루트부터 트리를 따라 내려가며 값을 비교, 작으면 왼쪽 크면 오른쪽 저장

TreeSet 생성자와 메서드

• Collection 인터페이스가 가지고 있는 중복되는 메서드는 잠시 빼고 작성함

생성자 또는 메서드	설명
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(Object fromElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.

트리 순회 (tree traversal)

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