TreeSet (2)

TreeSet - 주요 생성자와 메서드

 

이번시간에는 TreeSet에 가지고 있는 주요 생성자와 메서드에 대해서 알아보자.
기본적으로 add(), remove(),. size(), isEmpty(), iterator()같은 것들은, Collection인터페이스가 가지고 있는 메서드들인데, 이것들은 다른 클래스들에서도 살펴봤으므로 이번 시간에는 제외하였다.

TreeSet이 가지고 있는 특별한 메서드 위주로 보자.

먼저 생성자를 보자.
TreeSet(), TreeSet(Collection c), TreeSet(Comparator comp)가 있는데, 여기서 주목해야 할 것은,
TreeSet(Comparator comp)이다. Comparator가 하는 일은 비교기준제공이다.
저번 시간에 공부했던 것 처럼, TreeSet의 add()메서드는 비교후, 저장하는데, 비교할 때 비교기준을 제공하는 것이 Comparator이다.

TreeSet(Comparator comp)는 주어진 정렬기준으로 정렬하는 TreeSet을 생성한다.
기본 생성자인 TreeSet()은 따로 주어진 정렬기준은 없으므로, 저장하는 객체의 Comparable을 사용해서 기본비교기준을 이용해서 저장한다.

그리고 first()는 정렬된 순서에서 첫 번째 객체를 반환한다.
last()는 정렬된 순서에서 마지막 객체를 반환한다.

ceiling(Obejct o)는 올림이다. 지정된 객체와 같은 객체를 반환하는데, 같은게 없으면, 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다. 없으면 null을 반환한다.
floor(Object o)는 내림이다. 지정된 객체와 같은 객체를 반환하는데, 같은게 없으면, 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다.

higher(Object o)는 지정된 객체보다 큰 값을 가진 객체 중제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다.
lower(Obeject o)는 지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null을 반환한다.

subSet(Object formElement, Object toElement)는 범위 검색의 결과를 반환한다. 끝 범위인 toElement는 범위에 포함되지 않는다.

headSet(Object toElement)는 지정된 객체보다 작은 값의 객체들을 반환한다.
tailSet(Object toElement)는 지정된 객체보다 큰 값의 객체들을 반환한다.

 

---

 

TreeSet - 범위 검색 subSet(), headSet(), tailSet()

 

TreeSet은 범위검색에 유용한 메서드들을 제공한다.

 

만약에 headSet(50)을 해서 50들을 반환하려고 한다고 가정하자.
50보다 작은 값들은 50이 저장되있는 노드의 왼쪽가지 아래에 있는 것들이다.
즉, 50이라는 요소의 왼쪽 가지에 있는 것들을 전부 출력하면 headSet(50)을 얻을 수 있다.

이번에는 tailSet(50)으로 50보다 큰값들을 찾으려고 한다고 가정하자.
50보다 큰값들은 50이 저장되있는 노드의 왼쪽가지 아래의 값들을 제외한 나머지 값들이 전부 50보다 큰 값이다.
따라서 50의 왼쪽가지 아래 이외의 값들은 전부 50보다 크다.

 

---

 

트리 순회(tree traversal)

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

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

트리는 순회방법이 여러개가 있다.
그중에 하나로,
- preorder라는 전위순회가 있는데, 부모를 먼저 읽고 자식들을 읽는 방법이다.
- postorder라는 후위순회가 있는데, 이것은 부모를 나중에 읽는다.
- inorder라는 중위순회가 있는데, 왼쪽자식노드 읽은다음, 부모노드 읽은 다음, 오른쪽 자식노드 읽는 방법이다.
- level 라는 레벨순회가 있는데, 한층씩 읽는 것을 레벨순회라고 한다.

 

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

여러가지 순회법이 있는데,
그중에 중위 순회로 읽어보자.

[Step 1]

[Step 2]

[Step 3]

[Step 4]

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

그래서, TreeSet은 정렬과 범위 검색에 유리하다.
단점은, 트리가 커질 수록 추가/삭제 시간이 많이 걸린다.

 

[Ex11_13]

 

[Ex11_14]

 

[Ex11_15]