Collection & Map - 3-2. Tree기반 Set & Map

• 이번 시리즈에서는 Java의 Collection과 Map에 대해 소개합니다.
  • 프레임워크의 기반이 되는 자료구조에 대한 개념은 따로 시리즈로 작성할 것이고, 본 시리즈에서는 Java에서 제공하는 자료구조들과 그에 따른 메서드들을 정리할 것입니다.

0. Java의 Collection Framework와 Map Interface

• Java에서는 데이터 구조와 알고리즘을 지원하는 강력한 표준 라이브러리를 제공하며, 이 중 Collection Framework와 Map은 데이터 관리와 처리의 핵심적인 역할을 합니다.

• 위 이미지는 주로 쓰이는 Collection Framework와 Map Interface의 상속 및 구현 관계를 제가 직접 그려본 것입니다.
  • 회색으로 표시된 Vector, Stack, Hashtable은 Java 초창기에 만들어져서 하위 버전 호환을 위해 남겨진 Legacy Class들입니다.
    • 구조적인 문제들이 있어서 현재는 더이상 업데이트되지 않고 거의 쓰이지 않기 때문에 본 시리즈에서도 따로 정리하진 않을 예정입니다.
  • Collection Framework
    • List 구현체 : ArrayList, LinkedList
    • Queue 구현체 : PriorityQueue, ArrayDeque, LinkedList
    • Deque 구현체 : ArrayDeque, LinkedList
    • Set 구현체 : HashSet, LinkedHashSet, TreeSet
  • Map Interface 구현체 : HashMap, LinkedHashMap, TreeMap

• 이번 포스팅에서는 Collection Framework의 하위 인터페이스인 Set 인터페이스와 Map 인터페이스에서 Tree를 기반으로 동작하는 구현체들을 자세히 다뤄보도록 하겠습니다.

1. Tree란?

• Tree는 데이터를 계층적으로 저장하는 구조로, Java의 TreeSet과 TreeMap은 레드-블랙 트리(Red-Black Tree)를 기반으로 동작합니다.
  • 레드-블랙 트리는 자가 균형 이진 탐색 트리로, 삽입, 삭제, 검색 시 균형을 유지하면서 O(log n) 시간 복잡도를 거의 일정하게 유지하도록 조정합니다.
    • 레드-블랙 트리에 관해선 추후에 자료구조를 정리할때 자세히 다룰 예정입니다.
  • 이러한 구조 덕분에 데이터가 자동으로 정렬된 상태로 저장됩니다.
    • 동적 정렬이 필요하거나 중간 값 탐색이 빈번하게 발생하는 경우, TreeSet과 TreeMap은 매우 효율적입니다. 특히 범위 검색, 최소/최대 값 탐색이 중요한 경우 유리합니다.

트리 기반 자료구조의 특징

• 정렬된 데이터 저장: Tree 기반 자료구조는 데이터를 정렬된 순서로 저장하며, 기본적으로 오름차순 정렬을 제공합니다.
  • Comparator 인터페이스를 사용하여 사용자 정의 정렬 기준을 설정할 수도 있습니다.
• 빠른 범위 검색: Tree 구조는 특정 값이 아닌, 범위 내에서의 검색이나 최소값/최대값 탐색에 매우 유리합니다.
  • 예를 들어, TreeSet은 주어진 범위 내에서 값을 검색할 수 있고, TreeMap은 특정 Key 범위의 Entry를 빠르게 조회할 수 있습니다.

2. Tree 기반 Set & Map의 공통적인 동작 원리

• 레드-블랙 트리 구조는 삽입, 삭제 시 트리의 균형을 맞추기 위한 추가적인 작업을 수행하지만, 이러한 작업을 통해 검색 및 범위 탐색에 효율적인 성능을 유지합니다.
  • 삽입, 삭제, 검색의 시간 복잡도는 O(log n)입니다.
  • 이는 트리의 높이에 비례하며, 레드-블랙 트리는 트리의 높이를 균형 있게 유지하기 때문에 최적의 성능을 제공합니다.
• 정렬된 데이터 저장: TreeSet과 TreeMap은 삽입과 동시에 데이터를 정렬된 상태로 저장합니다.
  • 이는 해시 기반 자료구조와 달리 데이터의 순서가 중요할 때 매우 유용합니다.
• 중복 허용 안 함: Tree 기반 자료구조는 중복된 값을 허용하지 않습니다.
  • TreeSet은 중복된 요소를 저장하지 않으며, TreeMap은 동일한 Key를 중복해서 저장할 수 없습니다. 만약 중복된 Key로 데이터를 삽입하면 기존 값이 덮어쓰여집니다.

3. TreeSet & TreeMap

3.1. TreeSet

