[C언어와 친구들] 이진 탐색 트리 (BST)

이진탐색트리(Binary Search Tree, BST)란?

- 모든 원소는 유일한 키 값을 갖는다. (중복 내용을 갖는 항목은 없다.)
- 왼쪽 서브트리의 모든 원소들은 루트의 키보다 작은 값을 갖는다.
- 오른쪽 서브트리의 모든 원소드른 루트의 키보다 큰 값을 갖는다.
- 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다. (재귀적으로 정의)

 

이진 탐색 트리에서 3가지 연산: 탐색/삽입/삭제

1) 탐색

루트 노드를 주고서 우리가 찾고 싶은 x라는 key 값을 찾는다. search(root, x) x를 root 값부터 비교해가면서 root 보다 크면 오른쪽 서브 트리를, root 보다 작으면 왼쪽 서브트리를 방문한다. 만약 x가 roo값과 같으면 바로 root를 반환한다. 

 

search 함수를 만들어보자...!

이 때, search 함수의 반환형은 노드 구조체를 가리키는 포인터 형이다. 그래야 나중에 삽입/삭제 시에도 계속해서 이 search 함수를 갖다쓸 수 있다.

=> Node*

 

먼저, 인자로 준 root를 받아 내부에 root를 가리키는 구조체 포인터 p를 선언한다. 자식이 없는 노드는 양끝에 NULL을 달고 있으니 이 값이 NULL이 될 때까지, 즉 트리의 맨 끝에 방문할 때까지 우리가 찾고자 x와 방문하는 노드의 key 값을 비교해가며 계속 이동시킨다. p->key가 x값과 같으면 p를 반환하고, 그렇지 않으면 x와 key 값을 비교해 왼쪽 혹은 오른쪽 자식 노드로 p가 가리키는 노듸 위치를 옮긴다. 

Node* searchBST(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;
}

 

2) 삽입

자, 탐색을 했으니 이제 이진 탐색 트리에 노드를 삽입해볼 차례이다.

노드는 어디서 삽입해야할까? 여기서 고려할 점은 BST의 특징 중 하나인데 바로

'모든 원소는 유일한 키값을 갖는다. (중복 내용을 갖는 항목은 없다.)'

 

따라서, 새로운 노드를 삽입한다고 하면 이 새로운 노드의 키값은 반드시 기존 BST에 있지 않아야 한다. 그렇단말인즉슨, 기존 이진 탐색 트리를 탐색해서 새로운 노드에 대한 값을 찾으려고 한다면 탐색에 실패할 것이다. 근데 그 실패했다고 알리는 위치는 기존 이진 탐색 트리를 스캔하면서 새로운 노드가 들어가야하는 자리에 해당한다. 따라서, 탐색에 실패한 그 위치에다가 새로운 노드를 삽입하면 된다. 일단 기본적으로 탐색을 먼저 해야한다는 말이기 때문에 위에서 구현한 search 함수를 활용하면 된다.

 

search 함수와 동일하게 먼저, 인자로 준 root를 받아 내부에 root를 가리키는 구조체 포인터 p를 선언한다. 

탐색을 실패한 위치에 노드를 삽입하면 되기 때문에 p가 NULL이 되기 직전 노드를 알아내면 된다. p가 NULL 값을 받기 직전에 가리키던 노드 포인터를 저장해주면 되기 때문에 새로운 구조체 포인터 parent를 선언한다.  즉, p의 부모 노드라고 생각하면 된다. 

=> 요약 ✨✨✨

parent를 만드는 이유: p가 NULL까지 가게 될 경우 그 위의 노드가 무엇인지 보고 그 노드를 기준으로 삽입해야 하기에

 

while문이 종료될 때까지 search 함수는 새로운 노드를 기존 트리 값과 비교해가면서 새로운 노드가 위치해야할 장소까지 포인터를 이동할 것이다. 먼저, 그 상황에서 새로운 노드에 대한 메모리를 동적으로 할당한다.

// 이진 탐색 트리 노드 삽입
// 노드 삽입으로 구축해보기 => 탐색 실패 시에 실패한 위치에 노드를 삽입한다.
// p가 NULL이 된 순간에는 NULL값을 받기 직전에 가리키던 노드 포인터 => parent가 될 것
// p가 NULL이 된 순간에 그 때의 parent의 child로 새 노드를 붙임
Node* insertBST(Node* root, char x){ 
    Node* p = root;
    Node* parent = NULL; // p의 발자취를 따라가는 변수 => parent가 한 발짝도 못 갈 수 있음 => 그 때는 루트 자체에다가 새 노드 삽입 !
    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;
    }

    // 탐색 실패로 while문 빠져나왔을 때,
    // 1. 새 노드 할당: 아직 기존 트리에 붙이지는 않고 노드만 만들어둔 상황
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = x;
    newNode->left = newNode->right = NULL;

    // 2. parent의 자식으로 새 노드 붙이기: 왼쪽 자식에 붙일거냐, 오른쪽 자식에 붙일거냐? 
    if (parent != NULL){
        if (parent->key < newNode->key){
            parent->right = newNode;
        }
        else
            parent->left = newNode;

    }
    return newNode;
}

 

3) 삭제

삭제하려는 노드의 차수의 수에 따라 세 가지 경우를 분리시켜 코드를 작성한다. 

