Red-Black Tree (1) 이진 탐색 트리

이후띵·2021년 12월 3일
RB-Treec언어이진탐색트리
0

RB Tree

목록 보기
1/5
post-thumbnail

Red-Black Tree를 구현하기 위해 이진 탐색 트리를 먼저 공부해야 겠다고 생각이 들었다. 이진 탐색트리를 공부한 후에, self-balancing 과정(left-rotation, right-rotation, color Promotion, color Demotion...)에서 발생하는 여러 경우의수를 고려하여 RB-Tree를 구현하는 것을 목표로 삼았다.

이진 탐색 트리

  • 모든 원소는 유일한 키 값을 갖는다.
  • 왼쪽(오른쪽#) 서브트리의 모든 원소들은 루트의 키보다 작은(큰#) 값을 갖는다.
  • 왼쪽, 오른쪽 서브트리도 이진탐색트리이다. (재귀적인 정의)

모든 서브트리에 대해서 이상의 조건들이 만족하여야 한다. (재귀)
즉, 이 트리 안에 어떤 노드를 루트 노드로 잡던지 이 조건들이 항상 true 가 된다.

위의 이진 탐색 트리로 중위순회(in-order traversal)을 하면?

  • 4 - 6 - 8 - 10 - 12 - 14 - 15 - 20 (오름차순)

이진 탐색 트리에서 중위순회를 하면, 오름차순으로 정렬이 된다.

이진 탐색 트리의 구현(C언어)

(1) 구조체 생성

typedef struct _Node {
    char key;
    struct _Node* left;
    struct _Node* right;
} Node;

(2) search 함수

  • x 와 일치하는 key가 나올 때까지 이진탐색.
  • 안나오면 return NULL, 나오면 return node
Node* search(Node* root, char x) {
    Node* p = root;
    while (p != NULL) {
        if (p -> key == x)
            return p;
        else if (p -> key < x)
            p = p -> right;
        else
            p = p -> left;
    }
    return NULL;
}

(3) insert 함수

key 값 = x
(같은 키가 있으면, 삽입하지 않도록 되어있다.)

진행 순서.

  • key 값이 들어갈 위치 탐색
  • 새롭게 만들어질 노드에 동적 메모리 할당 (malloc)
  • 새로운 노드에 key = x, left = NULL, right = NULL 입력.
  • 부모 노드가 있을 때, key 값을 비교하여 적절한 위치에 연결.
Node* insert(Node* root, char x){
    Node* p = root;
    Node* parent = NULL;
    while (p != NULL) {
        parent = p;
        if (p -> key == x){
            printf("같은 키가 있습니다. \n");
            return p;
        }
        else if (p -> key < x)
            p = p -> right;
        else
            p = p -> left;
    }
    // 새 노드 할당
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode -> key = x;
    newNode -> left = newNode -> right = NULL;
    // parent 의 자식으로 새 노드 붙이기
    if (parent != NULL) { // 맨처음 삽입하는 상황일 수도 있어서? (루트노드 삽입시?)
        if (parent -> key < newNode -> key){
            parent -> right = newNode;
        }
        else {
            parent -> left = newNode;
        }
    }
    return newNode;
}

(4) delete 함수

Node* delete(Node* root, char x){
    Node* p = root;
    Node* parent = NULL;
    while ((p != NULL) && (p -> key != x)) {
        parent = p;
        if (p -> key < x){
            p = p -> right;
        }
        else
            p = p -> left;
    }
    if (p == NULL) {
        printf("찾는 노드가 없습니다. \n");
        return root;
    }

    if (p -> left == NULL && p -> right == NULL) { // 차수가 0
        if (parent == NULL) // 차수가 0(자식 x), 부모노드x (루트노드 하나만 있을 때)
            root = NULL;
        else {
            if (parent -> left == p) // 자식이 없으면서, 자신이 왼쪽 노드일 때.
                parent -> left = NULL;
            else // 자식이 없으면서, 자신이 오른쪽 노드일 때.
                parent -> right = NULL;
        }
    }
    else if (p -> left == NULL || p -> right == NULL){ // 차수가 1
        Node *child = (p -> left != NULL) ? p -> left : p -> right; // 차수가 1일 때, 자식의 노드를 child 변수가 참조함.
        if (parent == NULL){
            root = child; // 자식이 1명인데 부모가 없으므로, 루트 노드를 삭제하는 중이었다는 뜻이니까 자식을 루트로 둔다.
        }
        else{
            if (parent -> left == p){ // 자신이 부모 노드의 왼쪽 자식 이었으면, 그 자리에 본인이 드감.
                parent -> left = child;
            }else{ // 오른쪽 자식이었으면 부모노드의 오른쪽 자식에 (지금 내자리) 외동딸로 등록.
                parent -> right = child;
            }
        }
    }
    else{ // 차수가 2
        Node * succ_parent = p;  // 지울 놈.
        Node* succ = p -> right;  // 지울 놈의 오른쪽 자식의 왼쪽 노드를 쭉 타고 들어가서(Null 만날때까지) 그놈을 지울 놈자리에 앉혀야 한다.
        while (succ -> left != NULL) {
            succ_parent = succ;
            succ = succ -> left;
        }
        p -> key = succ -> key;
        if (succ_parent -> left == succ){
            succ_parent -> left = succ -> right;
        }else{
            succ_parent -> right = succ -> right;
        }
        p = succ; // succ사용후 메모리 반환을 위한 저장.
    }

    free(p);
    return 0;
}

(5) 중위 순회(in-order traversal) 함수 : 이진 트리구조를 확인해보기 위한 간단한 함수

void inorder(Node* root){
    if (root == NULL){
        return;
    }
    inorder(root -> left);
    printf("%c", root -> key);
    inorder(root -> right);
}

전체 코드.

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

// typedef char data;
typedef struct _Node {
    char key;
    struct _Node* left;
    struct _Node* right;
} Node;

Node* search(Node* root, char x) {
    Node* p = root;
    while (p != NULL) {
        if (p -> key == x)
            return p;
        else if (p -> key < x)
            p = p -> right;
        else
            p = p -> left;
    }
    return NULL;
}
Node* insert(Node* root, char x){
    Node* p = root;
    Node* parent = NULL;
    while (p != NULL) {
        parent = p;
        if (p -> key == x){
            printf("같은 키가 있습니다. \n");
            return p;
        }
        else if (p -> key < x)
            p = p -> right;
        else
            p = p -> left;
    }
    // 새 노드 할당
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode -> key = x;
    newNode -> left = newNode -> right = NULL;
    // parent 의 자식으로 새 노드 붙이기
    if (parent != NULL) { // 맨처음 삽입하는 상황일 수도 있어서 (루트노드 삽입시)
        if (parent -> key < newNode -> key){
            parent -> right = newNode;
        }
        else {
            parent -> left = newNode;
        }
    }
    return newNode;
}
Node* delete(Node* root, char x){
    Node* p = root;
    Node* parent = NULL;
    while ((p != NULL) && (p -> key != x)) {
        parent = p;
        if (p -> key < x){
            p = p -> right;
        }
        else
            p = p -> left;
    }
    if (p == NULL) {
        printf("찾는 노드가 없습니다. \n");
        return root;
    }

    if (p -> left == NULL && p -> right == NULL) { // 차수가 0
        if (parent == NULL) // 차수가 0(자식 x), 부모노드x (루트노드 하나만 있을 때)
            root = NULL;
        else {
            if (parent -> left == p) // 자식이 없으면서, 자신이 왼쪽 노드일 때.
                parent -> left = NULL;
            else // 자식이 없으면서, 자신이 오른쪽 노드일 때.
                parent -> right = NULL;
        }
    }
    else if (p -> left == NULL || p -> right == NULL){ // 차수가 1
        Node *child = (p -> left != NULL) ? p -> left : p -> right; // 차수가 1일 때, 자식의 노드를 child 변수가 참조함.
        if (parent == NULL){
            root = child; // 자식이 1명인데 부모가 없으므로, 루트 노드를 삭제하는 중이었다는 뜻이니까 자식을 루트로 둔다.
        }
        else{
            if (parent -> left == p){ // 자신이 부모 노드의 왼쪽 자식 이었으면, 그 자리에 본인이 드감.
                parent -> left = child;
            }else{ // 오른쪽 자식이었으면 부모노드의 오른쪽 자식에 (지금 내자리) 외동딸로 등록.
                parent -> right = child;
            }
        }
    }
    else{ // 차수가 2
        Node * succ_parent = p;  // 지울 놈.
        Node* succ = p -> right;  // 지울 놈의 오른쪽 자식의 왼쪽 노드를 쭉 타고 들어가서(Null 만날때까지) 그놈을 지울 놈자리에 앉혀야 한다.
        while (succ -> left != NULL) {
            succ_parent = succ;
            succ = succ -> left;
        }
        p -> key = succ -> key;
        if (succ_parent -> left == succ){
            succ_parent -> left = succ -> right;
        }else{
            succ_parent -> right = succ -> right;
        }
        p = succ; // free(p)를 통해 놓아주기 위해 설정.
    }

    free(p);
    return 0;
}
void inorder(Node* root){
    if (root == NULL){
        return;
    }
    inorder(root -> left);
    printf("%c", root -> key);
    inorder(root -> right);
}
int main(){
    Node *root = insert(NULL, 'D');
    insert(root, 'B');
    insert(root, 'A');
    insert(root, 'E');
    insert(root, 'C');
    insert(root, 'F');
    inorder(root); printf("\n");
    return 0;
}

삽입 : D(root), B, A, E, C, F
중위 순회시 출력 결과 : ABCDEF

오름차순으로 잘 출력된다.

profile
이후띵
이후띵's 개발일지
다음 포스트

Red-Black Tree (2) 정리 - 이해하기

0개의 댓글