TreeSet

TreeSet - 범위 탐색, 정렬

• 이진 탐색 트리(binary search tree)로 구현, 범위 탐색과 정렬에 유리.
• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
• 최초의 요소를 Root라고 한다.
• 이진 트리란 각 노드가 부모자식 관계로 연결되어 있는걸 뜻함
• 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

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

이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장

단점

• 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)
  이유 : 트리가 커지면 커질수록 요소를 저장(삭제)할 때마다 root부터 비교를 해야하기 때문

TreeSet - 데이터 저장과정

boolean add(Object o) // 저장할 객체 o

중복을 허용하지 않기 때문에 compare()를 호출해서 비교
*HashSet은 equlas(), hashCode()로 비교

TreeSet - 주요 생성자와 메서드

Collection interface에 포함된 메서드는 제외

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)
// 범위 검색(from과 to 사이)의 결과를 반환한다. (끝 범위인 toElement는 범위에 포함되지 않음)
SortedSet headSet(Object toElement) // 지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement) // 지정된 객체보다 큰 값의 객체들을 반환한다.

• TreeSet은 비교 기준이 필요 하기 때문에 둘중 하나를 해야한다.

1. 저장하는 객체가 comparable를 갖고 있던가 (객체가 implement Comparable를 구현하던가)
2. TreeSet이 비교 기준을 가지고 있어야한다. (비교 기준이 implement Comparator를 구현하던가)

트리 순회(tree traversal)

• 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

부모를 앞으로 보내는 것을 pre order(전위순회) 라고 한다. (부모를 먼저 읽고 자식을 나중에)
부모를 나중에 읽고 자식을 먼저 읽는 것을 post order (후위순회)라고 한다
부모를 가운데 두고 왼쪽 자식(1) 부모(2) 오른쪽 자식(3) 순으로 읽는 것을 inorder(중위 순회)라고 한다.
레벨 순회는 순서대로 위에서 아래로, 왼쪽에서 오른쪽으로 순회 한다.

중위 순회하면 오름차순으로 정렬된다.

TreeSet : 정렬과 범위 검색에 유리하다, 그러나 트리가 커질 수록 추가/삭제 시간이 오래걸린다.