[C언어] RB 트리 구현(1) - 삽입

 

 

저번에 RB트리 개념에 대해 허접하게 정리했었는데요.

오늘은 C언어로 구현하는 방법에 대해 적어보겠습니다~

코드는 [Introduction to Algorithms] 의 13장 레드 블랙 트리 내용을 기반으로 작성했습니다!

 

 

 

먼저 사용할 구조체 등을 선언해줍니다.

레드, 블랙 속성을 표현하기 위해 enum color_t를 정의합니다.

key 값의 표현을 위해 typedef로 int형 key_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;

 

다음은 구조체 node_t와 rbtree 입니다.

각 노드는 color, key, 부모&왼쪽&오른쪽 노드 포인터까지 5가지 멤버를 갖고 있습니다.

rbtree는 루트 노드와 nil 노드를 갖고 있습니다.

 

* 여기서 nil 노드는 자식 노드가 없어 NULL을 가리켜야 하는 경우, 트리의 nil 노드를 가리키게 하기 위한 용도로 사용됩니다.

레드블랙트리는 leaf 노드가 Black이라는 속성을 갖고 있어야 하기 때문에 일반 이진 탐색 트리처럼 NULL을 가리킬 수가 없어 대신 Black 속성을 갖는 nil 노드를 가리키는 것 입니다. 이때, 모든 leaf 노드에 nil 노드를 위한 공간을 하나씩 할당하게 되면 메모리 공간을 너무 많이 차지하기 때문에 nil 노드를 가리켜야 할 경우는 속해있는 트리의 하나의 nil 노드를 가리켜 메모리를 절약합니다.

 

 

레드 블랙 트리 생성

rbtree *new_rbtree(void)
{
    rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
    node_t *nil = (node_t *)malloc(sizeof(node_t));
    p->root = nil;
    p->nil = nil;
    p->nil->color = RBTREE_BLACK;
    
    return p;
}

 

alloc 함수를 이용해 트리와 nil 노드의 메모리를 할당해줍니다~

아직 트리에 아무 노드도 존재하지 않기 때문에 root 노드가 nil을 가리키게 합니다.

또, p->nil 에 nil을 가리키게 하고, p->nil 의 색을 블랙으로 지정해줍니다. p->nil은 이후로 다른 노드를 가리킬 일이 없습니다.

 

 

레드 블랙 트리 삽입

node_t *rbtree_insert(rbtree *t, const key_t key)
{
    node_t *new = (node_t *)malloc(sizeof(node_t));
    node_t *y = t->nil;
    node_t *x = t->root;
    new->key = key;

    while (x != t->nil)
    { // x가 nil을 가리킬때까지 이진 탐색을 반복
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    // while이 끝났을 때는 x는 nil을, y는 그 부모를 가리킴

    new->parent = y;
    if (y == t->nil) // 반복이 끝났는데 y가 nil을 가리키면 트리가 비었다는 뜻
        t->root = new;
    else if (key < y->key)
        y->left = new;
    else
        y->right = new;

    new->left = t->nil;
    new->right = t->nil;
    new->color = RBTREE_RED;

    rbtree_insert_fixup(t, new); // 새로운 삽입으로 규칙 위반일 수 있으니 확인

    return t->root; // root가 바뀌었을 수 있으니 루트 반환
}

 

삽입 코드입니다~ 함수의 인자로 받아온 t 트리에 새로운 노드를 삽입하겠습니다.

삽입할 new 노드의 메모리를 할당해주고, 함수의 인자로 받아온 key 값을 new->key에 저장해줍니다.

 

x와 y는 트리를 탐색해 삽입할 위치를 찾을 때 사용합니다.

x는 t->root로 초기화하고 x를 기준으로 탐색을 진행합니다. x가 nil을 가리킬 때까지 while문을 반복해 이진 탐색을 반복하며 x의 값을 y에 저장합니다.

반복문이 종료된 후 y는 새로 삽입할 노드의 부모를 가리키게 됩니다.

new->parent에 y를 지정해주고, y가 nil을 가리킨다면 트리가 비었다는 의미이므로 new를 트리의 루트로 설정, 아니라면 위치에 맞게 y의 왼쪽 또는 오른쪽 자식으로 new를 지정해줍니다.

 

이후는 new 노드의 자식을 nil로 초기화, 색을 RED로 초기화합니다. 아시겠지만 새로 삽입되는 노드의 색은 RED로 고정됩니다.

 

노드를 새로 삽입했다면 레드블랙트리의 5가지 속성을 위반하지 않았는지 fixup 함수를 통해 확인합니다.

 

 

삽입 시 속성 위반 확인

void rbtree_insert_fixup(rbtree *t, node_t *z)
{
    node_t *y = NULL; // 삼촌 노드

    while (z->parent->color == RBTREE_RED)
    {
        if (z->parent == z->parent->parent->left) // 내 부모 노드가 할아버지 노드의 왼쪽 자식일때
        {
            y = z->parent->parent->right;
            if (y->color == RBTREE_RED) // 삼촌 노드의 색이 RED인 경우 1
            {
                z->parent->color = RBTREE_BLACK;
                y->color = RBTREE_BLACK;
                z->parent->parent->color = RBTREE_RED;
                z = z->parent->parent;
            }
            else{
                if (z == z->parent->right) // 삼촌 노드의 색이 BLACK이며, 삽입 노드가 부모의 오른쪽 자식인 경우 2
                {
                    z = z->parent;
                    rotate(t, z, LEFT);
                }
                z->parent->color = RBTREE_BLACK;  // 삽입 노드가 부모의 왼쪽 자식인 경우 3
                z->parent->parent->color = RBTREE_RED;
                rotate(t, z->parent->parent, RIGHT);
            }
        }
        else
        {
            y = z->parent->parent->left;
            if (y->color == RBTREE_RED) // 경우 1
            {
                z->parent->color = RBTREE_BLACK;
                y->color = RBTREE_BLACK;
                z->parent->parent->color = RBTREE_RED;
                z = z->parent->parent;
            }
            else{
                if (z == z->parent->left) // 경우 2
                {
                    z = z->parent;
                    rotate(t, z, RIGHT);
                }
                z->parent->color = RBTREE_BLACK; // 경우 3
                z->parent->parent->color = RBTREE_RED;
                rotate(t, z->parent->parent, LEFT);
            }
        }
    }

    t->root->color = RBTREE_BLACK;
}

 

새로 삽입한 노드가 속성을 위반시키지 않는 지 확인하는 코드입니다.

만약 부모 노드의 색이 BLACK이라면 속성을 위반하지 않기 때문에 반복문을 바로 빠져나옵니다.

부모 노드가 RED라면, 삼촌 노드의 색과 new 노드의 위치 등을 기준으로 세 가지 경우로 나누어 처리합니다.

 

경우 1) 삼촌의 색이 RED

