레드-블랙 트리
Updated:
Red-Black Tree
개념
레드-블랙 트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
레드-블랙 트리를 포함한 이진 탐색 트리는 모든 노드에 ‘자신이 가진 자료는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고, 자신보다 왼쪽에 위치한 부분트리가 가지고 있는 자료보다 크거나 같다’라는 조건을 만족한다. 이런 특성 때문에 특정 값을 빠르게 찾아 낼 수 있으며, 각 구성원소(elements)간의 효율적인 in-order traversal이 가능하다.
용도와 장점
레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.
특성
레드-블랙 트리는 각각의 노드가 레드나 블랙이인 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한(valid) 레드-블랙 트리가 된다.
- 노드는 레드 혹은 블랙 중에 하나이다.
- 루트 노드는 블랙이다.
- 모든 리프 노드들(NIL)은 블랙이다.
- 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
- 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
위 조건들을 만족하게 되면, 레드-블랙 트리는 가장 중요한 특성을 나타내게 된다: 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배보다 항상 작음. 다시 말해 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다. 따라서, 삽입-삭제-검색시 최악의 경우에서의 시간복잡도가 트리의 높이에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다.
동작
레드-블랙 트리의 읽기 전용(read-only) 동작(탐색 등)은 이진 탐색 트리의 읽기 전용 동작의 구현을 변경하지 않아도 되는데, 이는 레드-블랙 트리가 이진 탐색 트리의 특수한 한 형태이기 때문이다. 그러나 삽입(insertion)과 삭제(removal)의 경우 이진 탐색 트리의 구현에 따른 동작만으로는 레드-블랙 트리의 특성을 만족하지 못한다. 다시 레드-블랙 트리의 특성을 만족하게 만들기 위해서는 O(log n) 또는 amortized O(1)번의 색 변환과 최대 3회의 트리 회전이 필요하다(삽입의 경우 2회). 삽입과 삭제는 복잡한 동작이지만, 그 복잡도는 여전히 O(log n)이다.
- 삽입(Insertion)
레드-블랙 트리의 삽입은 단순 이진 탐색 트리에서 하는 것과 같이 노드를 삽입하고, 색을 붉은색으로 정하는 것으로 시작한다. 그 다음 단계는 주위 노드의 색에 따라 달라진다. 여기서 ‘삼촌 노드(uncle node)’를 도입할텐데, 이는 같은 높이에 있는 옆 노드의 부모 노드를 뜻한다. 여기서 레드-블랙 트리의 특성이 추가된다.
- 특성 3(모든 리프 노드들은 검정색이다)은 언제나 변하지 않는다.
- 특성 4(적색 노드의 모든(두) 자식은 검정색이다)는 적색 노드의 추가, 검정색 노드의 적색 노드로의 전환, 회전에 의해서 제대로 지켜지지 않는 상황이 된다.
- 특성 5(어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다)는 검정색 노드의 추가, 적색 노드의 검정색 노드로의 전환, 회전에 의해서 제대로 지켜지지 않는 상황이 된다.
- N : 삽입하는 원소
- P : N의 부모 노드
- G : P의 부모 노드
- U : N의 삼촌 노드
struct node *grandparent(struct node *n)
{
if ((n != NULL) && (n->parent != NULL))
return n->parent->parent;
else
return NULL;
}
struct node *uncle(struct node *n)
{
if (n == NULL)
return NULL;
struct node *g = grandeparent(n);
if (g == NULL)
return NULL; // 할아버지가 없으면 삼촌도 없다
if (n->parent == g->left)
return g->right;
else
return g->left;
}
첫 번째 경우
N이라고 하는 새로운 노드가 트리의 시작(root)에 위치한다. 이 경우 레드-블랙 트리의 첫 번째 속성(트리의 시작은 검정색이다)을 만족하기 위해서 N을 검정색으로 표시한다. 이 경우 시작점으로부터 뻗어나가는 모든 경로에 검정색 노드를 하나 추가한 셈이 되기 때문에 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)은 여전히 유효하다.
void insert_case1(struct node *n)
{
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}
두 번째 경우
새로운 노드의 부모 노드 P가 검정색이라면, 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식 노드는 검정색이다)은 유효하다. 그러므로 두 번째 경우에도 이 트리는 적절한 레드-블랙 트리이다.
레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)도 별 문제가 없는데, 이는 새로운 노드 N은 두개의 검정색 노드를 leaf node로 가지고 있기 때문이다. 비록 N이 붉은색 노드라고 해도 N이 들어간 자리에 원래 위치했던 노드의 색이 검정색이었으므로, N의 자식 노드에게서 시작되는 경로들은 모두 같은 수의 검정색 노드를 가지게 되고, 결과적으로 다섯 번째 속성은 유지되게 된다.
void insert_case2(struct node *n)
{
if (n == NULL)
return;
if (n->parent->color == BLACK)
return;
else
insert_case3(n);
}
세 번째 경우
만약 부모 노드 P와 삼촌 노드 U가 모두 붉은색 노드라면, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)을 유지하기 위해서, P와 U를 모두 검정색으로 바꾸고 할아버지 노드 G를 붉은색으로 바꾼다. 이렇게 함으로써 붉은색 노드인 N은 검정색 부모 노드를 가지게 된다.
그런데 이번에는 할아버지 노드 G가 레드 블랙 트리의 두 번째 속성(root node는 검정색이다)이나 네 번째 속성(붉은색 노드의 두 자식 노드는 검정색이다)을 만족하지 않을 수 있다(네 번째 속성은 G의 부모 노드가 붉은색일 경우 만족하지 않는다). 이를 해결하기 위해서 G에 대해 지금까지 설명한 첫 번째 경우부터 세 번째 경우까지를 재귀적으로 적용한다. 이 작업은 삽입 과정 중에 발생하는 유일한 재귀 호출이며, 회전 작업을 하기 전에 적용해야 한다는 것에 주의한다. (이는 일정한 횟수의 회전 작업만이 필요하다는 것을 증명한다)
void insert_case3(struct node *n)
{
if (n == NULL)
return;
struct node *u = uncle(n), *g;
if ((u != NULL) && (u->color == RED))
{
n->parent->color = BLACK;
u->color = BLACK;
g = grandparent(n);
g->color = RED;
insert_case1(g);
}
else
{
insert_case4(n);
}
}
주의:이 후의 단계에서는 부모 노드 P가 항라버지 노드 G의 자식이라고 가정하고 진행한다. 만약 P가 G의 오른쪽 자식이라고 했을 때는 네 번째, 다섯 번째 경우에서 왼쪽과 오른쪽을 바꿔서 진행하면 된다. 소스 코드는 이를 고려해서 작성되어있다.
네 번째 경우
부모 노드 P가 붉은색인데, 삼촌 노드 U는 검정색이다. 또한, 새로운 노드 N은 P의 오른쪽 자식 노드이며, P는 할아버지 노드 G의 왼쪽 자식 노드이다. 이 경우 N과 P의 역할을 변경하기 위해 왼쪽 회전을 한다. 그 후 부모 노드였던 P를 다섯 번째 경우에서 처리하게 되는데, 이는 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식은 검정색 노드이다)을 아직 만족하지 않기 때문이다.
회전 작업은 몇몇 경로들이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)을 위반하지 않는다.
void insert_case4(struct node *n)
{
if (n == NULL)
return;
struct node *g = grandparent(n);
if ((n == n->parent->right) && (n->parent == g->left))
{
rotate_left(n->parent);
n = n->left;
}
else if ((n == n->parent->left) && (n->parent == g->right))
{
rotate_right(n->parent);
n = n->right;
}
insert_case5(n);
}
static void rotate_left(struct node *n)
{
if (n == NULL)
return;
struct node *c = n->right;
struct node *p = n->parent;
if (c->left != NULL)
c->left->parent = n;
n->right = c->left;
n->parent = c;
c->left = n;
c->parent = p;
if (p != NULL)
{
if (p->left == n)
p->left = c;
else
p->right = c;
}
}
static void rotate_right(struct node *n)
{
if (n == NULL)
return;
struct node *c = n->left;
struct node *p = n->parent;
n->left = c->right;
n->parent = c;
c->right = n;
c->parent = p;
if (p != NULL)
{
if (p->right == n)
p->right = c;
else
p->left = c;
}
}
다섯 번째 경우
부모 노드 P는 붉은색이지만 삼촌 노드 U는 검정색이고, 새로운 노드 N이 P의 왼쪽 자식 노드이고, P가 할아버지 노드 G의 왼쪽 자식 노드인 상황에서 G에 대해 오른쪽 회전을 한다.
회전의 결과 이전의 부모 노드였던 P는 새로운 노드 n과 할아버지 노드 G를 자식 노드로 갖는다. G가 이전에 검정색이었고, P는 붉은색일 수 밖에 없기 때문에 P와 G의 색을 반대로 바꾸면 레드-블랙 트리의 네 번째 속성(붉은색 노드의 두 자식 노드는 검정색 노드이다)을 만족한다.
레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)은 계속 유지되는데, 이는 이전에 P를 포함하는 경로는 모두 G를 지나게 되고, 바뀐 후 G를 포함하는 경로는 모두 P를 지나기 때문이다. 바뀌기 전에는 G가, 바뀐 후에는 P가 P, G, N 중 유일한 검정색 노드이다.
void Insert_case5(struct node *n)
{
if (n == NULL)
return;
n->parent->color = BLACK;
g->color = RED;
if (n == n->parent->left)
rotate_right(g);
else
rotate_left(g);
}
삽입 동작은 치환 작업인데, 이는 모든 호출이 tail recursion이기 때문이다.
Leave a comment