[자료구조] (2) 레드블랙 트리(Red-Black Tree)와 이진 트리(Binary Tree)의 차이점

데이터를 효율적으로 저장하고 검색하기 위해 다양한 트리 자료구조(Tree Structure)가 사용된다. 그중에서도 이진 트리와 레드블랙 트리는 많은 프로그래밍 환경에서 자주 등장한다. Java Collection에서 트리 맵(Tree Map), 트리 셋(Tree Set)의 경우 레드블랙 트리를 사용한다. 그럼 이진트리와 레드블랙 트리는 어떤점이 다를까?

 

이진 트리(Binary Tree)란?

이진 트리는 모든 노드가 최대 두 개의 자식 노드(left, right)를 가지는 트리 구조이다.

    10
   /  \
  5    15

• 노드 : 트리 구조의 기본 단위로, 값(data)을 저장하고 다른 노드와의 연결을 가짐
• 루트(Root) 노드 : 트리의 제일 위에 있는 시작 노드
• 자식 노드 : 어떤 노드의 아래에 연결된 노드
• 부모 노드 : 자식 노드를 가진 노드
• 형제 노드 : 같은 부모를 가진 노드
• 리프(Leaf) 노드 : 더이상 자식이 없는 노드

출처 : https://rosweet-ai.tistory.com/55

비록 같은 값을 가지고 있다고 해도 이진 트리는 왼쪽 자식 노드와 오른쪽 자신 노드를 구분한다.

 

출처 : https://rosweet-ai.tistory.com/55

이진 트리는 트리지만 선형자료구조인 1차원 배열로도 표현할 수 있다는 특징을 가집니다.

 

이진 탐색 트리(Binary Search Tree, BST)란?

보통 "이진 트리"라고 하면 정렬된 구조인 이진 탐색 트리(BST)를 말한다.

 

BST의 규칙

• 왼쪽 서브트리의 값은 부모 노드보다 작아야 한다.
• 오른쪽 서브트리의 값은 부모 노드보다 커야 한다.
• 이 규칙은 모든 노드에 대해 적용된다.

     10
    /  \
   5    15
  / \     \
 2   7     20

 

이런 규칙을 통해 데이터를 저장하면, 탐색(Search), 삽입(Insert), 삭제(Delete) 같은 연산이 평균적으로 **O(log N)**의 시간 복잡도로 수행된다.

BST의 단점

데이터가 정렬되어 들어오는 경우, 트리가 한쪽으로 쏠리는 편향(Bias) 현상이 발생할 수 있다.

삽입 순서: 1 → 2 → 3 → 4 → 5

생성되는 트리:
1
 \
  2
   \
    3
     \
      4
       \
        5

 

이럴 경우 트리는 사실상 리스트처럼 변해버리며, 탐색 시간도 O(N)으로 늘어난다.
이를 방지하기 위해 등장한 것이 바로 레드블랙 트리(Red-Black Tree)다.

 

레드블랙 트리(Red-Black Tree)란?

레드블랙 트리는 이진 탐색 트리의 성능 저하 문제를 해결하기 위해 고안된 균형 이진 탐색 트리(Self-Balancing BST)이다.

 

핵심 특징

• 각 노드는 빨강(Red) 또는 검정(Black)으로 색칠된다.
• 트리의 높이가 자동으로 균형을 유지하도록 삽입/삭제 시 재구성(회전 + 색 변경)이 일어난다.
• 최악의 경우에도 트리의 높이가 2 × log N을 넘지 않도록 보장한다.

주요 규칙

1. 루트는 항상 검정이다.
2. 빨간 노드는 연속해서 나올 수 없다. (즉, 빨간 노드의 자식은 반드시 검정)
3. 루트에서 리프 노드까지 가는 모든 경로의 검정 노드 수는 동일해야 한다.
4. 리프 노드는 모두 NIL(=null)이며 검정색이다.

이러한 규칙 덕분에, 데이터를 어떤 순서로 삽입하더라도 트리는 균형을 유지하고 O(log N)의 탐색 성능을 보장한다.

 

이진 트리 vs 레드블랙 트리 요약 비교

구분	이진 트리(BST)	레드 블랙 트리(RBT)
구조	모든 노드가 최대 2개의 자식을 가짐	BST 규칙 + 색상과 균형 유지 규칙 추가
균형 유지	없음 (삽입 순서에 따라 한쪽으로 쏠림 가능)	자동 균형 유지 (회전 및 색상 변경)
최악 시간 복잡도	O(N) (편향된 경우)	O(log N) (균형 유지됨)
구현 난이도	상대적으로 쉬움	복잡함 (회전, 색 규칙 처리 필요)
사용 예시	학습용, 단순한 트리 구조	Java TreeMap, C++ std::map, 데이터베이스 인덱스 구조 등