TreeSet

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

이진 탐색 트리(binary search tree)

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

TreeSet 생성자와 메서드

• Collection 인터페이스가 가지고 있는 메서드들은 당연히 포함된다.

• TreeSet() : 기본 생성자

• TreeSet(Collection c) : 주어진 컬렉션을 저장하는 TreeSet을 생성하는 생성자

• TreeSet(Comparator comp) : 주어진 정렬기준으로 정렬하는 TreeSet을 생성, Comparator comp가 비교기준을 제공한다. 만약 기본 생성자처럼 Comparator comp의 비교기준을 제공하지 않고 생성자를 생성한다면 저장하는 객체 클래스에서 comparable 인터페이스의 compareTo()를 구현해줘야 한다.

• Object first() : 정렬된 순서에서 첫 번째 객체를 반환하는 메서드

• Object last() : 정렬된 순서에서 마지막 객체를 반환하는 메서드

• Object ceiling(Object c) : 입력되는 객체와 같은 객체를 반환하거나 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다.

• Object floor(Object c) : 입력되는 객체와 같은 객체를 반환하거나 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다.

• Object higher(Object c) : 입력되는 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다.

• Object lower(Object c) : 입력되는 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다. 없으면 null을 반환한다.

• SortedSet subSet(Object fromElement, Object toElement) : 범위 검색 (fromElement와 toElement사이)의 결과를 반환한다. 끝 범위인 toElement는 포함하지 않고 반환한다.

• SortedSet headSet(Object toElement) : 입력되는 객체보다 작은 값의 객체를 반환한다.

• SortedSet tailSet(Object toElement) : 입력되는 객체보다 큰 값의 객체를 반환한다.

• boolean add(Object o) : add() 메서드를 호출하면 compare() 를 호출해서 중복이 있는지 비교한 후 객체를 저장한다. 저장이 성공했다면 true를 실패했다면 false를 반환, HashSet에서는 equals(), hashCode() 를 호출한다.

트리 순회 (tree travelsal)

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