레드-블랙 트리

2-3-4트리 역할이 가능한 이진 탐색 트리

레드 블랙 트리 테스트 예시 (전개도 참고)

레드-블랙 트리 삽입 연산 구현

#include <stdio.h>
#include <stdlib.h>

#define nil -99999
typedef struct TreeNode {
    int key;
    int color; // red:0, black:1 
    int root; // 루트 노드 파악 
    int size_field;
    struct TreeNode* left, * right;
}TreeNode;
typedef struct TreeNode* TreeNode_ptr;

// (현재 서브트리의 루트, 새로 삽입한 노드)
typedef struct set {
    TreeNode_ptr T;
    TreeNode_ptr new_node;
}set;
typedef struct set* set_ptr;

// 루트 노드 생성 (키 값은 초기화하지 않음) 
TreeNode_ptr init() {
    TreeNode_ptr T = (TreeNode_ptr)malloc(sizeof(TreeNode));
    T->root = 1;  // 루트 표시
    T->color = 1; // 루트의 색은 블랙 

    // nil 처리 
    T->left = (TreeNode_ptr)malloc(sizeof(TreeNode));
    T->right = (TreeNode_ptr)malloc(sizeof(TreeNode));
    T->left->key = T->right->key = nil;
    T->left->root = T->right->root = 0;
    T->left->color = T->right->color = 1; // nil은 항상 블랙 
    return T;
}

// 트리에 size_field(부분트리에 속한 노드의 개수) 부여
// postorder를 응용해서 제작함 
void get_size_field(TreeNode_ptr T) {
    if (T->key != nil) {
        get_size_field(T->left);
        get_size_field(T->right);
        if ((T->left->key == nil) && (T->right->key == nil)) // 잎 노드
            T->size_field = 1;
        else { // 내부 노드 
            if ((T->left->key != nil) && (T->right->key != nil))
                T->size_field = 1 + (T->left->size_field) + (T->right->size_field);
            else if ((T->left->key != nil) && (T->right->key == nil))
                T->size_field = 1 + (T->left->size_field);
            else
                T->size_field = 1 + (T->right->size_field);
        }
    }
}

// 이진 탐색 트리의 부모 탐색 (루트가 오면 NULL 반환, nil노드가 오면 nil노드 반환) 
// 순환 호출할 때 현재 노드를 같이 넘겨주면, 부모 노드를 받는 것이 됨 -> 값이 같으면 부모 노드 리턴 가능!
TreeNode_ptr search_parent_node(TreeNode_ptr T, int key, TreeNode_ptr parent) {
    if (T == NULL)
        return NULL;

    if (T->key == nil)
        return T;

    if (key == T->key)
        return parent;

    else if (key < T->key)
        return search_parent_node(T->left, key, T);
    else
        return search_parent_node(T->right, key, T);
}

// 이진 탐색 트리 전용 노드 생성 
TreeNode_ptr make_node(int key) {
    TreeNode_ptr tmp = (TreeNode_ptr)malloc(sizeof(TreeNode));
    tmp->key = key;
    tmp->color = 0;
    tmp->root = 0;

    // nil 처리 
    tmp->left = (TreeNode_ptr)malloc(sizeof(TreeNode));
    tmp->right = (TreeNode_ptr)malloc(sizeof(TreeNode));
    tmp->left->key = tmp->right->key = nil;
    tmp->left->root = tmp->right->root = 0;
    tmp->left->color = tmp->right->color = 1; // nil은 항상 블랙 
    return tmp;
}

// 이진 탐색 트리 삽입 (삽입한 노드를 반환) 
set_ptr insert_node(TreeNode_ptr T, int key, set_ptr s) {
    static int first = 1;
    TreeNode_ptr node = NULL; // 삽입할 노드 

    // 첫 번째 시도 <루트 노드 처리>
    if ((first--) == 1) {
        T->key = key;
        s->T = s->new_node = T;
        return s;
    }

    // n번째 시도 (n>1)
    if (T->key == nil) {
        node = make_node(key);
        s->T = s->new_node = node;
        return s;
    }
    if (key < T->key) {
        s = insert_node(T->left, key, s);
        T->left = s->T;
        s->T = T;
        return s;
    }
    else if (key > T->key) {
        s = insert_node(T->right, key, s);
        T->right = s->T;
        s->T = T;
        return s;
    }
    else { // 동일한 키는 허용하지 않음
        s->T = s->new_node = T;
        return s;
    }
}

