[자료구조] 레드-블랙 트리(Red-Black Tree)

Red-Black Tree

출처 : 위키피디아

 자가 균형 이진 탐색 트리(self-balancing binary search tree) 로서, 대표적으로 연관 배열 등을 구현하는 데 쓰이는 자료구조입니다. 

트리에 N개의 원소가 있을 때 O(log N)의 시간 복잡도를 삽입, 삭제, 검색을 할 수 있습니다.

레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 일정한 실행 시간을 보장하여 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 사용됩니다.

 

특성

Red-Black Tree는 각각의 노드가 Red, Black 두가지의 색상 속성을 가지고 있는 이진 탐색 트리입니다.

각 구성 원소는 in-order traversal(중위순회) 연산을 수행합니다.

- in-order traversal(중위순회) : 왼쪽 끝까지 내려간 이후 노드를 방문하고 오른쪽 자식 노드로 이동하여 순회를 계속한다.

조건

이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한 Red-Black Tree가 됩니다.

1. 노드는 Red 혹은 Black 중의 하나이다.
2. Root Property : 루트 노드는 Black
3. External Property : 모든 리프 노드들(NIL)은 Black
4. Internal Property : Red 노드의 자식노드 양쪽은 언제나 모두 Black
   (Red 노드는 연달아 나타날 수 없음 == No Double Red
    , Black노드 만이 Red노드의 부모가 될 수 있다.)
5. Depth Property : 모든 리프 노드에서 Black depth는 같다.
   (리프 노드에서 루트 노드까지 가는 경로에서 만나는 Black노드의 개수가 같다.)

 

삽입

(리프 노드는 생략되었습니다.)

Red-Black Tree에 새로운 노드를 삽입할 때 새로운 노드는 항상 Red로 삽입된다.

Red노드가 연속으로 2번 나타나는 (Double Red)가 발생하여 4번 조건에 위배되는 경우가 나옵니다.

 

Double Red 문제 해결

N : New, 새로 삽입할 노드
P : Parent, 부모 노드
G : Grant Parent, 조상 노드
U : Uncle, 삼촌 노드

 

Red-Black Tree는 이러한 Double Red문제를 해결하기 위해 2가지 전략을 사용합니다.

insert(7)

- U == Balck → Restructuring

- U == Red → Recoloring

Restructuring

1. In-order traversal (중위 순환) 
   - N, P, G를 오름차순으로 정렬
   - 셋 중 중간 값이 부모, 나머지 둘을 자식
2. 새로 부모가 된 노드를 Black으로 만들고 나머지 자식들을 Red

예를 들면 다음과 같은 작업 과정입니다.

1. 7 삽입

2. Double Red 발생!

    →Restructuring 진행

        1) 6, 7, 8 을 In-order 정렬 

        2) tree 변경

        3) 새로 부모가 된 노드를 Black, 자식은 Red

insert(13)

9는 원래 8의 자식 노드였기 때문에 그대로 따라갑니다.

 

Recoloring

1. N, P, U를 Black으로 변경, G는 Red로 변경
  1-1. G 가 루트 노드라면 Black으로 변경
  1-2. G 를 Red로 변경 시 Double Red 발생하면 Restructuring 및 Recoloring 진행
  1-3. Double Red 발생하지 않을 때까지 반복

※ G가 루트 노드가 아니었을 시 Double Red가 다시 발생할 수 있습니다.

 

insert(13)

insert(23) 연산1

---

좀 더 깊은 depth를 가진 tree로 예제를 풀어보겠습니다.

 

insert(23)

insert(23) 연산2

Double Red 발생!

U가 Red 임으로 Recoloring으로 진행합니다.

 

insert(23) 연산3

Double Red 발생!

U가 Red 임으로 Recoloring으로 진행합니다.

G가 루트 노드임으로 Black으로 변경합니다.

insert(23) 연산 최종

연산이 모두 끝난 최종 B-R Tree입니다.

---

Red-Black Tree에 삽입(insertion)하는 경우, Restructuring 과 Recoloring 둘다 O(logN) 시간 복잡도를 가지게 됩니다.

 

4번 조건인 Depth Property 덕분에 Red-Black Tree의 높이가 logN에 바운드 될 수 있습니다. 때문에 Balance하다고 할 수 있습니다.

레드 블랙 트리는 현재 고안된 이진탐색 트리 중 가장 성능이 좋다고 합니다.

 

C++ STL에서도 사용하고 있는 자료구조입니다.

 

 

 

Red-Black Tree를 구현해볼 수 있는 사이트입니다.