TreeSet 클래스

[TreeSet 클래스]

1. Set 인터페이스를 구현한 컬렉션 클래스

2. 순서를 유지하지 않고, 중복을 허용하지 않는다.

3. 범위 검색과 정렬에 유리한 컬렉션 클래스

  - 이진 탐색 트리(binary search tree)로 구현함

  - 이진 탐색 트리는 부모보다 작은 값을 왼쪽에, 큰 값은 오른쪽에 저장

4. 객체 저장시 비교를 하기 때문에 따로 정렬해줄 필요가 없다.

  - 데이터가 많아질수록 비교 횟수가 증가하기 때문에 HashSet보다 추가, 삭제에 시간이 더 걸리게 된다.

5. 링크드 리스트처럼 각 요소(node)가 나무(tree) 형태로(tree) 연결된 구조

  - 가장 상위 노드는 루트(root)라고 부름

  - 이진 트리는 모든 노드가 0~2개의 하위 노드를 가짐(부모-자식관계)

 

[TreeSet의 데이터 저장 과정]

1. add()를 사용한다.

2. 중복을 허용하지 않기 때문에 equals()와 hashCode()가 오버라이딩 되어있어야 정상 작동을 한다.

다음 그림은 TresSet에 7, 4, 5, 1, 9 순으로 저장하는 과정이다.

 

[생성자]

TreeSet()
// 기본 생성자

TreeSet(Collection c)
// c를 저장한 TreeSet 생성

TreeSet(Comparator comp)
// 주어진 정렬기준으로 정렬하는 TreeSet 생성
// 다른 생성자들처럼 정렬기준이 제공되지 않는다면 저장되는 객체의 Comparable 사용
// 객체의 Comparable이 없을 때 TreeSeet의 Comparator가 없다면 에러 발생

 

[메서드]

Object first()
// 정렬된 순서에서 첫 번째 객체 반환

Object last()
// 정렬된 순서에서 마지막 객체 반환

Object ceiling(Object o)
// o와 같은 객체를 반환. 같은 것이 없다면 o보다 큰 값 중 가장 가까운 값의 객체 반환. 없다면 null 반환

Object floor(Object o)
// o와 같은 객체를 반환. 같은 것이 없다면 o보다 작은 값 중 가장 가까운 값의 객체 반환. 없다면 null 반환

Object higher(Object o)
// o보다 큰 값 중 가장 가까운 값의 객체 반환. 없다면 null 반환

Object lower(Object o)
// o보다 작은 값 중 가장 가까운 값의 객체 반환. 없다면 null 반환

SortedSet subSet(Object fromElement, Object toElement)
// from <= x < to인 x들을 반환

SortedSet headSet(Object toElement)
// to보다 작은 값의 객체들을 반환

SortedSet tailSet(Object fromElement)
// from보다 큰 값의 객체들을 반환

// 기타 컬렉션 인터페이스에 있는 메서드
add(), size(), remove(), isEmpty(), iterator()

---

 [쿠키글] 트리 순회(tree traversal)

1. 트리 순회란 이진 트리의 모든 노드를 한 번씩 읽는 것을 말한다.

2. 노드를 읽는 순서

- 전위 순회(pre order): 부모 -> 왼쪽 자식 -> 오른쪽 자식 순으로 읽음

- 중위 순회(in order): 왼쪽 자식 -> 부모 -> 오른쪽 자식 순으로 읽음. 오름차순

- 후위 순회(post order): 왼쪽 자식 -> 오른쪽 자식 -> 부모 순으로 읽음

- 레벨 순회: 루트부터 같은 레벨 순서대로 왼쪽에서 오른쪽으로 읽음

위 그림을 읽는 방법에 따라 순회해보면 다음과 같다.

- 전위 순회: 80, {50, (35, 10, 45), 65}, (95, 100)

- 중위 순회: {(10, 35, 45), 50, 65}, 80, (95, 100)

- 후위 순회: {(10, 45, 35), 65, 50}, (100, 95), 80

- 레벨 순회: 80, 50, 95, 35, 65, 100, 10, 45