[Java] TreeSet 구현

출처

ChatGPT

Java 1.8 소스 코드

---

자바의 TreeSet은 java.util 패키지에 포함된 정렬된 집합을 구현한 클래스이다. TreeSet은 이진 탐색 트리의 일종인 레드-블랙 트리(Red-Black Tree) 구조로 구현되어 있으며, 요소를 저장할 때 자동으로 정렬해준다. 이 때문에 TreeSet은 중복을 허용하지 않으면서, 항상 정렬된 순서로 요소를 유지한다.

• 관련 글 -> [자료 구조] 이진 탐색 트리 Binary search Tree, BST
• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

TreeSet의 주요 특성

1. 정렬된 순서

TreeSet은 내부적으로 요소들을 정렬된 순서대로 저장한다. 요소는 삽입될 때 이미 정렬된 상태로 배치되며, 검색, 탐색, 범위 검색 등에서 효율적으로 작동한다.

2. 중복 허용 안함

TreeSet은 중복 요소를 허용하지 않는다. 만약 이미 존재하는 요소를 추가하려고 하면, 기존 요소가 유지되고 새로 추가되지 않는다.

3. 성능

TreeSet에서 추가, 삭제, 검색의 성능은 모두 O(log n)의 시간 복잡도를 가진다. 이는 HashSet의 상수 시간 복잡도(O(1))보다는 느리지만, 데이터가 정렬된 상태로 유지되는 장점이 있다.

 

2. TreeSet의 내부 구현

1. TreeSet의 기본 구조

TreeSet은 내부적으로 NavigableMap 인터페이스를 구현한 TreeMap을 사용해 데이터를 관리한다. TreeMap이 데이터를 레드-블랙 트리로 관리하기 때문에, TreeSet도 동일한 방식을 사용해 데이터를 정렬하고, 검색 성능을 유지한다.

• 레드-블랙 트리는 스스로 균형을 유지하는 이진 탐색 트리이다. 삽입 또는 삭제 작업이 발생할 때, 트리의 균형을 맞추는 추가 작업이 발생하지만, 이로 인해 O(log n)의 성능을 보장할 수 있다.

 

TreeSet 클래스의 선언

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    // 실제 데이터를 저장하는 TreeMap
    private transient NavigableMap<E,Object> m;

    // TreeMap의 값으로 사용되는 상수. TreeSet은 오직 키만 중요하므로 모든 값은 동일한 상수로 설정됩니다.
    private static final Object PRESENT = new Object();

    // 기본 생성자 (자연 정렬)
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    // Comparator를 받는 생성자
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    // 내부적으로 TreeMap을 사용하는 생성자
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    // 기타 코드 생략...
}

 

• 위 코드에서 TreeSet은 NavigableMap<E, Object> 타입의 TreeMap을 통해 데이터를 관리한다. PRESENT라는 상수는 TreeMap에서 값으로 사용된다. 왜냐하면 TreeSet은 키만 중요하고 값은 의미가 없기 때문이다.

2. TreeSet의 add 메소드

TreeSet의 add 메소드는 내부적으로 TreeMap의 put 메소드를 사용해 요소를 추가한다. TreeMap에서 중복된 키를 허용하지 않기 때문에, 중복된 요소는 자동으로 거부된다.

 

add 메소드 구현

public boolean add(E e) {
    // TreeMap의 put 메서드를 호출하여 요소를 추가
    return m.put(e, PRESENT) == null;
}

 

• m.put(e, PRESENT)는 TreeMap에 새로운 키 e를 추가하고, 값은 PRESENT 상수로 저장된다.
• 만약 추가하려는 키 e가 이미 존재하면 put 메소드는 기존 값을 반환하며, 새로 추가되지 않는다.
• == null 조건은 put 메소드가 null을 반환했는지 확인해, 새로 요소가 추가되었는지 여부를 반환한다.

3. TreeSet의 remove 메소드

TreeSet의 remove 메소드도 내부적으로 TreeMap의 remove 메소드를 사용한다. TreeMap에서 해당 키를 찾아 제거한다.

 

remove 메소드 구현

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

 

• m.remove(o)는 TreeMap에서 해당 키를 찾아서 제거하고, 삭제된 값(즉, PRESNET 상수)을 반환한다.
• 반화된 값이 PRESENT와 같으면, 해당 요소가 존재했고 삭제되었음을 의미하므로 true를 반환한다.

4. 정렬 및 탐색 관련 메소드

TreeSet은 요소들이 항상 정렬된 상태로 저장된다. 이를 위해 내부적으로 TreeMap의 정렬된 트리 구조를 활용한다. 이 구조 덕분에 다양한 탐색 메소드가 가능하다.

 

first, last, higher, lower 메소드

public E first() {
    return m.firstKey();
}

public E last() {
    return m.lastKey();
}

public E higher(E e) {
    return m.higherKey(e);
}

public E lower(E e) {
    return m.lowerKey(e);
}

 

• first()와 last() : 트리에서 가장 작은(첫 번째) 키와 가장 큰(마지막) 키를 반환한다. 이들은 트리의 좌측 끝과 우측 끝에 위치한 요소이다.
• higher(E e)와 lower(E e): 주어진 키 e보다 큰 첫 번째 요소와 작은 첫 번째 요소를 반환한다. 이는 트리에서 노드를 탐색하여 순서에 맞는 다음 또는 이전 노드를 찾는다.

5. 내부적으로 사용하는 TreeMap의 동작 원리

