[2기 수원 곽지혜] Red Black Tree

레드블랙트리

 

레드블랙트리는 균형을 이룬 이진 탐색트리로써, 연관배열등을 구현하는데 쓰이는 자료구조입니다. 숫자 등의 비교 가능한 자료를 정리하는 데 쓰입니다. 레드블랙트리는 복잡한 자료구조이지만, 사용에 있어 효율적이고 우수한 실행시간을 보입니다. 트리에 n개의 원소가 있을 때 O(log n)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있습니다.

 

 

 

레드블랙트리의 용어

1) root node - 다른 어떤 노드의 Child 노드가 될수 없고, 최대 두개의 Child 노드를 가질 수 있습니다.

2) leaf node - 어떤 노드에 자식노드가 없다면 leaf node라고 부릅니다. 그리고 여기서 leaf node는 NULL이라 가정합니다. 즉, 자료를 가지고 있지 않습니다.

3) data - 레드블랙트리도 이진 탐색 트리에 속하기 때문에 모든 노드에 대해 자신이 가진 자료는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 data에 대해서 작거나 같고, 왼쪽에 위치한 부분트리가 가지고 있는 모든 data에 대해서 크거나 같은 조건을 만족 합니다. 

이런 특성으로 특정 값을 빠르게 찾아 낼 수 있고, 각 Element간의 효율적인 in-order traversal이 가능합니다.

 

 

 

레드블랙트리의 특성

레드블랙트리는 각 노드가 레드나 블랙인 색상 속성을 가진 이진 탐색트리 입니다. 이진 탐색트리의 특성에서 아래의 조건을 만족할 때, 레드블랙트리라고 할 수 있습니다.

 

1) node는 red 혹은 black 중의 하나이다.(A node is either red or black)

2) root node는 black 이다.(The root is black.)

3) 모든 leaf node는 black이다.

    (All leaves are black. The leaves are the NIL children.) 

    ※ 모든 tree는 2진 tree이며 NIL을 leaf node로 본다.

4) node가 red이면 그 자식은 반드시 black이다. 

    한편 black node만이 red node의 부모 node가 될 수 있다.

    (Both children of every red node are black. 

     Therefore, a black node is the only possible parent for a red node.)

5) 어떤 node로부터 시작되어 leaf node에 도달하는 모든 경로에는 

     leaf node를 제외하면 모두 작은 개수의 블랙 노드가 있다.

     (Every simple path from a node to a descendant leaf contains 

      the same number of black nodes. Not counting the leaf node

 

 

위 조건들을 만족하게 되면, 레드블랙트리는 가장 중요한 특성을 나타냅니다. '루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다.'라는 특성입니다. 다시 말해서 레드블랙트리는 균형이 잡혀 있다고 할 수 있고, 삽입, 삭제, 검색시 최악의 경우에서의 시간복잡도가 트리의 높이에 따라 결정되기 때문에 보통의 이진 검색 트리에 비해 효율적입니다. 그 이유는 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 점입니다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 되고, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두배 이상이 될 수 없습니다.

 

보통의 트리와는 다르게 레드블랙트리는 "nil leaves" 나 "null leaves"를 사용하는데, 이 "null leaf"는 자료를 가지고 있지 않으며, 트리의 끝을 나타내는 데만 쓰입니다. 그림으로 표현할 때, "null leaf"를 생략하고 그리는 경우가 많은데, 그렇게 되면 그림상으로는 레드-블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있지만 실제로는 그렇지 않습니다. 모든 노드들은 하나 또는 두개의 자식이 "null leaf" 일지라도, 두개의 자식을 가지고 있는 것입니다.

 

 

 

레드블랙트리의 삽입

 

삽입에 대해 설명하기전에 몇가지 용어에 대해 간략히 설명하자면, 삽입하는 원소를 N이라고 하고 부모노드를 P 할아버지 노드는 G라고 표기하고 삼촌 노드는 U라고 표기 합니다. 부모와의 관계는 레벨의 차이이고, 삼촌노드는 부모와 같은 레벨에 있는 노드이며, 할아버지와의 관계는 레벨 차이가 2인 노드입니다. 

 

삽입하는 케이스는 총 5가지 입니다.

1) 루트노드는 블랙

2) 추가노드는 레드

3) 부모 노드와 삼촌노드 모두 레드라면, 부모와 삼촌은 블랙이되고, 할아버지 노드는 레드가 됩니다. 이때, 할아버지 노드가 루트노드일 경우 블랙

4) 부모노드가 레드일때, 삼촌노드는 블랙인 경우 삽입 노드는 부모의 오른쪽 자식노드이고, 부모는 할아버지 노드의 왼쪽 자식노드일때, 왼쪽회전을 한 후 위의 조건에 맞는 케이스를 반복합니다.

5) 4와 같은 조건에서 새로운 노드는 부모의 왼쪽 자식노드이고, 부모는 할아버지 노드의 왼쪽 자식노드일 경우, 오른쪽 회전을 하고, 위의 조건에 맞는 케이스를 반복합니다.

 

위의 내용을 토대로 C코드를 작성해 보겠습니다.

먼저 부모와 자식은 바로 접근할 수 있지만 할아버지 노드와 삼촌노드를 접근하기 위해서는 연산이 필요하기에 함수로 정의한 후 사용합니다.

 

node grandparent(node n) {

    return n->parent->parent;

}

 

node uncle(node n) {

    if (n->parent == grandparent(n)->left)

        return grandparent(n)->right;

    else

        return grandparent(n)->left;

}

 

각 경우별로 함수를 작성해보면,

 

void insert_case1(node n) {

    if (n->parent == NULL)

        n->color = BLACK;

    else

        insert_case2(n);

}

 

void insert_case2(node n) {

    if (n->parent->color == BLACK)

        return; /* Tree is still valid */

    else

        insert_case3(n);

}

 

void insert_case3(node n) {

    if (uncle(n) != NULL && uncle(n)->color == RED) {

        n->parent->color = BLACK;

        uncle(n)->color = BLACK;

        grandparent(n)->color = RED;

        insert_case1(grandparent(n));

    }

    else

        insert_case4(n);

}

 

void insert_case4(node n) {

    if (n == n->parent->right && n->parent == grandparent(n)->left) {

        rotate_left(n->parent);

        n = n->left;

    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {

        rotate_right(n->parent);

        n = n->right;

    }

    insert_case5(n);

}

 

void insert_case5(node n) {

    n->parent->color = BLACK;

    grandparent(n)->color = RED;

    if (n == n->parent->left && n->parent == grandparent(n)->left) {

        rotate_right(grandparent(n));

    } else {

        /* Here, n == n->parent->right && n->parent == grandparent(n)->right */

        rotate_left(grandparent(n));

    }

}

 

rotate함수에 대해서 간단하게 작성해보면 아래와같이 적용할 수 있습니다.

void rotate_left(node n) {

           node l = n->left;

           n->left = l->right;

           l->right = n;

}

 

void rotate_right(node n) {

           node r = n->right;

           n->right = r->left;

           r->left = r;

}

Reference – 관련링크

도서 + 쉽게 배우는 알고리즘(관계중심의 사고법) / 문병로  

위키피디아 + http://en.wikipedia.org/wiki/Red%E2%80%93black_tree