TreeMap과 정렬된 자료구조 — 순서가 필요할 때의 선택

HashMap은 O(1)인데 TreeMap은 O(log n)입니다. 그런데도 TreeMap을 선택해야 하는 순간이 있을까요?

TreeMap이란

TreeMap은 키를 정렬된 상태로 유지 하는 Map 구현체입니다. 내부적으로 Red-Black 트리 를 사용합니다.

JAVA

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 3);
map.put("apple", 1);
map.put("cherry", 2);

// 키가 자동으로 정렬됨
System.out.println(map); // {apple=1, banana=3, cherry=2}

왜 필요한가

HashMap은 키의 순서를 보장하지 않습니다. 다음 상황에서는 TreeMap이 필요합니다.

키 순서대로 순회 해야 할 때
범위 검색 (예: "apple"과 "cherry" 사이의 키)
** 가장 작은/큰 키** 빠르게 조회
floor/ceiling (특정 값 이하/이상의 가장 가까운 키)

Red-Black 트리 기반

TreeMap 내부는 Red-Black 트리입니다. 간략하게 살펴보면:

JAVA

// TreeMap 내부의 노드 (간략화)
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color; // RED = false, BLACK = true
}

Red-Black 트리의 규칙:

모든 노드는 빨강 또는 검정
루트는 검정
빨간 노드의 자식은 반드시 검정 (빨강이 연속 불가)
루트에서 모든 리프까지의 검정 노드 수가 동일

이 규칙들이 트리의 높이를 O(log n) 이내로 보장합니다.

시간 복잡도 비교

연산	HashMap	TreeMap
get	O(1) 평균	O(log n)
put	O(1) 평균	O(log n)
remove	O(1) 평균	O(log n)
containsKey	O(1) 평균	O(log n)
firstKey/lastKey	-	O(log n)
범위 검색	O(n)	O(log n + k)
정렬 순회	O(n log n)	O(n)

k는 결과 개수

NavigableMap 인터페이스

TreeMap이 구현하는 NavigableMap은 강력한 탐색 메서드를 제공합니다.

JAVA

TreeMap<Integer, String> scores = new TreeMap<>();
scores.put(60, "C");
scores.put(70, "B");
scores.put(80, "B+");
scores.put(90, "A");
scores.put(95, "A+");

// 가장 작은/큰 키
scores.firstKey();   // 60
scores.lastKey();    // 95

// floor: 주어진 값 이하의 가장 큰 키
scores.floorKey(85);   // 80
scores.floorKey(80);   // 80

// ceiling: 주어진 값 이상의 가장 작은 키
scores.ceilingKey(85); // 90
scores.ceilingKey(90); // 90

// lower/higher: 미만/초과
scores.lowerKey(80);   // 70 (80 미만)
scores.higherKey(80);  // 90 (80 초과)

// 범위 검색
SortedMap<Integer, String> range = scores.subMap(70, 90);
// {70=B, 80=B+} (70 이상 90 미만)

// inclusive 지정 가능
NavigableMap<Integer, String> range2 = scores.subMap(70, true, 90, true);
// {70=B, 80=B+, 90=A} (70 이상 90 이하)

역순 탐색

JAVA

// 역순 뷰
NavigableMap<Integer, String> descending = scores.descendingMap();
// {95=A+, 90=A, 80=B+, 70=B, 60=C}

// 역순 키 집합
NavigableSet<Integer> descKeys = scores.descendingKeySet();

// head/tail 범위
SortedMap<Integer, String> head = scores.headMap(80);  // 80 미만
SortedMap<Integer, String> tail = scores.tailMap(80);  // 80 이상

커스텀 정렬

기본적으로 키의 자연 순서(Comparable)를 사용하지만, Comparator를 지정할 수 있습니다.

JAVA

// 역순 정렬
TreeMap<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.put("apple", 1);
reverseMap.put("banana", 2);
reverseMap.put("cherry", 3);
// {cherry=3, banana=2, apple=1}

// 문자열 길이순 정렬 (같은 길이면 사전순)
TreeMap<String, Integer> byLength = new TreeMap<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder())
);

실무 활용 예제

구간 스케줄링

JAVA

// 회의실 예약 시스템: 시간 구간 관리
TreeMap<LocalTime, String> schedule = new TreeMap<>();
schedule.put(LocalTime.of(9, 0), "회의 A");
schedule.put(LocalTime.of(10, 30), "회의 B");
schedule.put(LocalTime.of(14, 0), "회의 C");

