RBTree(Red Black Tree)

RB트리는
전체 트리의 높이를 $\log N$ ($N$은 노드의 개수) 으로 유지하는
이진 탐색 트리이다.

RBTREE의 5가지 조건

1. 모든 노드는 RED 또는 BLACK

2. 루트는 BLACK

3. 모든 리프(NIL)는 BLACK

4. 노드가 RED 이면 그 노드의 자식은 모두 BLACK

5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함해야함

각 노드는 자신의 부모, 왼쪽 자식, 오른쪽 자식의 정보와
노드 자신의 key값을 가지고 있다.

구현을 용이하게 하기 위해 NIL node 를 이용하는데,
NIL node 는 부모와 자식 정보를 가지지 않고
색깔이 항상 BLACK인 node로 정의한다.

💻 구현(1) (노드, RB트리)

노드와 트리의 정보를 갖게 될 구조체는 다음과 같이 구현했다.

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;

node_t

node_t는 RB트리의 노드 구조체이다.
자기 자신의 포인터 변수를 갖는 구조체를 '자기 참조 구조체' 라고 하며,
자기 참조 구조체가 갖는 자기 자신 타입의 포인터 멤버를 링크(link)라고 한다.
node_t는 자기 참조 구조체이고,
*parent, *left, *right는 링크이다.

멤버

color_t color : 노드의 색(RBTREE_RED, RBTREE_BLACK)
key_t key : 노드의 Key값(int)
struct node_t *parent, *left, *right
: 순서대로, 노드의 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드

rbtree

rbtree는 RB트리 구조체이다.

멤버

node_t *root : rbtree의 root 노드. 초기값은 nil
node_t *nil : 경계노드.
한 노드의 자식 또는 부모가 존재하지 않으면 nil로 채운다.

RB Tree를 복구하기 위한 방법

Insert와 Delete는 트리를 수정한다.
이는 원래 트리를 RB트리의 조건에 위배되는 상태로 만들 수 있다.
따라서, Insert와 Delete 이후에는 RB트리를 복구시키는 과정이 필요하다.

복구를 위해 트리를 일부 수정해주어야 하고,
수정에 공통적으로 사용되는 2가지 방법이 존재한다.

하나는 노드의 연결 정보를 변경시키는 회전 이고,
다른 하나는 노드의 색을 바꿔주는 방법이다.

두 방법 모두 이진 탐색 트리의 특성을 보전한다.

두 가지 방법 중 색을 바꿔주는 것은
말 그대로 각 노드의 색을 조건에 맞게 변경해주는 것으로
이후에 RB트리가 복구 되는 과정에서 조건에 맞게 진행될 것이다.

회전 또한 복구 과정에서 조건에 맞게 사용되나,
우선 회전이라는 것이 어떤 일이 일어나는 과정인지 알아볼 필요가 있다.

회전(Rotate)

우회전(Right-Rotate)과 좌회전(Left-Rotate)이 있다.

왜 할까?

RB 트리는 높이를 $\log N$ ($N$은 노드의 개수) 으로 유지 시키는
이진 탐색 트리라고 설명했다.

RB 트리에 node를 삽입하거나, 기존의 node를 삭제하는 것은
트리 한쪽이 치우쳐지는 형태의 불균형을 초래하고,
이는 이 불균형을 존재하지 않도록 강제하는 RB 트리의 5가지 조건(혹은 특성)을 위배하는 상황으로 이어진다.

어떤 node의 삽입/삭제로 인해
root노드 기준 좌/우 subTree 중 한 쪽의 길이가 상대적으로 짧아진 tree를 생각해보자,

좌우의 균형을 다시 맞춰주기 위해서, 아래처럼 간단한 방법을 생각해 볼 수 있다.

길이가 긴 subtree의 root node 레벨을 올려주어, 전체 트리의 좌/우 서브트리의 높이를 맞춰주는 것이다.
위 그림은 단순한 예시이고, 실제로 Rotate는 저런식으로 동작하지는 않는다(양 subtree의 크기나 Rotate 이후의 형태도 맞지 않다.).
다만 Rotate를 하는 목적에 대한 직관적인 설명은 될 수 있을 것이다.

해도 될까?

Rotate가 RB 트리의 불균형을 조정하기 위한 방법이라면,
최소한 RB 트리가 되기 위한 전제인 "이진 탐색 트리"인 상태를 깨뜨려서는 안 될 것이다.

아래에 Left Rotate와 Right Rotate의 과정을 그려놓았다.
각 과정에서 어떤 방식으로 이진 탐색 트리의 특성을 유지 시키면서
Rotate를 가능하게 하는지 확인해 볼 수 있다.

해보자

코드나 설명을 보면 부분적으로는 이해가 되는데,
전체 과정이 그려지지를 않아서
그냥 진짜로 그림을 그려보았다.

아래는 혹시 몰라서 적어둔 그림의 이해를 위한 설명이다.

회전이 진행되며 두 Node의 사이의 간선이 변경되는 과정을 코드와 그림으로 표현했다.