• 기본 원리: TreeSet은 이진 탐색 트리 구조를 사용해 중복되지 않는 요소들을 정렬된 순서로 저장하는 Set 구현체입니다.
  • 정렬: 요소들은 기본적으로 오름차순으로 정렬되며, Comparator를 통해 사용자 정의 기준으로 정렬할 수 있습니다.
    • 예시: TreeSet<Integer> set = new TreeSet<>(Comparator.reverseOrder());는 내림차순 정렬을 적용한 예입니다.
• 중복 허용 안 함: 중복된 값을 허용하지 않습니다. 삽입 시 이미 존재하는 값이 있으면 새로운 값은 삽입되지 않습니다.
• 범위 검색: TreeSet은 범위 내에서의 요소를 탐색하는 데 유리합니다.
  • 예시: headSet(), tailSet(), subSet() 등의 메서드를 통해 특정 범위 내의 요소들을 검색할 수 있습니다.

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(10);
        set.add(5);
        set.add(20);
        set.add(1);
        
        System.out.println(set);  // [1, 5, 10, 20] (오름차순 정렬)
        
        System.out.println(set.subSet(5, 20));  // [5, 10] (범위 검색)
    }
}

3.2. TreeMap

• 기본 원리: TreeMap은 이진 탐색 트리 구조를 사용해 Key-Value 쌍을 정렬된 순서로 저장하는 Map 구현체입니다.
  • 정렬: TreeMap은 Key를 기준으로 오름차순 정렬되며, Comparator를 사용해 사용자 정의 기준으로 정렬할 수 있습니다.
• 중복된 Key 허용 안 함: 중복된 Key는 허용되지 않으며, 동일한 Key를 삽입하면 기존 값이 덮어씌워집니다.
• 범위 검색: TreeMap은 Key 범위 내에서 데이터를 검색하는 데 유리합니다.
  • 예시: headMap(), tailMap(), subMap() 등의 메서드를 사용해 특정 범위의 데이터를 빠르게 검색할 수 있습니다.
  • TreeMap은 NavigableMap 인터페이스를 구현하여, 기본적인 Map 기능 외에도 범위 검색, 최대/최소 값 탐색 등의 기능을 추가로 제공합니다.

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);
        
        System.out.println(map);  // {apple=1, banana=2, cherry=3} (Key 정렬)
        
        System.out.println(map.subMap("apple", "cherry"));  // {apple=1, banana=2} (범위 검색)
    }
}

4. TreeSet & TreeMap의 고유 메서드

• Tree 기반 자료구조인 TreeSet과 TreeMap은 기본적으로 이진 탐색 트리를 사용하여 데이터를 정렬된 상태로 저장하고 관리합니다.
  • 이를 바탕으로 여러 유용한 메서드를 제공하며, 특히 범위 검색, 최소값/최대값 탐색 등이 매우 효율적으로 수행됩니다.
• 이러한 고유 메서드들은 기본적인 Set과 Map 인터페이스와 더불어서 SortedSet, SortedMap, NavigableSet, NavigableMap의 인터페이스들을 추가적으로 구현한 것들입니다.

4.1. TreeSet의 고유 메서드

메서드명	설명	반환 값
first()	Set에서 가장 작은 요소(첫 번째 요소)를 반환	가장 작은 요소
last()	Set에서 가장 큰 요소(마지막 요소)를 반환	가장 큰 요소
ceiling(E e)	주어진 요소 e보다 크거나 같은 최소 요소를 반환. 없으면 null	주어진 요소보다 크거나 같은 최소 요소
floor(E e)	주어진 요소 e보다 작거나 같은 최대 요소를 반환. 없으면 null	주어진 요소보다 작거나 같은 최대 요소
higher(E e)	주어진 요소 e보다 큰 요소 중 가장 작은 요소를 반환	주어진 요소보다 큰 최소 요소
lower(E e)	주어진 요소 e보다 작은 요소 중 가장 큰 요소를 반환	주어진 요소보다 작은 최대 요소
pollFirst()	Set에서 첫 번째 요소(가장 작은 요소)를 반환하고, 해당 요소를 Set에서 제거	제거된 첫 번째 요소
pollLast()	Set에서 마지막 요소(가장 큰 요소)를 반환하고, 해당 요소를 Set에서 제거	제거된 마지막 요소
subSet(E fromElement, E toElement)	fromElement(포함)부터 toElement(포함하지 않음)까지의 범위에 있는 요소들을 반환	지정된 범위의 요소들
headSet(E toElement)	toElement(포함하지 않음)까지의 요소를 반환	지정된 범위의 요소들
tailSet(E fromElement)	fromElement(포함)부터 끝까지의 요소를 반환	지정된 범위의 요소들

4.2. TreeMap의 고유 메서드

