레드-블랙 트리

용어

레드-블랙 트리는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다. 이진 트리에서는 각각의 자료는 '노드(node, 분기점)'에 저장이 된다. 자료를 트리 구조로 저장할 때, 노드들 중 최상위에 있는 노드를 루트 노드(root node)라고 부른다. 이진 트리에서 노드는 최대 두 개의 자식 노드를 가질 수 있다. 각각의 자식 노드도 역시 최대 두 개의 자식 노드를 가질 수 있으며, 이런식으로 계속 연결된다. 그러므로, 어떤 트리도 루트 노드로부터 그 트리에 속한 모든 노드에 도달할 수 있다.
어떤 노드에 자식 노드가 없다면, 그 노드를 리프 노드(leaf node)라고 부르는데, 말 그대로 트리의 맨 가장자리에 있기 때문이다. 트리의 노드 중 하나를 루트 노드로 하고 그 자신과 자식 노드들로 이루어진 트리도 동일하게 트리 구조를 가지는데, 이를 부분 트리(sub-tree)라고 한다. 레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다.
레드-블랙 트리를 포함한 이진 탐색 트리는, 모든 노드에 대해 '자신이 가진 자료는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고, 자신보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다' 라는 조건을 만족한다. 이런 특성 때문에 특정 값을 빠르게 찾아 낼 수 있으며, 각 구성원소(elements)간의 효율적인 in-order traversal이 가능하다.

용도와 장점

레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.
AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전(rotations)이 필요하다.
레드-블랙 트리는 함수형 프로그래밍에서 특히 유용한데, 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합(set)등을 내부적으로 레드-블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O(log n)만큼의 시간이 필요하다.
레드-블랙 트리는 2-3-4 트리와 등장변환이 가능하다(isometry). 다시 말해서, 모든 2-3-4 트리에는 구성 원소와 그 순서(order)가 같은 레드-블랙 트리가 최소한 하나 이상 존재한다는 말이다. 2-3-4 트리에서의 삽입, 삭제 과정은 레드-블랙 트리에서의 색 전환(color-flipping)과 회전(rotation)과 같은 개념이다. 그러므로 실제로는 잘 쓰이지 않지만 2-3-4 트리는 레드-블랙 트리의 동작 과정(logic)을 이해하는 데 많은 도움을 주기 때문에 많은 알고리즘 교과서들이 레드-블랙 트리가 나오기 바로 전에 2-3-4 트리를 소개하고 있다.

동작

레드-블랙 트리의 읽기 전용(read-only) 동작(탐색 등)은 이진 탐색 트리의 읽기 전용 동작의 구현을 변경하지 않아도 되는데, 이는 레드-블랙 트리가 이진 탐색 트리의 특수한 한 형태이기 때문이다. 그러나 삽입(insertion)과 삭제(removal)의 경우 이진 탐색 트리의 구현에 따른 동작만으로는 레드-블랙 트리의 특성을 만족하지 못한다. 다시 레드-블랙 트리의 특성을 만족하게 만들기 위해서는 O(log n) 또는 amortized O(1)번의 색 변환과(실제로는 매우 빨리 이루어진다) 최대 3회의 트리 회전(tree rotation)이 필요하다(삽입의 경우 2회). 삽입과 삭제는 복잡한 동작이지만, 그 복잡도는 여전히 O(log n)이다.

첫 번째 경우

N 이라고 하는 새로운 노드가 트리의 시작(root)에 위치한다. 이 경우, 레드-블랙 트리의 첫 번째 속성(트리의 시작은 검정색이다)을 만족하기 위해서, N을 검정색으로 표시한다. 이 경우, 시작점으로부터 뻗어나가는 모든 경로에 검정색 노드를 하나 추가한 셈이 되기 때문에 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)은 여전히 유효하다.
void insert_case1(struct node *n){
    if (n->parent == NULL)
        n->color = BLACK;
    else
        insert_case2(n);}

네 번째 경우

부모 노드 P가 붉은색인데, 삼촌 노드 U는 검정색이다; 또한 새로운 노드 N은 P의 오른쪽 자식 노드이며, P는 할아버지 노드 G의 왼쪽 자식 노드이다. 이 경우, N과 P의 역할을 변경하기 위해서 왼쪽 회전을 한다; 그 후, 부모 노드였던 P를 다섯 번째 경우에서 처리하게 되는데, 이는 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식은 검정색 노드이다)을 아직 만족하지 않기 때문이다. 회전 작업은 몇몇 경로들 이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)을 위반하지 않는다.
void insert_case4(struct node *n){
    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){
    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){
    struct node *c = n->left;
    struct node *p = n->parent;

    if (c->right != NULL)
        c->right->parent = n;

    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){
    struct node *g = grandparent(n);

    n->parent->color = BLACK;
    g->color = RED;
    if (n == n->parent->left)
        rotate_right(g);
    else
        rotate_left(g);}
삽입 동작은 치환 작업인데, 이는 모든 호출(call)이 tail recursion이기 때문이다.

병렬 알고리즘 (Parallel algorithms)

아이템의 수에 비례하여 컴퓨터 프로세서를 이용할 수 있다면, 정렬되어 있는 아이템을 가지고 레드-블랙 트리를 만드는 병렬 알고리즘은 상수시간이나 시간으로 구현될 수 있다. 빠른 검색, 삽입, 삭제를 위한 병렬 알고리즘 또한 알려져 있다.