Java TreeSet, TreeMap, 그리고 Red-Black Tree

TreeSet

 

 - 정의

Set 인터페이스를 구현한 클래스 중 하나로 중복을 허용하지 않는 정렬된 집합

 

• Red-Black Tree 기반으로 구현
• 삽입, 삭제, 검색 연산의 시간 복잡도가 O(log n)
• 집합 내 모든 요소가 정렬된 상태로 유지
• null을 허용하지 않음

 

- 생성자

 

• TreeSet() : 빈 TreeSet 생성
• TreeSet(Collection<? extends E> c) : 컬렉션의 원소를 이용하여 TreeSet 생성
• TreeSet(Comparator<? super E> comparator) : 주어진 조건대로 정렬하는 TreeSet 생

- 메서드

 

• add(E e) : 원소 삽입
• remove(E e) : 원소 삭제
• first() : 첫 번째 원소 반환
• last() : 마지막 원소 반환
• pollFirst() : 첫번째 원소 제거 후 반환
• pollLast() : 마지막 원소 제거 후 반환
• higher(E e) : 입력받은 값 이상의 값 중 첫번째 값 반환
• lower(E e): 입력받은 값 이하의 값 중 마지막 값 반환
• subSet( E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
  : fromElement부터 toElement까지의 정렬된 set 반환, boolean으로 경계값 포함시킬지 결정

public class TreeSetExample {
    public static void main(String[] args) {
        // 1. TreeSet 생성
        TreeSet<Integer> set1 = new TreeSet<>();
        set1.add(10);
        set1.add(20);
        set1.add(30);

        System.out.println("set1: " + set1);  // [10, 20, 30]

        // 2. Comparator를 이용하여 역순으로 정렬된 TreeSet 생성
        TreeSet<Integer> set2 = new TreeSet<>(Comparator.reverseOrder());
        set2.add(10);
        set2.add(20);
        set2.add(30);

        System.out.println("set2 (reverse order): " + set2);  // [30, 20, 10]

        // 메서드 사용 예제
        set1.add(25);
        System.out.println("add(25): " + set1);  // [10, 20, 25, 30]

        set1.remove(20);
        System.out.println("remove(20): " + set1);  // [10, 25, 30]

        System.out.println("first(): " + set1.first());  // 10
        System.out.println("last(): " + set1.last());    // 30

        System.out.println("pollFirst(): " + set1.pollFirst());  // 10 (제거 후 반환)
        System.out.println("after pollFirst(): " + set1);        // [25, 30]

        System.out.println("pollLast(): " + set1.pollLast());    // 30 (제거 후 반환)
        System.out.println("after pollLast(): " + set1);         // [25]

        set1.add(15);
        set1.add(40);
        System.out.println("set1: " + set1);  // [15, 25, 40]
        System.out.println("higher(20): " + set1.higher(20));   // 25 (20 이상 값 중 첫 번째)
        System.out.println("lower(30): " + set1.lower(30));     // 25 (30 이하 값 중 마지막)

        TreeSet<Integer> subset = (TreeSet<Integer>) set1.subSet(15, true, 40, false);
        System.out.println("subSet(15, true, 40, false): " + subset);  // [15, 25]
    }
}

 

 

TreeMap

 

 - 정의

Map 인터페이스를 구현한 클래스 중 하나로 키와 값의 쌍을 저장하며 키를 기준으로 정렬된 상태를 유지하는 맵

 

• Red-Black Tree 기반으로 구현
• 삽입, 삭제, 검색 연산의 시간 복잡도가 O(log n)
• 키가 정렬된 상태로 유지
• 키에 null을 허용하지 않

- 생성자

• TreeMap() : 빈 TreeMap 생성.
• TreeMap(Comparator<? super K> comparator) : 주어진 조건대로 키를 정렬하는 TreeMap 생성
• TreeMap(Map<? extends K, ? extends V> m) : 다른 Map의 모든 엔트리를 포함하는 TreeMap 생성

- 메서드

• put(K key, V value) : 주어진 키와 값을 TreeMap에 삽입
• remove(Object key) : 주어진 키에 해당하는 엔트리 제거
• firstEntry() : 첫 번째 엔트리 반환
• lastEntry() : 마지막 엔트 반환
• pollFirstEntry() : 첫 번째 엔트리를 제거하고 반환
• pollLastEntry() : 마지막 엔트리를 제거하고 반환
• higherEntry(K key) : 주어진 키보다 큰 첫 번째 키의 엔트리 반환
• lowerEntry(K key) : 주어진 키보다 작은 마지막 키의 엔트리 반환
• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
  : 주어진 범위에 해당하는 부분 맵 반환, boolean 값을 통해 경계값을 포함할지 여부를 결정

public class TreeMapExample {
    public static void main(String[] args) {
        // 1. TreeMap 생성
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("apple", 3);
        map.put("banana", 5);
        map.put("cherry", 2);
        map.put("date", 4);

        System.out.println("map: " + map);  // {apple=3, banana=5, cherry=2, date=4}

        // 2. 첫 번째 엔트리 반환
        Map.Entry<String, Integer> firstEntry = map.firstEntry();
        System.out.println("firstEntry(): " + firstEntry);  // apple=3

        // 3. 마지막 엔트리 반환
        Map.Entry<String, Integer> lastEntry = map.lastEntry();
        System.out.println("lastEntry(): " + lastEntry);  // date=4

        // 4. 첫 번째 엔트리를 제거하고 반환
        Map.Entry<String, Integer> pollFirst = map.pollFirstEntry();
        System.out.println("pollFirstEntry(): " + pollFirst);  // apple=3
        System.out.println("after pollFirstEntry(): " + map);  // {banana=5, cherry=2, date=4}

        // 5. 마지막 엔트리를 제거하고 반환
        Map.Entry<String, Integer> pollLast = map.pollLastEntry();
        System.out.println("pollLastEntry(): " + pollLast);  // date=4
        System.out.println("after pollLastEntry(): " + map);  // {banana=5, cherry=2}

        // 6. 주어진 키보다 큰 첫 번째 키의 엔트리 반환
        Map.Entry<String, Integer> higherEntry = map.higherEntry("banana");
        System.out.println("higherEntry('banana'): " + higherEntry);  // cherry=2

        // 7. 주어진 키보다 작은 마지막 키의 엔트리 반환
        Map.Entry<String, Integer> lowerEntry = map.lowerEntry("cherry");
        System.out.println("lowerEntry('cherry'): " + lowerEntry);  // banana=5

        // 8. 특정 범위의 부분 맵 반환 (경계값 포함 여부 설정 가능)
        Map<String, Integer> subMap = map.subMap("banana", true, "cherry", true);
        System.out.println("subMap('banana', true, 'cherry', true):

 

Red-Black Tree

 

이진 탐색 트리의 일종으로 , 자체 균형을 유지하는 트리

 

- 특징

 

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

이진 탐색 트리는 한쪽으로 치우쳐진 경우 삽입, 삭제, 검색 등의 연산이 최악의 경우 O(N)의 시간 복잡도를 갖지만 Red-Black Tree는 균형을 유지하기에 최악의 경우에도 O(logN)의 시간 복잡도를 갖게 됩니다.

 

일반적인 이진 탐색 트리는 1 - 2 - 3 - 4 - 5 이렇게 1자 형태의 트리로 구성될 수도 있습니다.

Red-Black Tree에 실제로 1부터 5까지 어떻게 삽입 되는지 확인해봅시다.

기본적으로 끝에 레드 노드로 값이 작으면 왼쪽, 크면 오른쪽으로 삽입하되 특징을 지키지 못한다면 재조정 과정(색 전환, 회전)을 거칩니다.

 

• N이 루트 : 블랙으로 색 전환
• N의 부모가 레드
  • N의 삼촌이 레드 : 부모와 삼촌을 블랙으로 바꾸고 조부모를 레드로 변경(조부모가 조건을 만족하는지 재확인)
  • N의 삼촌이 블랙(혹은 Null)
    • N이 안쪽 자손(부모가 왼쪽 자식(오른쪽 자식)이면서 N은 오른쪽 자식(왼쪽 자식))
      : 부모 기준 왼쪽(오른쪽)으로 회전
    • N이 바깥쪽 자손(부모가 왼쪽 자식(오른쪽 자식)이면서 N은 왼쪽 자식(오른쪽 자식))
      : N의 부모를 블랙, 조부모를 레드로 전화하고 오른쪽(왼쪽) 회전

 

- 예시 : 1부터 5까지 삽입

1. 1 삽입

 

 

루트이므로 블랙으로 전환

 

2. 2 삽입

 

조건 만족

 

3. 3 삽입

 

 

레드가 연속되므로 조건 불만족

N의 부모가 레드고 삼촌이 블랙(Null), N이 바깥쪽(오른쪽) 자식이므로 N의 부모를 블랙, 조부모를 레드로 칠하고 왼쪽으로 회전

 

 

4. 4 삽입

 

레드가 연속되므로 조건 불만족

N의 부모가 레드, 삼촌이 레드이므로 부모와 삼촌을 블랙으로 변경하고 조부모를 레드로 변경

조부모는 루트이므로 다시 블랙으로 변경

 

 

5. 5 삽입

 

 

레드가 연속되므로 조건 불만족

N의 부모가 레드고 삼촌이 블랙(Null), N이 바깥쪽(오른쪽) 자식이므로 N의 부모를 블랙, 조부모를 레드로 칠하고 왼쪽으로 회전