각 Node는 부모, 왼쪽 자식, 오른쪽 자식의 정보를 가지고 있고,
간선의 방향은 정보를 가진 Node에서 그 정보에 해당하는 Node로 향한다.

예를들어, Node A에서 Node B로 향하는(A에서 출발한 화살표가 B에 꽂힌) 간선이 존재할 때,
Node A는 부모 또는 왼쪽 자식 또는 오른쪽 자식 중 하나의 관계로서
Node B의 정보를 가지고 있다는 의미이다.
(Node A가 Node B의 정보를 가지고 있다.)

각 단계에서 변경된 간선에 대해
변경 이전의 간선은 빨간 점선으로,
변경 이후의 간선은 파란 실선으로 그렸으며
변경 이후의 간선으로 생긴 새롭게 연결된 Node와의 관계를

P = 부모
Left = 왼쪽 자식
Right = 오른쪽 자식
Child = 자식(좌/우 구분을 따로 표현하지 않음)

와 같이 표시했다.

우회전(Right-Rotate)

왼쪽이 right rotate 이전의 상태,
오른쪽이 right rotate 이후의 상태이다.

right rotate 과정을 단계로 구분지어 표현했다.
하나의 단계마다 하나의 Node가 가지는 부모 또는 왼쪽 자식 또는 오른쪽 자식 의 정보가 수정된다.

📍 1번 단계에서

Node x 에서 위쪽(빈 곳)으로 연결된 간선은 x와 x의 부모 노드가 연결된 간선이다.
이후 단계가 진행되면서,
마찬가지로 위쪽의 빈 곳을 향하는 간선은 회전 전의 x의 부모 노드와 연결된 간선이다.

📍 1번, 2번 단계에서

x와 $\beta$ 는 부모-왼쪽자식 관계를 갖게된다.

📍 3번, 4번 단계에서

y와 회전 전의 x의 부모 노드 는 자식-부모 관계를 갖게된다.
(4번의 Child 라고 표시된 간선과, 5번의 Right 라고 표시된 간선에 의해)

이는 회전 전의 x와 x의 부모 노드 사이의 관계를 그대로 대체하는 것이다.

y가 x의 자리를 차지할 때
x와 x의 부모와의 관계를 그대로 가져가야 하기 하기 때문에,

y가 회전 전의 x의 부모 노드 의 왼쪽 자식이 되는지, 오른쪽 자식이 되는지는
x가 회전 전의 x의 부모 노드 의 왼쪽 자식이었는지, 오른쪽 자식이었는지 여부를 그대로 따라간다.

회전 전의 상태에서,

x가 x의 부모 노드의 왼쪽 자식이었다면,
4단계의 Child라는 표현은 Left가 될 것이고,

x가 x의 부모 노드의 오른쪽 자식이었다면, Right가 될 것이다.

( x가 root 였다면, y는 root가 된다. )

📍 5번, 6번 단계에서

원래는 부모였던 node x와
원래는 왼쪽 자식이었던 node y의
부모-자식 관계의 역전이 일어난다.

y는 x를 자신의 오른쪽 자식으로 두고,
x는 y를 자신의 부모로 둔다.

💻 구현(2) (right rotate)

void right_rotate(rbtree *t, node_t *x) {
  node_t *y = x->left;
  x->left = y->right;
  if(y->right != t->nil) {
    y->right->parent = x;
  }
  y->parent = x->parent;
  if(x->parent == t->nil) {
    t->root = y;
  } else if(x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->right = y;
  }
  y->right = x;
  x->parent = y;
}

좌회전(Left-Rotate)

right rotate의 과정과 대칭이다.

과정이 right rotate와 완벽하게 대칭이기 때문에, 부연 설명은 적지 않았다.

💻 구현(3) (left rotate)

void left_rotate(rbtree *t, node_t *x) {
  node_t *y = x->right;
  x->right = y->left;
  if(y->left != t->nil) {
    y->left->parent = x;
  }
  y->parent = x->parent;
  if(x->parent == t->nil) {
    t->root = y;
  } else if(x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->right = y;
  }
  y->left = x;
  x->parent = y;
}

rotate

전체 과정을 보았다면, 이진 탐색 트리에서 한 노드의 각 자식들이 가지는 특성은 그대로 유지된다는 사실을 확인 할 수 있을 것이다.

Left Rotate를 예로 들면,
$\beta$는 y의 왼쪽 자식에서 x의 오른쪽 자식이 된다.

y의 왼쪽 자식이었던 $\beta$의 대소관계는 $x \le \beta \le y$ 이었을 것이고,
이는 x의 오른쪽 자식인 $\beta$가 $x \le \beta$ 이어야 한다는 조건을 항상 만족한다.

x와 y의 부모-자식관계가 변경 가능한 것도 마찬가지 이다.

y가 x의 오른쪽 자식일 때의 x, y의 대소관계 ( $x \le y$ ) 와
x가 y의 왼쪽 자식일 때의 x, y의 대소관계 ( $x \le y$ ) 는 같다.

따라서 rotate는 "이진 탐색 트리"의 특성을 유지한 채로 node를 회전시킬 수 있다.