자료구조 구현 - C를 통한 이진 탐색 트리의 연산 구현

간단한 소개

이진 탐색 트리 (binary search tree)

이진탐색트리는 이진트리의 일종으로서, 다음과 같은 조건을 만족해야 한다.

• 왼쪽 서브트리의 모든 노드들은 부모 노드보다 작아야 한다.
• 오른쪽 서브트리의 모든 노드들은 부모 노드보다 커야 한다.
• 왼쪽과 오른쪽 서브트리도 이진탐색트리여야 한다.

즉, 이진탐색트리는 이진트리의 일종으로서 노드들의 값이 일정한 순서를 갖고 있으며, 이진탐색트리는 데이터를 정렬된 상태로 저장하고 탐색, 삽입, 삭제 등의 연산을 수행할 수 있다.

고로, 탐색 시간을 최소화하는 데에 유용한 자료구조이다. 시간복잡도 역시 O(log n)으로 매우 효율적이다.

이 글에서는 이진 탐색 트리에 대한 탐색 연산, 삽입 연산, 삭제 연산을 다룬다.

구현한 코드

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

typedef struct _Node 
{
    int data;
    struct _Node *left, *right;
} Node;

Node* create_node(Node *node, int data)
{
    node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* insert_node(Node *root, int data)
{
    if(root==NULL){
        return create_node(root, data);
    }
    else if(data < (*root).data){
        (*root).left = insert_node((*root).left, data);
    }
    else if(data > (*root).data){
        (*root).right = insert_node((*root).right, data);
    }
    return root;
}

Node* search_node(Node *root, int data)
{
	while (root!=NULL) {
        if(root->data==data){
            return root;
        }
        else if(data < root->data){
            return search_node(root->left, data);
        }
        else if(data > root->data){
            return search_node(root->right, data);
        }
        return root;
    }
    return NULL; //fail
}

Node* delete_node(Node *root, int data)
{
    if(root==NULL){
        return root;
    }
    else if(data < root->data){
        root->left = delete_node(root->left, data);
    }
    else if(data > root->data){
        root->right = delete_node(root->right, data);
    } else {
        if(root->left==NULL){
            Node *temp = root->right;
			free(root);
			return temp;
        }
        else if(root->right==NULL){
            Node *temp = root->left;
			free(root);
			return temp;
        }
        Node *temp = root->right;
        while(temp->left != NULL){
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }
    return root;
}

int main()
{
    Node *root = NULL;
    root = insert_node(root, 7);
    root = insert_node(root, 14);
    root = insert_node(root, 21);
    root = insert_node(root, 28);
    root = insert_node(root, 35);
    root = insert_node(root, 9);
    root = insert_node(root, 19);
    root = insert_node(root, 29);
    root = insert_node(root, 39);
    root = insert_node(root, 49);
    root = insert_node(root, 1);
    root = insert_node(root, 11);
    root = insert_node(root, 22);
    root = insert_node(root, 33);
    root = insert_node(root, 44);
    root = insert_node(root, 55);
    
    printf("삭제연산 테스트 용 인풋을 입력해보자. :");
    int inp;
    scanf("%d", &inp);

    if (search_node(root, inp)!=NULL) {
        printf("트리에서 %d를 찾았습니다. \n", inp);
    } else {
        printf("트리에 %d가 없습니다. \n", inp);
    }
    
    delete_node(root, inp);

    if (search_node(root, inp)!=NULL) {
        printf("트리에서 %d를 찾았습니다. \n", inp);
    } else {
        printf("트리에 %d가 없습니다. \n", inp);
    }

    return 0;
}

코드 읽기

구조체 Node 선언

typedef struct _Node 
{
    int data;
    struct _Node *left, *right;
} Node;

(저번에 그냥 이진트리를 구현할 때 TreeNode라고 했더니 뭔가 긴 것 같아서 이번엔 그냥 Node라고 했다...)
위 코드에서 트리의 한 노드를 뜻하는 구조체 ㅡNode 구조체를 정의해준다. 동시에 이를 Node라는 새로운 자료형으로 typedef 해주고 있다. typedef는 구조체를 새로운 자료형 이름으로 정의하는 역할을 하며, Node는 ㅡNode의 별명이라고 생각할 수 있다. 보수 관리의 효용을 위해 이런 식으로 typedef를 쓴다고 한다.

트리 노드의 삽입

Node* create_node(Node *node, int data)
{
    node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* insert_node(Node* root, int data)
{
    if(root==NULL){
        return create_node(root, data);
    }
    else if(data < root->data){
        root->left = insert_node(root->left, data);
    }
    else if(data > root->data){
        root->right = insert_node(root->right, data);
    }
    return root;
}

insert_node()를 먼저 보자.

새 노드를 삽입하려면 루트 노드부터 시작하여 삽입할 노드가 들어갈 위치를 찾아야 한다. 이를 위해서 insert_node 함수는 루트 노드부터 시작하여 data의 값이 현재 root의 data보다 크면 오른쪽, 작으면 왼쪽으로 쭉쭉 내려가며 계속해서 재귀적으로 호출되어진다.

함수의 실행 내내 변수 root가 사전적인 의미의 루트(루트 노드(root node) : 부모가 없는 노드. 한 트리는 하나의 루트 노드만을 가진다.)라고 생각하면 혼란스러울 수 있다. 이 함수는 재귀적으로 계속해서 자신의 root를 갱신하고 있으며, 함수의 실행 과정 속에서 변수 root란 현재 노드를 가리키는 포인터 변수가 된다. 지금 탐색의 대상이 되는 현재의 노드 root의 data 값이 아까 함수의 실행 시 매개변수로 입력받았던 data 값보다 크면 오른쪽, 작으면 왼쪽 자식을 탐색하러 내려간다.

위 코드블록은 이렇게 표현할 수도 있다. 화살표 연산자가 덜 익숙한 것인지, 개인적으로는 도트 연산자가 한 구조체와 그 맴버의 관계를 더 잘 가독할 수 있는 표기법인 것 같다...

Node* create_node(Node *node, int data)
{
    node = (Node*)malloc(sizeof(Node));
    (*node).data = data;
    (*node).left = NULL;
    (*node).right = NULL;
    return node;
}

Node* insert_node(Node* root, int data)
{
    if(root==NULL){
        return create_node(root, data);
    }
    else if(data < (*root).data){
        (*root).left = insert_node((*root).left, data);
    }
    else if(data > (*root).data){
        (*root).right = insert_node((*root).right, data);
    }
    return root;
}

만약 더 이상의 자식을 찾을 수 없다면, 즉 탐색하러 내려간 곳이 NULL이라면 이제 적절한 삽입 위치를 찾은 것이다. insert_node 함수는 여기서 새로운 루트 노드를 반환한다. 그리고 이 반환된 루트 노드를 다시 root 변수에 할당함으로써, 새로운 노드가 삽입된 이진탐색트리의 루트를 가리키도록 한다.

이쯤되서 main함수를 들여다 보자.

int main()
{
    Node *root = NULL;
    root = insert_node(root, 7);
    root = insert_node(root, 14);
    root = insert_node(root, 21);
    .
    .

방금 내가 insert_node 함수는 여기서 새로운 루트 노드를 반환하고, 이 반환된 루트 노드를 다시 root 변수에 할당함으로써, 새로운 노드가 삽입된 이진탐색트리의 루트를 가리키도록 한다고 했다. 바로root = insert_node(root, 숫자);라는 코드를 통해 새로운 노드가 삽입된 이진탐색트리의 루트를 root 변수에 다시 할당하여, 이진탐색트리의 루트를 업데이트하는 것이다.

다시 정리한다면
1. 트리의 첫 노드에 대한 생성일 때, 가장 먼저 insert_node() 의 if(root==NULL) 블록이 실행될 것이다. 아니라면 else if문 안의 코드들이 가장 먼저 실행될 것이다.
2. 만나는 노드들마다의 맴버 data 값을 비교해가며 더 이상의 자식을 찾을 수 없을 때까지 트리의 끝으로 내려간다.
3. 삽입 위치를 찾은 insert_node 함수는 여기서 새로운 루트 노드를 반환한다. 그리고 이 반환된 루트 노드를 다시 포인터 변수 root에 할당한다.

트리 내 노드 탐색

Node* search_node(Node* root, int data)
{
	while (root!=NULL) {
        if(root->data==data){
            return root;
        }
        else if(data < root->data){
            return search_node(root->left, data);
        }
        else if(data > root->data){
            return search_node(root->right, data);
        }
        return root;
    }
    return NULL; //fail
}
.
.
.
int main()
{
    printf("삭제연산 테스트용 인풋을 입력해보자. :");
    int inp;
    scanf("%d", &inp);

    if (search_node(root, inp)!=NULL) {
        printf("트리에서 %d를 찾았습니다. \n", inp);
    } else {
        printf("트리에 %d가 없습니다. \n", inp);
    }
    .
    .

어떤 숫자를 입력값으로 받는다. 그러면 해당 숫자를 맴버 data의 값으로 가지는 구조체 Node를, 트리의 루트부터 찾아 내려간다. 탐색하는 원리는 insert_node()와 같다.

입력받은 data 값과 일치하는 data 값을 가진 구조체를 만나면 해당 구조체, 즉 현재 탐색의 대상이 되는 Node를 가리키는 포인터 변수인 root를 return 해준다. 만약 해당 data 값을 가진 구조체를 끝까지 찾지 못하면, 즉 root==NULL이라면 while문을 빠져나와 NULL을 return 하게 된다.

트리 노드의 삭제

Node* delete_node(Node* root, int data)
{
    if(root==NULL){
        return root;
    }
    else if(data < root->data){
        root->left = delete_node(root->left, data);
    }
    else if(data > root->data){
        root->right = delete_node(root->right, data);
    } else {
        if(root->left==NULL){
            Node *temp = root->right;
			free(root);
			return temp;
        }
        else if(root->right==NULL){
            Node *temp = root->left;
			free(root);
			return temp;
        }
        Node *temp = root->right;
        while(temp->left != NULL){
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }
    return root;
}

트리의 삭제 연산은 언제나 복잡하다. 여러 경우의 수를 고려해야 하기 때문이다.

절차지향언어인 만큼 위에서부터 차례대로 하나하나 읽어보겠다....

1. root 노드가 NULL이면, 삭제할 노드가 애당초 존재하지 않으므로 NULL인 상태 그대로를 반환. (삭제 실패와 다름이 없으나 현재 우리의 코드 안에는 삭제 실패의 경우에 대한 수행은 없으므로...)

    if(root==NULL){
        return root;
    }

	else if(data < root->data){
        root->left = delete_node(root->left, data);
    }
    else if(data > root->data){
        root->right = delete_node(root->right, data);
    }

이제, 삭제할 노드의 데이터 값을 가진 노드를 찾아 나선 것이다. 현재 노드의 데이터 값보다 작으면, 현재 노드의 왼쪽 서브트리에서 삭제할 노드를 찾는다. 이를 위해 현재 노드의 left 포인터를 인자로 하여 delete_node() 함수를 재귀적으로 호출.
삭제할 노드의 데이터 값이 현재 노드의 데이터 값보다 크면, 현재 노드의 오른쪽 서브트리에서 삭제할 노드를 찾는다. 마찬가지로 이를 위해 현재 노드의 right 포인터를 인자로 하여 delete_node() 함수를 재귀적으로 호출.
3-1.

else {
        if(root->left==NULL){
            Node *temp = root->right;
			free(root);
			return temp;
        }
        else if(root->right==NULL){
            Node *temp = root->left;
			free(root);
			return temp;
        }
        .
        .

위의 과정을 거쳐 else문은 data == root->data 인 경우에 들어오게 된다. 즉, 삭제할 노드를 찾았을 때이다.

삭제할 목표 노드의 메모리를 free() 함수로 해제해준다. 삭제할 노드의 오른쪽 자식이 없다면 삭제할 노드의 왼쪽 서브트리 노드를, 삭제할 노드의 왼쪽 자식이 없다면 삭제할 노드의 오른쪽 서브트리 노드를 반환한다. 이렇게 되어 삭제해야 하는 노드가 삭제된다.
3-2.

else {  .
		.
        Node *temp = root->right;
        while(temp->left != NULL){
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }

삭제할 목표 노드가 왼쪽 오른쪽 모두 서브트리를 가진 경우이다.

삭제할 노드를 찾았는데 삭제할 노드의 왼쪽 오른쪽 노드 모두가 NULL이 아니면, 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 찾아 그 노드를 해당 노드의 값을 삭제할 노드로 대체할 것이다.

이진탐색트리의 노드 삭제에 대한 자세한 설명은 아래의 블로그가 도움이 되었다.
https://zeddios.tistory.com/492

즉, 한 노드는 자기 자신보다 값이 더 큰 숫자들만을 오른쪽 서브트리에 둘 수 있으므로, 자기 자신이 사라질 때에 자신의 오른쪽 서브트리에서 가장 작은 값이 그 삭제되는 노드의 위치로 오는 게 논리적으로 옳기 때문이다.

그리하여 오른쪽 자식 중에서 가장 작은 값을 우리가 삭제하고자 하는 노드의 자리로 옮긴 뒤, 원래 그 값을 가지고 있었던 노드를 삭제한다.

결과 출력