// x의 부모 노드를 반환
TreeNode_ptr get_parent(TreeNode_ptr T, TreeNode_ptr x) {
    return search_parent_node(T, x->key, NULL); // x가 루트면 NULL 반환 
}

// x의 조부모 노드를 반환
TreeNode_ptr get_Gparent(TreeNode_ptr T, TreeNode_ptr x, TreeNode_ptr x_parent) {
    TreeNode_ptr x_Gparent = NULL;
    if (x_parent)
        x_Gparent = search_parent_node(T, x_parent->key, NULL);
    return x_Gparent;
}

// x의 삼촌 노드를 반환 
TreeNode_ptr get_uncle(TreeNode_ptr T, TreeNode_ptr x, TreeNode_ptr x_parent, TreeNode_ptr x_Gparent) {
    TreeNode_ptr x_uncle = NULL;
    if (x_Gparent) {
        x_uncle = x_Gparent->left;
        if (x_uncle == x_parent)
            x_uncle = x_Gparent->right;
    }
    return x_uncle;
}

// 지그재그 판별기
int zig_zag(TreeNode_ptr gp, TreeNode_ptr p, TreeNode_ptr x) {
    // [1] x가 왼쪽 자식인데 x_parent가 오른쪽 자식
    if (p->left == x && gp->right == p)
        return 1;
    // [2] x가 오른쪽 자식인데 x_parent가 왼쪽 자식
    else if (p->right == x && gp->left == p)
        return 2;
    else
        return 0;
}

// 지그지그 판별기
int zig_zig(TreeNode_ptr gp, TreeNode_ptr p, TreeNode_ptr x) {
    // [3] x가 왼쪽 자식인데 x_parent도 왼쪽 자식
    if (p->left == x && gp->left == p)
        return 3;
    // [4] x가 오른쪽 자식인데 x_parent도 오른쪽 자식
    else if (p->right == x && gp->right == p)
        return 4;
    else
        return 0;
}

// rotate_right
// RL과 LL인 상황에 쓰임 
TreeNode_ptr rotate_right(TreeNode_ptr parent) {
    TreeNode_ptr child = parent->left;
    parent->left = child->right; // child의 서브 트리 한 쪽을 parent가 가져감 
    child->right = parent; // 오른쪽 회전 
    return child;
}

// rotate_left
// LR과 RR인 상황에 쓰임 
TreeNode_ptr rotate_left(TreeNode_ptr parent) {
    TreeNode_ptr child = parent->right;
    parent->right = child->left; // child의 서브 트리 한 쪽을 parent가 가져감 
    child->left = parent; // 왼쪽 회전 
    return child;
}