3-1) 차수가 0인 경우(= 자식노드가 0인 경우)

3-2) 차수가 1인 경우(= 자식노드가 1인 경우)

=> 차수가 0인 경우와 1인 경우는 소스코드의 주석을 참고하도록 하자.

 

3-3) 차수가 2인 경우(= 자식노드가 2인 경우)

최상위 노드인 루트 노드를 삭제한다고 가정을 하자.

왼쪽 서브트리 또는 오른쪽 서브트리에서 하나의 후계자를 골라서 10의 자리로 올리게 된다. 

 

- 왼쪽 서브트리에서의 후계자를 고른다면 ?

=> 왼쪽 서브 트리에서 가장 큰 값인 8이 후계자가 될 것

=> 왼쪽에서 가장 큰 노드를 골랐을 때 이 노드의 오른쪽 자식은 절대 없다.  Why? 당연히 오른쪽 자식이 더 큰 값이기에

- 오른쪽 서브트리에서의 후계자를 고른다면?

=> 오른쪽 서브트리에서의 가장 작은 값인 12가 후계자가 될 것

=> 오른쪽에서 가장 작은 노드를 골랐을 때 이 노드의 왼쪽 자식은 절대 없다.  Why? 당연히 왼쪽 자식이 더 작은 값이기에

 

만약 10이라는 노드를 삭제한다고 했을 때, 실제로는 10을 제거하지 않는다. 

실제적인 제거는 후계자 노드(12)를 제거한다.

[실제로 제거될 차수가 2인 노드(=10)]에 후계자 노드의 데이터 값(12)만 복사해준다.

데이터 값을 복사해준 뒤, 후계자 노드를 노드를 제거한 뒤 노드를 연결해주는 작업을 한다.

insert, delete 함수에서 p의 발자취를 따라가는 변수로 parent 변수를 사용했듯이

후계자 노드를 찾아갈 때도 역시 후계자의 parent 노드를 유지하면서 따라 간다. 

 

이진 탐색 트리 노드 삭제는 차수가 0~2의 경우를 나눈 것을 고려하고 코드를 보면 된다.

// 이진 탐색 트리 노드 삭제
// deleteBST의 반환 타입을 Node *로 해야하는 이유는 deleteBST 안에서 삭제가 되고 밑에 있는 노드가 위로 올라오게 될 수 있음, 새로운 루트 노드의 주소를 돌려줄 수 있게끔 루트노드의 주소를 돌려주도록 만듬
Node* deleteBST(Node* root, char x){ 
    Node* p = root;
    Node* parent = NULL;
    while ((p != NULL) && (p->key != x)){ // key를 만나거나 삭제할 게 없으면 while문 종료!
        parent = p;
        if (p->key == x){
            printf("같은 키가 있습니다.\n");
            return p;
        }
        else if (p->key < x){
            p = p->right;
        }
        else
            p = p ->left;
    }
    if (p==NULL){ // 삭제해야하는데 찾는 노드가 없으면 할 일이 없겠지 ?
        printf("찾는 노드가 없습니다.\n");
        return root;
    }

    // 차수가 0인 경우
    if (p->left == NULL && p->right == NULL){
        if (parent == NULL){  // 1) 현재 노드가 루트 노드이면서 차수가 0인 경우
            root = NULL; // 해당 노드가 루트 노드인 경우! 루트를 삭제
            // 트리 전체 노드가 한 개밖에 없는데 그것이 지워진 상황
        }
        else {  // 2) 현재 노드가 루트가 아닌데 차수가 0인 경우
            if (parent->left == p)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
    }
    // 차수가 1인 경우 => 이렇게 쓰면 0인 것도 들어올 수 있는데 차수가 0인 케이스는 위에서 걸러짐
    else if (p->left == NULL || p->right == NULL){
        Node *child = (p->left != NULL) ? p->left : p->right;
        if (parent == NULL){ // 1) 현재 노드가 루트 노드이면서 차수가 1인 경우 => 자식 하나가 새로운 노드가 됨
            root = child;
        }
        else {  // 2) 현재 노드가 루트가 아닌데 차수가 1인 경우
            if (parent->left == p)
                parent->left = child;
            else
                parent->right = child;
        }
    }
    // 차수가 2인 경우 => 후계자를 찾으러 떠나야 하니깐 succ_parent, succ를 만드는 것!
    else {
        Node* succ_parent = p;  // 후계자의 parent 노드를 유지하면서 따라간다.
        Node* succ = p->right;   // 후계자를 오른쪽 서브트리에서 찾으려고 하니 p->right
        while (succ->left != NULL){
            succ_parent = succ; // succ_parent는 현재 succ를 가리키게 하고
            succ = succ->left; // succ는 왼쪽 자식 노드를 가리키게 옮김
        }
        p->key = succ->key;
        if (succ_parent->left == succ){
            succ_parent->left = succ->right;
        }
        else
            succ_parent->right = succ->right;
        p = succ;
    }

    free(p);
    return root; // 위 과정을 통해 값이 바뀌었을 수 있으니 root를 반환
}

 

RBtree... 가자...!!!

 

공부 참고)

[자료구조] 이진 탐색 트리 : 개념과 구현(C언어): https://www.youtube.com/watch?v=ESqeK-ACHkU 

이진 탐색 트리 설명 참고