RB 트리(Red-Black Tree)

Ena JJJ·2022년 11월 26일

datastructure

Red-Black Tree란?

레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조이다.
레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

RBTree 특성(5개)

모든 노드 RED / BLACK
루트노드는 BLACK
모든 NIL 노드는 BLACK
노드가 RED 면, 자녀는 BLACK(RED는 연속하면 안됨)
임의의 경로(자신을 제외)부터 자손 NIL까지 BLACK개수는 동일

RB트리는 어떻게 균형을 잡는가?

삽입/삭제시 #2,#4,#5 속성을 위반함. 이들을 해결하기 위해서 구조를 바꾸면, 자연스럽게 균형이 잡히게 된다.

삽입처리

삽입전 RB트리 속성을 만족한 상태
삽입 방식은 일반적인 BST(이진검색트리)와 동일(삽입노드의 색깔은 항상 RED)
삽입 후 RB트리 속성 위반 여부 확인
RB트리 속성을 위반했다면 재조정(insert-fixup)
RB트리 속성을 다시 만족

삽입노드는 무조건 RED인 이유 -> 삽입 후에도 #5 속성을 만족하기 위해서

insert-fixup(삽입 시 속성위반 재조정)

삽입 후 #2, #4 속성을 위반할 경우가 발생하므로, 다음의 알고리즘 수행을 수행해서 속성 위반을 해결

while (부모가 RED) {

 CASE 1. 
if 부모/삼촌 == RED이면, 
    부모/삼촌 모두 BLACK으로 바꾸고, 할아버지를 RED로 변경
    할아버지에서 다시 시작
  
// CASE 2/3. 삼촌 == BLACK
else {
    // CASE 2. 
    if 할아버지/부모/자신 꺾인 상태
        회전해서 부모/자신을 펴준다. CASE 3 상태가 됨
 
    // CASE 3. 할아버지/부모/자신 펴진 상태
    부모/할아버지 서로 색바꾸기
    할아버지 기준 회전
}

}

// 종료전
루트를 BLACK으로 변경

삽입 시 조정 CASE 1,2,3

아래의 CASE 2,3은 좌우 대칭으로 동작

수평으로 배치된 두개의 레드가 있다면, 색상을 블랙으로 변경하고 부모를 레드로 바꿀 수 있다.

삭제 처리

삭제 전 RB트리 속성 만족한 상태
삭제 방식은 일반적인 BST와 동일
삭제 후 RB트리 속성 위반 여부 확인
RB트리 속성을 위반했다면 재조정 (delete-fixup)
RB트리 속성을 다시 만족

삭제 색 결정법

삭제하려는 노드의 자녀가 없거나 하나라면, 삭제 후 노드의 색은 자기자신의 색

삭제하려는 노드의 자녀가 둘이라면, 삭제 후 노드의 색은 삭제된 노드의 색

delete-fixup (삭제 시 속성위반 재조정)

삭제색이 RED이면, 어떠한 속성도 위반하지 않는다
삭제색이 BLACK이면, #2, #4, #5 속성을 위반할 수 있다

#2. 루트노드는 블랙
#4. 노드가 RED면, 자녀는 BLACK (레드는 연속하면 안됨)
#5. 임의의 경로(자신을 제외)부터 자손 NIL까지 BLACK의 개수 동일
블랙이 지워졌을 때, 블랙높이가 -1 됨. #5 속성이 깨짐

해당 위치(아래의 그림에서 회색 노드)에서 #5 를 만족시키도록 조정

부모 - 형제 - RED자손 -> 꺾인상태 -> 형제기준 회전 -> 펴주기

부모 - 형제 - RED자손 -> 펴진상태 -> 부모기준 회정 -> 구부리기

while (타겟이 루트아님 && 타겟 == BLACK) {

  // CASE 1.
  if 형제 == RED
      형제/부모 서로 색바꾸기, 부모기준 회전 (타겟이 내려가도록)

  // CASE 2.
  if 형제 == BLACK, 형제의 자식 둘다 블랙
      형제/자신의 블랙을 부모로 올리기 -> 형제를 RED로 변경, 부모에서 다시 fixup

  else {
      // CASE 3.
      if 형제 == BLACK, 부모/형제/(형제의 꺾인 자식) == RED
          자식 RED와 형제 서로 색바꾸기, 펴지게 회전 (RED가 바깥쪽에 오게)
          CASE 4가 됨

      // CASE 4. 형제 == BLACK, 부모/형제/(형제의 펴진 자식) == RED
      부모/형제 서로 색바꾸기
      형제의(펴진 자식) = BLACK
      부모기준 회전 (타겟이 내려가도록)
      타겟을 루트로 설정 -> while 종료
  }
}

	// 종료전
타겟을 BLACK으로 변경

자료구조 (rbtree, node_t)

typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;

typedef int key_t;

typedef struct node_t {
    color_t color;
    key_t key;
    struct node_t *parent, *left, *right;
} node_t;

typedef struct {
    node_t *root;
    node_t *nil;  // for sentinel
} rbtree;