TreeSet은 왜 이진 탐색 트리 대신 레드-블랙 트리를 사용할까?

TreeSet 이란? 

• 중복을 허용하지 않고,
• 자동으로 정렬되는 Set 컬렉션입니다.

내부적으로는 TreeMap을 사용하고,
TreeMap의 핵심 자료구조가 바로 레드-블랙 트리(Red-Black Tree)이다!

이진 탐색 트리란 어떤 문제가 있을까? 

이진 탐색 트리는:

• 왼쪽 < 부모 < 오른쪽 규칙을 지키는 간단한 구조지만,
• 삽입 순서에 따라 한쪽으로 쏠릴 수 있는 문제가 있다.

예시: 오름차순으로 삽입

1 → 2 → 3 → 4 → 5

 

[1]
  \
  [2]
    \
    [3]
      \
      [4]
        \
        [5]

이 구조는 거의 LinkedList처럼 변형되어,
검색/삽입 성능이 O(log n)에서 O(n)으로 퇴화할 수 있다.

레드-블랙 트리(Red-Black Tree)는 어떻게 다른가?

레드-블랙 트리는 트리의 균형을 자동으로 맞춰주는 이진 탐색 트리이다.

• 노드에 색깔(Red/Black) 을 부여하여
• 트리의 균형을 유지한다.

🧩 레드-블랙 트리의 5가지 규칙:

1. 노드는 빨강(Red) 또는 검정(Black)이다.
2. 루트 노드는 항상 검정이다.
3. 빨강 노드의 자식은 반드시 검정이다. (빨강이 연속되지 않는다)
4. 루트에서 리프(null)까지 가는 경로의 검정 노드 수는 모두 같다.
5. 리프(null)는 검정으로 간주한다.

노드는 언제 빨강으로 설정되는가?

기본 규칙:

새로 삽입되는 노드는 항상 빨강(Red) 으로 설정된다.

빨강으로 시작하는 이유는 빨강 노드는 트리 높이에 영향을 주지 않기 때문이다.
만약 검정으로 시작하면 트리의 높이가 증가할 수 있기 때문에 빨강으로 삽입하는 것이 기본이다.

📦 삽입 흐름 예시 (노드 색상 변경 과정)

삽입 순서:

10 → 5 → 15 → 3

10 삽입

• 첫 노드는 예외적으로 검정으로 설정된다.

 

(B)10

5 삽입

• 새 노드는 항상 빨강이다.
• 부모(10)는 검정이므로 문제없다.

(B)10
 /
(R)5

15 삽입

• 새 노드는 빨강이다.
• 부모(10)는 검정이므로 문제없다.

    (B)10
     /   \
 (R)5   (R)15

3 삽입

• 새 노드는 빨강이다.
• 부모(5)도 빨강이므로 빨강-빨강 충돌이 발생한다.

해결 방법: 색깔 조정 (Recoloring)

• 부모(5)와 삼촌(15) 모두 빨강이므로 → 부모/삼촌을 검정, 할아버지(10)를 빨강으로 변경한다.

    (R)10
     /   \
 (B)5   (B)15
 /
(R)3

• 하지만 루트는 항상 검정이어야 하므로 → 10을 다시 검정으로 설정한다.

    (B)10
     /   \
 (B)5   (B)15
 /
(R)3

이러한 과정을 통해 트리는 균형을 유지하게 된다.

왜 TreeSet은 레드-블랙 트리를 사용하는가?

이유	설명
✅ 트리의 균형 유지	항상 O(log n) 성능을 보장한다. (편향 트리 걱정이 없다)
✅ 자동 정렬	데이터를 삽입할 때마다 정렬 상태로 저장된다.
✅ 중복 제거 + 정렬 유지	HashSet은 순서가 없지만, TreeSet은 정렬된 상태를 유지한다.