11-39 TreeSet - 범위 탐색, 정렬

- 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리.

- 이진 트리는 모든 노드가 최대 2개(0~2)의 하위 노드를 갖음

  각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

class TreeNode {

        TreeNode left; // 왼쪽 자식노드

        Object      element; // 저장할 객체

        TreeNode right; // 오른쪽 자식노드

}

 

이진 탐색 트리(binary search tree)

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

- 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

 

TreeSet - 데이터 저장과정 boolean add(Object o) - 중복x 이기때문 equals와 hashCode 메서드 호출

* TreeSet에 7,4,9,1,5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.

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

 

 

 

TreeSet 주요 생성자와 메서드

 

생성자 또는 메서드

설 명

TreeSet() (기본 comparable)	기본 생성자 (Default constructor)
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성 (Creates a TreeSet that stores the given collection)
TreeSet(Comparator comp) (비교기준제공)	주어진 정렬 기준으로 정렬하는 TreeSet을 생성 (Creates a TreeSet that is sorted based on the given comparator)
Object first() (제일 작은거 오름차순)	정렬된 순서에서 첫 번째 객체를 반환 (Returns the first object in sorted order)
Object last() (제일 큰거 오름차순)	정렬된 순서에서 마지막 객체를 반환 (Returns the last object in sorted order)
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 toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.

 

headSet(50) -> 왼쪽 가지들을 다 출력함

 

 

◆알아두면 좋음

트리 순회 (tree traversal)

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

- 전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.