Java | Collection Framework - Set (트리 구조와 TreeSet)

TreeSet

• 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용
• 요소들은 값이 정렬된 순서로 저장되고, 기준은 Comparator(비교자)로 변경할 수 있다
• 주요 연산들은 O(log n) 의 시간 복잡도를 가진다 (HashSet 보다는 느림)
• 데이터를 정렬된 순서로 유지하면서, 집합의 특성 또한 가져야 할 때 (범위 검색 등이 필요 시)
  유용하다

트리 구조

• 부모 노드와 자식 노드로 구성된다
• 가장 높은 조상을 root(루트) 라고 한다
• 자식을 2개 까지 가질 수 있는 트리를 이진 트리라고 한다
• 왼쪽 자식은 더 작은 값을 가지고, 오른쪽 자식은 더 큰 값을 가지는 것을 이진 탐색 트리라고 한다

class Node {
	Object item;
    Node left;
    Node right;
}

이진 탐색 트리의 핵심은
입력 시점에 데이터를 정렬해서 보관한다는 것이다
작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다

이진 탐색 트리의 연산은 한 번에 절반 씩의 데이터를 날리고
남은 절반에 대해서만 연산을 지속한다는 것이다
따라서 평균 O(log n), 최악의 경우 O(n) 의 시간 복잡도를 가지고
이는 리스트보다 빠르고 해시보다는 느리다

대체로 O(log n) 이지만
트리의 균형이 깨진 경우 O(n) 까지 나올 수 있다
이 때는 트리의 균형을 동적으로 맞춘다
균형을 맞추는 알고리즘을 가진 AVL 트리, 레드-블랙 트리 등의 다양한 트리가 존재한다
자바에서는 레드-블랙 트리를 사용해 균형을 지속적으로 유지하고
따라서 최악의 경우에도 O(log n) 을 유지할 수 ㅣㅇㅆ다

이진 탐색 트리 - 순회

• 이진 탐색 트리는 입력이 아니라 데이터의 값을 기준으로 정렬해서 보관한다
• 정렬된 순서로 데이터를 순회할 수 있다

중위 순회

기준이 되는 노드로부터 모든 왼쪽 노드를 처리 후에 오른쪽 노드를 처리하는 방식
기준이 되는 노드는 중앙이기 때문에
왼쪽 - 기준 - 오른쪽 순서가 된다
이 순서는 순회 중 모든 경우에서 동일하게 진행된다

Set 인터페이스 구현체 HashSet, LinkedHashSet, TreeSet 에서
iterator() 를 호출하면 컬렉션 내부 값을 리스트처럼 하나씩 호출할 수 있다

Interator<String> iterator = set.iterator();

while(iterator.hasNext()) {
	sout(iterator.next() + " ");
}

Set 인터페이스 구현체 특징 정리

• HashSet: 입력한 순서 보장 x - O(1)
• LinkedHashSet: 입력한 순서 보장 - O(1)
• TreeSet: 데이터 값 기준 정렬 - O(log N)

TreeSet 의 정렬 기준

TreeSet 정렬 시 문자열 등 순서가 없는 데이터에 대한 정렬 기준을
Comparable, Comparator 인터페이스를 구현하여 지정할 수 있다