// 현재 시각에 가장 가까운 다음 회의 찾기
LocalTime now = LocalTime.of(11, 0);
Map.Entry<LocalTime, String> nextMeeting = schedule.ceilingEntry(now);
// 14:00=회의 C

// 특정 시간대의 회의 목록
SortedMap<LocalTime, String> morningMeetings =
    schedule.subMap(LocalTime.of(9, 0), LocalTime.of(12, 0));

리더보드 (점수판)

JAVA

// 점수 기반 리더보드
TreeMap<Integer, List<String>> leaderboard = new TreeMap<>(Comparator.reverseOrder());

void addScore(String player, int score) {
    leaderboard.computeIfAbsent(score, k -> new ArrayList<>()).add(player);
}

// 상위 N명 조회
List<String> getTopPlayers(int n) {
    List<String> top = new ArrayList<>();
    for (Map.Entry<Integer, List<String>> entry : leaderboard.entrySet()) {
        for (String player : entry.getValue()) {
            top.add(player);
            if (top.size() >= n) return top;
        }
    }
    return top;
}

시계열 데이터 관리

JAVA

// 타임스탬프 기반 데이터 저장
TreeMap<Instant, Double> metrics = new TreeMap<>();

// 최근 5분간의 메트릭
Instant fiveMinutesAgo = Instant.now().minus(5, ChronoUnit.MINUTES);
SortedMap<Instant, Double> recent = metrics.tailMap(fiveMinutesAgo);

// 평균 계산
double avg = recent.values().stream()
    .mapToDouble(Double::doubleValue)
    .average()
    .orElse(0.0);

DB 인덱스와의 연결

TreeMap의 동작 원리는 데이터베이스의 B-Tree 인덱스와 유사합니다.

SQL

-- B-Tree 인덱스가 지원하는 연산들
CREATE INDEX idx_score ON students(score);

-- 범위 검색: TreeMap의 subMap과 유사
SELECT * FROM students WHERE score BETWEEN 70 AND 90;

-- 최솟값/최댓값: TreeMap의 firstKey/lastKey와 유사
SELECT MIN(score), MAX(score) FROM students;

-- 정렬: TreeMap의 자연 순서 순회와 유사
SELECT * FROM students ORDER BY score;

TreeMap의 subMap(70, 90)이 O(log n + k)인 것처럼, B-Tree 인덱스도 범위 스캔을 효율적으로 처리합니다.

인덱스 스캔 vs 풀 스캔

SQL	HashMap 비유	TreeMap 비유
`WHERE id = 5`	get(5): O(1)	get(5): O(log n)
`WHERE score BETWEEN 70 AND 90`	전체 순회: O(n)	subMap: O(log n + k)
`ORDER BY score`	정렬 필요: O(n log n)	순회: O(n)

TreeMap vs TreeSet

TreeSet은 내부적으로 TreeMap을 래핑합니다.

JAVA

// TreeSet 내부 (간략화)
public class TreeSet<E> implements NavigableSet<E> {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();

    public TreeSet() {
        this.m = new TreeMap<>();
    }

    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }
}

TreeSet은 "값이 항상 PRESENT인 TreeMap"에 불과합니다.

LinkedHashMap — 삽입 순서 유지

정렬이 아니라 삽입 순서 만 유지하면 된다면 LinkedHashMap이 적합합니다.

JAVA

// 삽입 순서 유지
LinkedHashMap<String, Integer> linked = new LinkedHashMap<>();
linked.put("banana", 2);
linked.put("apple", 1);
linked.put("cherry", 3);
// {banana=2, apple=1, cherry=3} — 삽입 순서 유지

// TreeMap과의 차이
TreeMap<String, Integer> tree = new TreeMap<>(linked);
// {apple=1, banana=2, cherry=3} — 키 정렬 순서

정리

TreeMap은 Red-Black 트리 기반 으로 키를 정렬된 상태로 유지합니다.
모든 연산이 O(log n) 이며, HashMap의 O(1)보다 느리지만 정렬과 범위 검색 에서 강점을 보입니다.
NavigableMap의 floor, ceiling, subMap 등은 구간 처리에 매우 유용합니다.
DB의 B-Tree 인덱스와 동작 원리가 유사하여, 범위 스캔 이 효율적입니다.
순서가 필요 없다면 HashMap, 정렬이 필요하면 TreeMap, 삽입 순서가 필요하면 LinkedHashMap을 선택합니다.