메서드명	설명	반환 값
firstKey()	Map에서 가장 작은 Key를 반환	가장 작은 Key
lastKey()	Map에서 가장 큰 Key를 반환	가장 큰 Key
ceilingKey(K key)	주어진 Key보다 크거나 같은 최소 Key를 반환. 없으면 null	주어진 Key보다 크거나 같은 최소 Key
floorKey(K key)	주어진 Key보다 작거나 같은 최대 Key를 반환. 없으면 null	주어진 Key보다 작거나 같은 최대 Key
higherKey(K key)	주어진 Key보다 큰 Key 중 가장 작은 Key를 반환	주어진 Key보다 큰 최소 Key
lowerKey(K key)	주어진 Key보다 작은 Key 중 가장 큰 Key를 반환	주어진 Key보다 작은 최대 Key
pollFirstEntry()	Map에서 첫 번째 Entry(Key-Value 쌍)를 반환하고, 해당 Entry를 Map에서 제거	제거된 첫 번째 Entry
pollLastEntry()	Map에서 마지막 Entry(Key-Value 쌍)를 반환하고, 해당 Entry를 Map에서 제거	제거된 마지막 Entry
subMap(K fromKey, K toKey)	fromKey(포함)부터 toKey(포함하지 않음)까지의 Key 범위 내의 Entry들을 반환	지정된 범위의 Entry들
headMap(K toKey)	toKey(포함하지 않음)까지의 Key 범위 내의 Entry들을 반환	지정된 범위의 Entry들
tailMap(K fromKey)	fromKey(포함)부터 끝까지의 Key 범위 내의 Entry들을 반환	지정된 범위의 Entry들

5. Tree 기반 Set & Map 활용 팁

5.1. 언제 TreeSet과 TreeMap을 사용해야 할까?

• 정렬된 데이터가 필요할 때: Tree 기반 자료구조는 데이터를 삽입과 동시에 정렬된 상태로 유지하므로, 순차적으로 데이터를 다루거나 특정 범위의 데이터를 효율적으로 검색해야 하는 상황에서 유리합니다.
• 범위 검색이 필요한 경우: TreeSet과 TreeMap은 범위 검색을 위한 메서드를 제공하므로, 주어진 범위 내에서 데이터를 탐색해야 하는 경우 적합합니다.

• 반면, 단순히 빠른 검색/삽입/삭제가 중요한 경우 해시 기반 자료구조인 HashSet과 HashMap이 더 나은 성능을 제공합니다.

5.2. Tree 기반 자료구조의 장단점

장점

• 정렬된 데이터: TreeSet과 TreeMap은 삽입과 동시에 항상 데이터를 정렬된 상태로 저장하므로, 정렬이 필요한 경우 매우 효율적입니다.
• 범위 검색에 유리: subSet(), subMap() 등의 메서드를 사용하여 범위 검색 및 최소/최대 값 탐색을 효율적으로 수행

단점

• 해시 기반보다 느린 삽입/삭제: Tree 기반 자료구조는 삽입, 삭제 시 O(log n)의 시간 복잡도를 가지므로, 해시 기반 자료구조(HashSet, HashMap)에 비해 삽입/삭제가 상대적으로 느립니다.
• 추가 메모리 사용: 트리 구조를 유지하기 위한 추가적인 메모리가 필요합니다.
• 추가적인 오버헤드: 트리의 균형을 유지하는 데 따른 추가적인 오버헤드가 있으며, 특히 작은 데이터셋에서는 HashSet이나 HashMap과 같은 해시 기반 자료구조보다 성능이 낮을 수 있습니다.

마무리

• 이번 포스팅에서는 Tree 기반 자료구조의 핵심적인 특징인 정렬된 데이터 저장과 효율적인 범위 검색에 대해 살펴보았고, 이를 구현한 TreeSet과 TreeMap의 다양한 고유 메서드와 활용 팁을 정리했습니다.
• TreeSet과 TreeMap은 각각 SortedSet, NavigableSet, SortedMap, NavigableMap 인터페이스를 추가적으로 구현하며, 기본적인 삽입/삭제/검색 이외에도 범위 검색이나 최소/최대 값 탐색과 같은 다양한 기능을 제공합니다.
  • 이러한 점은 해시 기반 자료구조에서는 제공되지 않는 중요한 차별점입니다.
• 그러나 삽입/삭제 속도가 중요한 경우에는 HashSet이나 HashMap이 더 나은 선택이 될 수 있으므로, 자료구조를 선택할 때는 목적과 상황에 맞는 선택이 필요합니다.

Collection & Map 자료 구조 마무리

• 이로써 Java에서의 Collection과 Map 인터페이스에 대해서 거의 모든 내용들을 전반적으로 다루고 정리해 보았습니다. 이번 시리즈에서 다룬 것 외에도 더 다양한 자료구조들도 있지만, 이러한 자료구조들은 추후에 따로 정리해보도록 하겠습니다.
• 다음 포스팅에서는 이러한 Collection과 Array를 보다 편리하게 다룰 수 있게 해주는 Collections와 Arrays 클래스에 대해서 다루어 보고자 합니다.