DataStructure

[5] Tree Set 의 개념과 여러 method 들의 시간 복잡도.

Mike야 2024. 12. 28. 15:17

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;
}

새로운 노드가 추가될 때:

  1. 루트부터 시작해서 비교하며 적절한 위치 탐색 O(log N)
  2. 노드 추가
  3. Red-Black Tree 특성 유지를 위한 재조정

이 과정에서 O(log N)의 시간이 소요됩니다.

3. 삭제

TreeSet에서 요소를 삭제하는 것도 이진 탐색 트리의 특성을 유지해야 합니다.

public boolean remove(Object o) {
    return m.remove(o) == PRESENT;
}

삭제 과정:

  1. 삭제할 노드 탐색 O(log N)
  2. 노드 삭제 및 트리 재구성 O(log N)
  3. 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)

주의사항

  1. 사용자 정의 객체를 TreeSet에 저장할 때는 반드시 Comparable을 구현하거나 Comparator를 제공해야 합니다.
  2. 이미 정렬된 순서로 데이터가 필요한 경우가 아니라면, HashSet을 사용하는 것이 성능상 유리할 수 있습니다.
  3. TreeSet은 이진 탐색 트리를 기반으로 하므로, 데이터의 추가/삭제가 빈번한 경우 성능 저하가 발생할 수 있습니다.

이처럼 TreeSet은 정렬이 필요한 상황에서 유용하게 사용할 수 있는 자료구조입니다. 하지만 단순히 중복을 제거하기 위한 용도라면 HashSet을, 정렬된 데이터가 필요한 경우에만 TreeSet을 선택하는 것이 좋습니다.

정리

TreeMap 은 Red-Black tree 로 구현된 이진 탐색 트리이고, Key 를 기준으로 정렬된 상태를 유지합니다. Red-Black tree 는 Tree의 균형을 맞추기 위해 노드에 색상을 부여하는 방식입니다. 지속적으로 루트 노드나 색상을 조정하여 균형을 맞춰줍니다. 따라서 조회나 삽입 삭제에 O(log N) 시간 복잡도를 보장해 줍니다. 여기서 TreeSet 은 TreeMap 으로 구현되어 있는데요. Key만 실제로 사용하고, Value 는 더미 데이터를 사용합니다.