[5] Tree Set 의 개념과 여러 method 들의 시간 복잡도.
TreeSet이란?
TreeSet은 내부적으로 TreeMap을 사용하는 Set 인터페이스의 구현체입니다. 중복을 허용하지 않고, 데이터가 정렬된 상태로 저장되는 특징을 가지고 있습니다.
특징
- 데이터가 정렬된 상태로 저장됨 (오름차순)
- 중복 데이터 허용하지 않음
- Red-Black Tree 기반의 이진 탐색 트리로 구현됨
- null 값을 저장할 수 없음
시간 복잡도에서의 TreeSet
데이터의 조회, 추가, 삭제, 수정을 기준으로 살펴보겠습니다.
1. 조회
TreeSet의 데이터들은 이진 탐색 트리 구조로 저장되어 있어, 특정 데이터를 찾을 때 O(log N)의 시간이 소요됩니다. Java Collections의 contains 메서드를 보면 다음과 같습니다:
public boolean contains(Object o) {
return m.containsKey(o); // TreeMap의 containsKey 호출
}
내부적으로 TreeMap의 containsKey를 호출하며, 이는 이진 탐색을 통해 이루어집니다.
2. 추가
TreeSet에 데이터를 추가할 때는 정렬된 상태를 유지해야 하므로, 적절한 위치를 찾아 삽입해야 합니다.
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
새로운 노드가 추가될 때:
- 루트부터 시작해서 비교하며 적절한 위치 탐색 O(log N)
- 노드 추가
- Red-Black Tree 특성 유지를 위한 재조정
이 과정에서 O(log N)의 시간이 소요됩니다.
3. 삭제
TreeSet에서 요소를 삭제하는 것도 이진 탐색 트리의 특성을 유지해야 합니다.
public boolean remove(Object o) {
return m.remove(o) == PRESENT;
}
삭제 과정:
- 삭제할 노드 탐색 O(log N)
- 노드 삭제 및 트리 재구성 O(log N)
- Red-Black Tree 특성 유지를 위한 재조정
전체적으로 O(log N)의 시간 복잡도를 가집니다.
TreeSet의 주요 메서드와 시간복잡도
1. 기본 동작 메서드
메서드 | 설명 | 시간복잡도 |
---|---|---|
add(E e) |
요소 추가 | O(log n) |
remove(Object o) |
요소 제거 | O(log n) |
contains(Object o) |
요소 포함 여부 확인 | O(log n) |
size() |
크기 반환 | O(1) |
isEmpty() |
비어있는지 확인 | O(1) |
clear() |
모든 요소 제거 | O(n) |
2. 탐색 관련 메서드
2.1 순차 탐색 메서드
메서드 | 설명 | 시간복잡도 |
---|---|---|
first() |
최솟값 반환 | O(1) |
last() |
최댓값 반환 | O(1) |
pollFirst() |
최솟값 반환 후 제거 | O(log n) |
pollLast() |
최댓값 반환 후 제거 | O(log n) |
2.2 범위 탐색 메서드
메서드 | 설명 | 시간복잡도 |
---|---|---|
lower(E e) |
주어진 요소보다 작은 최대 요소 | O(log n) |
higher(E e) |
주어진 요소보다 큰 최소 요소 | O(log n) |
floor(E e) |
주어진 요소보다 작거나 같은 최대 요소 | O(log n) |
ceiling(E e) |
주어진 요소보다 크거나 같은 최소 요소 | O(log n) |
3. 부분 집합 관련 메서드
메서드 | 설명 | 시간복잡도 |
---|---|---|
subSet(E fromElement, E toElement) |
범위 내 요소들의 부분집합 반환 | O(log n) |
subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) |
포함 여부를 지정하여 부분집합 반환 | O(log n) |
headSet(E toElement) |
주어진 요소보다 작은 요소들의 부분집합 | O(log n) |
tailSet(E fromElement) |
주어진 요소보다 큰 요소들의 부분집합 | O(log n) |
주의사항
- 사용자 정의 객체를 TreeSet에 저장할 때는 반드시 Comparable을 구현하거나 Comparator를 제공해야 합니다.
- 이미 정렬된 순서로 데이터가 필요한 경우가 아니라면, HashSet을 사용하는 것이 성능상 유리할 수 있습니다.
- TreeSet은 이진 탐색 트리를 기반으로 하므로, 데이터의 추가/삭제가 빈번한 경우 성능 저하가 발생할 수 있습니다.
이처럼 TreeSet은 정렬이 필요한 상황에서 유용하게 사용할 수 있는 자료구조입니다. 하지만 단순히 중복을 제거하기 위한 용도라면 HashSet을, 정렬된 데이터가 필요한 경우에만 TreeSet을 선택하는 것이 좋습니다.
정리
TreeMap 은 Red-Black tree 로 구현된 이진 탐색 트리이고, Key 를 기준으로 정렬된 상태를 유지합니다. Red-Black tree 는 Tree의 균형을 맞추기 위해 노드에 색상을 부여하는 방식입니다. 지속적으로 루트 노드나 색상을 조정하여 균형을 맞춰줍니다. 따라서 조회나 삽입 삭제에 O(log N) 시간 복잡도를 보장해 줍니다. 여기서 TreeSet 은 TreeMap 으로 구현되어 있는데요. Key만 실제로 사용하고, Value 는 더미 데이터를 사용합니다.