TreeSet이 사용하는 TreeMap은 레드-블랙 트리로 구현되어 있다. 레드-블랙 트리는 이진 탐색 트리의 일정으로 삽입, 삭제, 탐색 작업을 효율적으로 수행하며 항상 O(log n)의 성능을 보장한다.

 

TreeMap의 일부 구현

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }

    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // comparable key
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }

    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

 

• 삽입 과정 : put 메소드는 새로운 요소를 삽입할 때 트리의 루트에서 시작해 비교를 통해 왼쪽 또는 오른쪽 서브트리로 내려간다. 적절한 위치를 찾으면 새로운 노드를 삽입한다.
• 균형 유지 : fixAfterInsertion 메소드는 레드-블랙 트리의 규칙에 따라 트리의 균형을 맞추기 위해 사용된다. 이 규칙을 적용함으로써 트리는 항상 균형을 유지하며, 삽입, 삭제 등의 작업이 O(log n)의 시간 복잡도로 처리된다.

 

3. TreeSet의 동작 방식

1. 요소 추가 (add 메소드)

TreeSet에 요소를 추가하면, 내부적으로 TreeMap의 put 메서드를 통해 요소가 추가된다. 이때, 요소가 정렬 기준에 따라 적절한 위치에 삽입된다.

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(10);
treeSet.add(20);
treeSet.add(15);  // 자동으로 정렬되어 [10, 15, 20] 순서로 저장됨

 

2. 요소 제거 (remove 메소드)

TreeSet에서 특정 요소를 제거하면, 내부적으로 TreeMap에서 해당 요소를 삭제해, 트리의 균형을 유지한다.

treeSet.remove(15);  // 요소 15가 삭제되고, 트리는 다시 정렬된 상태를 유지함

 

3. 정렬 기준

TreeSet은 기본적으로 요소들의 자연 순서(Natural Ordering)에 따라 정렬된다. 즉, 요소들이 Comparable 인터페이스를 구현하고 있을 경우, 이를 사용해 정렬된다. 예를 들어, Integer나 String과 같은 클래스는 이미 Comparable 인터페이스를 구현하고 있어 기본적으로 오름차순으로 정렬된다.

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("Banana");
treeSet.add("Apple");
treeSet.add("Cherry");

// 출력 결과: [Apple, Banana, Cherry]
System.out.println(treeSet);

 

4. 사용자 정의 정렬 기준

TreeSet은 사용자 정의 Comparator를 사용해 정렬 기준을 변경할 수 있다. TreeSet의 생성자에서 Comparator를 전달하며, 해당 비교 기준에 따라 요소가 정렬된다.

Comparator<String> reverseOrder = Comparator.reverseOrder();
TreeSet<String> treeSet = new TreeSet<>(reverseOrder);
treeSet.add("Banana");
treeSet.add("Apple");
treeSet.add("Cherry");

// 출력 결과: [Cherry, Banana, Apple] (내림차순 정렬)
System.out.println(treeSet);

 

4. TreeSet의 메소드

• add(E e) : 주어진 요소를 추가하고, 정렬된 상태로 유지한다.
• remove(Object o) : 지정된 객체를 제거한다.
• first() : 집합에서 가장 작은(첫 번째) 요소를 반환한다.
• last() : 집합에서 가장 큰(마지막)요소를 반환한다.
• higher(E e) : 주어진 요소보다 큰 첫 번째 요소를 반환한다.
• lower(E e) : 주어진 요소보다 작은 첫 번째 요소를 반환한다.
• subSet(E fromElement, E toElement) : 주어진 범위 내의 요소들을 반환한다.

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);

// 범위 검색
SortedSet<Integer> subset = treeSet.subSet(2, 5);  // [2, 3, 4]
System.out.println(subset);

// 가장 작은 요소
System.out.println(treeSet.first());  // 1

// 가장 큰 요소
System.out.println(treeSet.last());   // 5

 

5. TreeSet의 장단점

장점

1. 정렬된 데이터 유지

TreeSet은 항상 정렬된 상태로 데이터를 유지한다. 따라서 정렬된 데이터가 필요한 경우 매우 유용하다.

2. 범위 검색 및 탐색

subSet, headSet, tailSet 등의 메서드를 통해 특정 범위 내의 요소를 쉽게 검색할 수 있다.

3. 중복 허용 안 함

중복된 요소는 저장되지 않으며, 이를 통해 집합의 특성을 유지할 수 있다.

단점

1. 느린 삽입 및 삭제

TreeSet은 HashSet과 달리 삽입과 삭제 작업에서 O(log n)의 시간이 걸린다. 이는 HashSet의 O(1)에 비해 느리므로, 정렬이 필요하지 않다면 HashSet이 더 효율적일 수 있다.

2. 메모리 사용량

TreeSet은 내부적으로 레드-블랙 트리를 유지하기 때문에, HashSet보다 메모리 사용량이 더 많을 수 있다.

 

6. 결론

TreeSet은 요소를 자동으로 정렬된 상태로 유지하면서 중복을 허용하지 않는 자바의 중요한 자료 구조이다. 내부적으로 레드-블랙 트리를 사용해 효율적으로 삽입, 삭제, 탐색을 수행한다. TreeSet은 데이터의 정렬이 필요하거나 범위 검색과 같은 작업이 필욯나 경우에 적합하다. 그러나 단순히 삽입과 삭제가 빠른 집합이 필요하다면 HashSet이 더 나은 선택일 수 있다.