먼저 할아버지 노드는 무조건 BLACK입니다.

삽입 시, 기존 트리는 속성을 만족한 상태라는 가정하에 있기 때문입니다.

부모&삼촌이 모두 RED인 경우, 부모&삼촌과 할아버지 노드의 색을 뒤바꿔주는 ReColoring이 발생합니다.

 

 

 

경우 2) 삼촌의 색이 BLACK & 자식이 꺾인 위치

'꺾였다' 라는 것이 어떤 의미인지 먼저 그림을 보겠습니다. 

왼쪽 트리는 할아버지/부모/자식이 쭉 펴져있는 모양새이죠.

오른쪽 트리는 할아버지/부모/자식이 부모를 기점으로 꺾인 모양입니다. 저런 오른쪽 트리의 모습을 '꺾였다'라고 표현했습니다.

꺾인 노드의 속성을 맞춰주려면 먼저 rotate를 통해 노드를 펴주는 작업을 해야 합니다.

 

여기서 rotate 함수를 살펴볼게요.

typedef enum { LEFT, RIGHT} rotate_flag;

node_t *rotate(rbtree *t, node_t *x, rotate_flag flag) // x 기준으로 회전
{ 
    node_t *y = flag ? x->left : x->right;
    node_t *temp_tree = flag ? y->right : y->left;
    flag ? (x->left = y->right) : (x->right = y->left);

    if (temp_tree != t->nil) // 옮길 서브트리가 있다면
        temp_tree->parent = x;  // 부모를 조정

    y->parent = x->parent;
    if (x->parent == t->nil)  // x의 부모가 없다면 == root
        t->root = y;
    else if (x == x->parent->left)  // 기존 x의 위치에 y를 등록
        x->parent->left = y;
    else
        x->parent->right = y;

    flag ? (y->right = x) : (y->left = x);  // y의 자식으로 x를 설정
    x->parent = y;

    return t->root;
}

 

위 rotate 함수는 insert와 erase fixup 함수에서 사용됩니다. 트리의 속성을 바르게 맞추기 위해 노드를 이리저리 돌려주기 위한 함수입니다. 원래 left_rotate와 right_rotate 함수 두 개를 각각 사용했는데, 조언을 듣고 하나로 합쳐보았습니다.

enum으로 LEFT, RIGHT를 정의하고, 입력받은 플래그에 따라 삼항연산자를 이용해 y와 temp_tree에게 알맞은 노드를 전해줬습니다.

x 기준 왼쪽으로 rotate                   y 기준 오른쪽으로 rotate

    x               y                       x               x
   / \             /                       / \             / \
  z   y    --->   x                       z   y    --->   z   a 
     /           / \                         /                 \
    a           z   a                       a                   y

간단하게 보면 위 그림같은 모습입니다~

 

경우 2)에서 rotate로 꺾인 노드를 해결하면 경우 3)으로 넘어갑니다.

 

 

경우 3)  삼촌의 색이 BLACK & 꺾이지 않은 상태

꺾이지 않은 상태라면 부모와 할아버지 노드의 색을 뒤바꾸고, 할아버지를 기준으로 rotate 합니다.

경우 3을 해결하고 난 최종 트리의 모습입니다~

 

다음은 삭제편으로 찾아오겠습니다!