[JAVA] TreeSet과 TreeMap의 심층 이해 : 정렬의 원리와 이진 탐색 트리의 마법

TreeSet과 TreeMap

 

자바 프로그래밍을 하다 보면 데이터를 단순히 저장하는 것을 넘어, 저장과 동시에 자동으로 정렬되기를 바라는 순간이 있습니다. 이때 우리는 자바 컬렉션 프레임워크(Java Collections Framework)가 제공하는 강력한 도구인 TreeSet과 TreeMap을 떠올리게 됩니다. 오늘은 이 두 자료구조가 어떤 원리로 데이터를 정렬하는지, 그리고 실무에서 어떤 기준으로 선택해야 하는지 심도 있게 다뤄보겠습니다.

1. 데이터 정렬의 핵심: 레드-블랙 트리(Red-Black Tree)

TreeSet과 TreeMap의 가장 큰 특징은 내부적으로 레드-블랙 트리(Red-Black Tree)라는 효율적인 이진 탐색 트리 구조를 사용한다는 점입니다. 일반적인 이진 탐색 트리는 데이터가 한쪽으로 치우칠 경우 성능이 급격히 저하되지만, 레드-블랙 트리는 스스로 균형을 맞추는(Self-balancing) 알고리즘을 통해 데이터의 추가, 삭제, 검색 시 O(log N)의 일관된 성능을 보장합니다.

2. TreeSet: 중복 없는 정렬된 집합

TreeSet은 Set 인터페이스를 구현하며, 이름 그대로 데이터를 중복 없이 저장하면서 동시에 오름차순(또는 사용자 정의 순서)으로 정렬합니다. 재미있는 사실은 TreeSet 내부를 들여다보면 실제로 TreeMap을 이용하여 구현되어 있다는 점입니다. 값(Value)은 고정된 더미 객체를 사용하고, 사용자가 넣는 데이터를 키(Key)로 활용하여 정렬을 수행합니다.

주요 특징

• 자동 정렬: 객체가 추가될 때마다 정렬된 상태를 유지합니다.
• 정렬 기준: 객체에 Comparable 인터페이스가 구현되어 있거나, 생성 시 Comparator를 제공해야 합니다.
• Null 제한: 정렬을 위해 비교가 필수적이므로 null 값을 저장하려고 하면 NullPointerException이 발생합니다.

3. TreeMap: 정렬된 키 기반의 맵

TreeMap은 키-값(Key-Value) 쌍으로 데이터를 관리하며, 키(Key)를 기준으로 자동 정렬합니다. 사전순 정렬이나 특정 수치 기준의 맵을 구성할 때 탁월한 성능을 발휘합니다. 특히 '가장 큰 키', '특정 범위 내의 키 목록' 등을 추출하는 탐색 기능에 최적화되어 있습니다.

언제 사용하는가?

단순 검색 속도만 따진다면 HashMap이 O(1)로 더 빠를 수 있습니다. 하지만 범위 검색(Range Search)이나 정렬된 순서의 순회가 빈번한 업무 로직에서는 TreeMap이 압도적인 편의성을 제공합니다.

4. TreeSet vs TreeMap 비교 정리

두 자료구조의 명확한 차이점을 표를 통해 확인해 보겠습니다.

항목	TreeSet	TreeMap
구현 인터페이스	Set, NavigableSet	Map, NavigableMap
저장 구조	객체 단일 저장	키-값(Key-Value) 쌍 저장
정렬 기준	저장된 객체 자체의 비교	저장된 '키(Key)' 객체의 비교
내부 구현	내부적으로 TreeMap 사용	레드-블랙 트리(Red-Black Tree)
주요 활용	중복 제거 및 정렬된 목록 관리	키 기반 정렬 및 범위 탐색

5. 실무에서의 정렬 기준 설정 (Comparable vs Comparator)

정렬된 트리 기반 컬렉션을 사용할 때 가장 빈번하게 발생하는 실수는 정렬 기준 미지정입니다. 자바는 객체를 어떻게 비교할지 모르면 런타임에 에러를 던집니다.

1. Comparable (기본 정렬): 클래스 내부에 compareTo()를 구현하여 객체의 자연 순서(Natural Order)를 정의합니다.
2. Comparator (커스텀 정렬): 클래스 수정 없이 외부에서 compare()를 정의하여 동적으로 정렬 기준을 변경할 때 사용합니다.

---

콘텐츠 출처 및 참고 문헌

• Oracle Java SE Documentation - The Set Interface / The Map Interface
• Joshua Bloch, Effective Java 3rd Edition, Addison-Wesley
• Robert Sedgewick & Kevin Wayne, Algorithms 4th Edition (Red-Black Trees Section)