[자료구조] RB트리

set, map, multiset, multimap과 같은 자동 정렬 연관 컨테이너는 내부적으로 Red-Black Tree를 사용해 데이터를 저장한다.

 

RB 트리란?

이진 탐색 트리의 한 종류로 항상 균형 잡힌 상태를 유지하도록 만든 자가 균형 이진 탐색 트리이다.

즉, 최악의 경우에도 탐색, 삽입, 삭제 시간이 O(log n)을 보장한다.

 

RB 트리의 핵심 속성

각 노드는 빨간색 또는 검은색으로 나누어진다.

그리고 5가지 규칙을 만족한다

 

1. 모든 노드는 빨강 또는 검정이다.

2. 루트노드는 항상 검정이다.

3. 모든 리프노드(NIL 포인터 : 암시적으로 존재하는 노드)는 검정이다

4. 빨간노드의 자식은 항상 검정이다(연속된 빨강노드 없음)

5. 루트에서 리프까지 가는 모든 경로의 검정 노드 수는 같다.

 

왜 RB 트리를 쓰는가?

이진 탐색트리의 단점

일반 BST는 삽입 순서에 따라 매우 한쪽으로 치우쳐져서 O(n) 성능이 될 수도 있다.

 

RB트리의 장점

항상 균형에 가까운 형태를 유지한다

삽입, 삭제, 탐색이 모두 O(log n) 시간 복잡도 보장된다.

자가 균형 조절을 위한 회전/색 변경이 있지만 비용은 제한적이며 예측가능하다. 

 

특히 C++ STL 구현에서는 삽입 시 자동으로 정렬되도록 하기 위해 RB 트리가 이상적이다.

 

 

예시구조

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

5가지 규칙을 만족한다.

 

또한,

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

이것도 유효한 RB트리이다. 역시 5가지 규칙을 만족했다. 하지만 균형유지 목적으로 빨강을 섞은걸 더 많이 쓴다.

 

연관예시

 

삽입

새 노드는 항상 빨강으로 삽입

삽입 후 부모 색에 따라 회전 및 색 변경 수행 -> 이를 통해 균형을 유지

 

삭제

삭제 시 검정 노드를 제거하면 검정 균형 조건이 깨질 수 있으므로 case를 나눠 형제 노드의 색상에 따라 회전/색상 변경 등 복잡한 보정 수행