// 레드 블랙 트리 삽입 
TreeNode_ptr rbt_insert_node(TreeNode_ptr T, int key, set_ptr s) {
    // 이진 탐색 트리에 key값을 가지는 노드 삽입 -> 삽입한 노드를 x로 받음 
    TreeNode_ptr x = insert_node(T, key, s)->new_node;

    // x노드의 부모 노드와 조부모 노드, 삼촌 노드를 정의
    TreeNode_ptr x_parent = get_parent(T, x);
    TreeNode_ptr x_Gparent = get_Gparent(T, x, x_parent);
    TreeNode_ptr x_uncle = get_uncle(T, x, x_parent, x_Gparent);

    x->color = 0;  // x의 색은 레드

    // x가 루트 노드가 아니고, 부모 노드의 색이 레드이면 
    while (!x->root && x_parent->color == 0) {
        // x의 삼촌 노드가 존재하고 
        if (x_uncle) {
            // <경우1> 삼촌 노드가 레드인 상황
            if (x_uncle->color == 0) {
                x_Gparent->color = 0;  // Gparent를 레드
                x_parent->color = x_uncle->color = 1; // parent와 uncle을 블랙 
                x = x_Gparent;

                // x노드의 부모 노드와 조부모 노드, 삼촌 노드를 재 정의
                x_parent = get_parent(T, x);
                x_Gparent = get_Gparent(T, x, x_parent);
                x_uncle = get_uncle(T, x, x_parent, x_Gparent);
            }
            else {
                int tmp = 0;
                T->root = 0;

                // <경우2> zig-zag인 상황: [1] (x가 왼쪽 자식인데 x_parent가 오른쪽 자식) or [2] (x가 오른쪽 자식인데 x_parent가 왼쪽 자식)
                if (tmp = zig_zag(x_Gparent, x_parent, x)) {

                    // [1] RL인 상황 -> rotate_right 진행 
                    if (tmp == 1)
                        x_Gparent->right = rotate_right(x_parent);

                    // [2] LR인 상황 -> rotate_left 진행 
                    else
                        x_Gparent->left = rotate_left(x_parent);

                    x = x_parent; 

                    // x노드의 부모 노드와 조부모 노드, 삼촌 노드를 재 정의
                    x_parent = get_parent(T, x);
                    x_Gparent = get_Gparent(T, x, x_parent);
                    x_uncle = get_uncle(T, x, x_parent, x_Gparent);
                }

                // <경우3> zig-zig인 상황: [3] (x가 왼쪽 자식인데 x_parent도 왼쪽 자식) or [4] (x가 오른쪽 자식인데 x_parent도 오른쪽 자식)
                tmp = zig_zig(x_Gparent, x_parent, x);
                TreeNode_ptr x_GGParent = search_parent_node(T, x_Gparent->key, NULL);

                // [3] LL인 상황 -> rotate_right 진행 
                if (tmp == 3) {
                    // 조부모의 부모 노드가 존재하면 회전 후 받은 루트를 해당 노드에 연결 
                    if (x_GGParent) {
                        if (x_GGParent->right == x_Gparent)
                            x_GGParent->right = rotate_right(x_Gparent);
                        else
                            x_GGParent->left = rotate_right(x_Gparent);
                    }
                    // 조부모의 부모 노드가 존재하지 않으면 회전 후 받은 루트를 트리의 루트로 지정  
                    else
                        T = rotate_right(x_Gparent);
                }

                // [4] RR인 상황 -> rotate_left 진행 
                else {
                    if (x_GGParent) {
                        // 조부모의 부모 노드가 존재하면 회전 후 받은 루트를 해당 노드에 연결 
                        if (x_GGParent->right == x_Gparent)
                            x_GGParent->right = rotate_left(x_Gparent);
                        else
                            x_GGParent->left = rotate_left(x_Gparent);
                    }
                    // 조부모의 부모 노드가 존재하지 않으면 회전 후 받은 루트를 트리의 루트로 지정  
                    else
                        T = rotate_left(x_Gparent);
                }

                x_Gparent->color = 0; // Gparent노드 레드 
                x_parent->color = 1; // parent노드 블랙
                T->root = 1;

                break;
            }
        }
    }

    T->color = 1; // 루트 노드의 색은 블랙 
    return T;
}

// 중위 순회 (정렬)
void inorder(TreeNode_ptr T) {
    if (T->key != nil) {
        inorder(T->left);
        printf("[ key: %d, ", T->key);
        printf("root: %d, ", T->root);
        printf("size_field: %d, ", T->size_field);
        if (T->color == 0)
            printf("color: red ]\n");
        else
            printf("color: black ]\n");
        inorder(T->right);
    }
}

// 레드 블랙 트리 연산 테스트 
int main() {
    // 세트 변수 s 정의 : 노드를 삽입했을 때, 삽입한 노드를 반환받기 위해 필요한 변수 
    set s;
    TreeNode_ptr T = init();

    // 삽입 테스트 
    T = rbt_insert_node(T, 5, &s);
    T = rbt_insert_node(T, 3, &s);
    T = rbt_insert_node(T, 20, &s);
    T = rbt_insert_node(T, 15, &s);
    T = rbt_insert_node(T, 25, &s);
    T = rbt_insert_node(T, 13, &s);
    T = rbt_insert_node(T, 18, &s);
    T = rbt_insert_node(T, 30, &s);
    T = rbt_insert_node(T, 17, &s);
    T = rbt_insert_node(T, 31, &s);
    T = rbt_insert_node(T, 33, &s);
    T = rbt_insert_node(T, 32, &s);
    T = rbt_insert_node(T, 34, &s);


    // 사이즈 필드 값 부여
    get_size_field(T);

    // 중위 순회하면서 검토 
    inorder(T);

    return 0;
}