이진 탐색 트리(Binary Search Tree)

데이터를 찾아보자!

이번에는 이진 탐색(Binary Search)이 적용된 이진 트리(Binary Tree)에 대해서 알아볼 것입니다. 이진 트리(Binary Tree)에 대해 더 상세한 설명을 보고싶으시면 아래 링크를 방문하여 이진 트리에 대한 설명을 읽어보시기 바랍니다.

이진 트리(Binary Tree)

우리가 알고 있는 이진 트리는 자식 노드가 최대 두 개의 노드를 지니고, 네 가지 성질을 지닙니다. 자식 노드가 아에 없거나, 왼쪽 자식 노드 혹은 오른쪽 자식 노드 하나만 존재하거나, 왼쪽과 오른쪽 자식 노드를 모두 지니는 경우입니다. 그렇다면, 우리가 배우게 될 이진 탐색 트리는 어떻게 자라야 할까요? 가장 핵심은 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 커야한다는 것입니다. 예를 들어서, 아래와 같이 트리가 자라야 되겠죠?

만약에 14라는 데이터를 찾으려 한다면, 루트 노드의 값인 10보다 크므로 오른쪽 자식 노드인 17과 비교를 하게됩니다. 그런데 이 17이란 값보다 작기 때문에 왼쪽 자식 노드를 살펴봅니다. 그리고 찾으려는 값과 일치하는지 비교를 하게 되는데, 왼쪽 자식 노드가 가지고 있는 값이 14이므로 탐색을 종료합니다. 이 경우는 찾으려는 데이터가 트리 내에 존재하는 경우이고, 만약 찾으려는 데이터가 없다면 어떻게 될까요? 예를 들어, 16이란 데이터를 찾는다고 생각해봅시다.

우선 찾으려는 값은 루트 노드의 값인 10보다 크므로 오른쪽 서브트리를 살펴봅니다. 오른쪽 자식 노드의 값은 17이고, 찾으려는 값보다 크므로 왼쪽 자식 노드를 방문합니다. 그런데 왼쪽 자식 노드인 14는 아무런 자식 노드를 지니고 있지 않습니다. 자식 노드가 없으므로 오른쪽 자식 노드를 방문한다고 해도 NULL일 뿐입니다. 한번, 이진 탐색 트리에서의 탐색 알고리즘을 보도록 합시다.

Node* searchNode(Node* Tree, int findData)
{
    // Tree가 비어있다면 NULL을 반환한다.
    if (Tree == NULL) return NULL;
    // 데이터를 만약 찾았다면, 해당 노드의 주소를 반환한다.
    if (Tree->Data == findData)
        return Tree;
    // 찾으려는 데이터가 현재 노드의 데이터보다 작다면, 왼쪽 자식 노드에서 탐색을 다시 시작한다.
    else if (Tree->Data > findData)
        searchNode(Tree->Left, findData);
    // 찾으려는 데이터가 현재 노드의 데이터보다 크다면, 오른쪽 자식 노드에서 탐색을 다시 시작한다.
    else
        searchNode(Tree->Right, findData);
}

위의 searchNode 함수는 데이터를 찾으면 그 노드의 주소값을 반환하고, 찾으려는 노드가 작다면 왼쪽 자식 노드에서 탐색을, 반대로 크다면 오른쪽 자식 노드에서 탐색을 다시 시작합니다. 이번에는, 이진 탐색 트리에서 삽입(Insert) 알고리즘을 한번 봐보도록 합시다.

void insertNode(Node* Tree, Node* newNode)
{
     if (newNode->Data > Tree->Data) // 새로 삽입되는 노드의 값이 현재 노드의 값보다 크다면
     {
         // 현재 노드의 오른쪽 자식 노드가 존재하는 경우, 오른쪽 자식 노드에서 삽입을 다시 시작한다.
         if (Tree->Right != NULL) insertNode(Tree->Right, newNode);
         // 현재 노드의 오른쪽 자식 노드가 비어있는 경우, 오른쪽 자식 노드는 새로 추가되는 노드가 들어간다.
         else Tree->Right = newNode;
     }
     else if (newNode->Data < Tree->Data) // 새로 삽입되는 노드의 값이 현재 노드보다 작다면
     {
         // 현재 노드의 왼쪽 자식 노드가 존재하는 경우, 왼쪽 자식 노드에서 삽입을 다시 시작한다.
         if (Tree->Left != NULL) insertNode(Tree->Left, newNode);
         // 현재 노드의 왼쪽 자식 노드가 비어있는 경우, 왼쪽 자식 노드는 새로 추가되는 노드가 들어간다.
         else Tree->Left = newNode;
     }
}

삽입 과정도 탐색 과정과 같이 간단해보이죠? 단지, 이진 탐색 트리의 핵심인 “크면 오른쪽! 작으면 왼쪽!”만 기억해도 어느정도 이해할 수 있는 부분입니다. 마지막으로는, 이진 탐색 트리에서 제거(Remove) 알고리즘을 한번 봐보도록 합시다.

Node* removeNode(Node* Tree, int data)
{
    // 임시로 쓰일 노드 포인터
    Node* tempNode;
    // 현재 노드가 NULL이라는 것은 비어있는 것을 의미한다.
    if (Tree == NULL) printf("해당하는 노드를 찾을 수 없습니다.\n");
    // 현재 노드의 값이 제거하려는 값보다 크다면, 왼쪽 자식 노드에서 제거하려는 값을 찾는다.
    else if (Tree->Data > data) Tree->Left = removeNode(Tree->Left, data);
    // 현재 노드의 값이 제거하려는 값보다 작다면, 오른쪽 자식 노드에서 제거하려는 값을 찾는다.
    else if (Tree->Data < data) Tree->Right = removeNode(Tree->Right, data);
    // 현재 노드의 값과 제거하려는 값이 같다면
    else
    {
        // 현재 노드의 왼쪽 자식 노드와 오른쪽 자식 노드가 모두 있는 경우
        if (Tree->Left != NULL && Tree->Right != NULL)
        {
            // 현재 노드의 오른쪽 노드에서 가장 값이 작은 노드의 주소값이 tempNode에 들어간다.
            // 가장 값이 작은 노드는 제일 왼쪽에 있는 노드라고 생각하면 된다.
            tempNode = findMinNode(Tree->Right);
            // 현재 노드의 값에다 값이 가장 작은 노드의 데이터를 대입한다.
            Tree->Data = tempNode->Data;
            // 현재 노드의 오른쪽 자식 노드에서 값이 가장 작은 노드를 제거한다.
            Tree->Right = removeNode(Tree->Right, tempNode->Data);
        }
        // 자식 노드가 없거나 한 쪽만 있는 경우
        else
        {
            // 임시 포인터 변수에다 Tree의 주소값을 대입한다.
            tempNode = Tree;
            // 현재 노드의 왼쪽 자식 노드가 비어있으면, 현재 노드는 현재 노드의 오른쪽 자식 노드가 된다.
            if (Tree->Left == NULL) Tree = Tree->Right;
            // 현재 노드의 오른쪽 자식 노드가 비어있으면, 현재 노드는 현재 노드의 왼쪽 자식 노드가 된다.
            else if (Tree->Right == NULL) Tree = Tree->Left;
            // tempNode를 메모리에서 해제한다.
            free(tempNode);
        }
    }
    // 현재 노드를 반환한다.
    return Tree;
}

추가로 잎 노드같은 경우에는 잎 노드의 오른쪽 자식 노드, 왼쪽 자식 노드가 없으므로 모두 NULL입니다. 즉, 잎 노드가 제거되는 경우에는 잎 노드에만 NULL이 들어가고 메모리에서 해제되는 것입니다. (제거 과정이 주석만으로도 부족하다면, 덧글로 올려주세요. 따로 제거가 이루어지는 과정을 추가로 달도록 하겠습니다.) 이번에는 전체 코드를 보여드리도록 하겠습니다.

예제보기

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    Node* Left;
    Node* Right;
    int Data;
} Node;

Node* createNode(int data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->Left = NULL;
    newNode->Right = NULL;
    newNode->Data = data;
    return newNode;
}

Node* searchNode(Node* Tree, int findData)
{
    if (Tree == NULL) return NULL;
    if (Tree->Data == findData)
        return Tree;
    else if (Tree->Data > findData)
        searchNode(Tree->Left, findData);
    else
        searchNode(Tree->Right, findData);
}

void insertNode(Node* Tree, Node* newNode)
{
     if (newNode->Data > Tree->Data)
     {
         if (Tree->Right != NULL) insertNode(Tree->Right, newNode);
         else Tree->Right = newNode;
     }
     else if (newNode->Data < Tree->Data)
     {
         if (Tree->Left != NULL) insertNode(Tree->Left, newNode);
         else Tree->Left = newNode;
     }
}

Node* findMinNode(Node* Tree)
{
    if (Tree == NULL) return NULL;
    if (Tree->Left != NULL) return findMinNode(Tree->Left);
    else return Tree;
}

Node* removeNode(Node* Tree, int data)
{
    Node* tempNode;
    if (Tree == NULL) printf("해당하는 노드를 찾을 수 없습니다.\n");
    else if (Tree->Data > data) Tree->Left = removeNode(Tree->Left, data);
    else if (Tree->Data < data) Tree->Right = removeNode(Tree->Right, data);
    else
    {
        if (Tree->Left != NULL && Tree->Right != NULL)
        {
            tempNode = findMinNode(Tree->Right);
            Tree->Data = tempNode->Data;
            Tree->Right = removeNode(Tree->Right, tempNode->Data);
        }
        else
        {
            tempNode = Tree;
            if (Tree->Left == NULL) Tree = Tree->Right;
            else if (Tree->Right == NULL) Tree = Tree->Left;
            free(tempNode);
        }
    }
    return Tree;
}

void printTree(Node* Tree)
{
    if (Tree == NULL) return;
    printTree(Tree->Left);
    printf("%d ", Tree->Data);
    printTree(Tree->Right);
}

int main()
{
    Node* Tree = createNode(10);
    Node* findNode;
    int input;
    insertNode(Tree, createNode(5));
    insertNode(Tree, createNode(1));
    insertNode(Tree, createNode(6));
    insertNode(Tree, createNode(17));
    insertNode(Tree, createNode(14));
    insertNode(Tree, createNode(21));
    
    while(1)
    {
        scanf("%d", &input);
        findNode = searchNode(Tree, input);
        if (findNode != NULL) 
        {
            printf("해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 %#x 입니다.\n", findNode);
            removeNode(Tree, input);
            printf("현재 트리 출력: ");
            printTree(Tree); printf("\n");
        }
        else printf("노드를 찾을 수 없었습니다.\n");
    }
    return 0;
}

결과보기

6
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498d50 입니다.
현재 트리 출력: 1 5 10 14 17 21
5
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498ce0 입니다.
현재 트리 출력: 1 10 14 17 21
14
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498dc0 입니다.
현재 트리 출력: 1 10 17 21
17
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498d88 입니다.
현재 트리 출력: 1 10 21

위의 예제는 입력된 데이터를 가지고, 그 데이터를 지니고 있는 노드가 트리 내에 존재하는지 확인합니다. 만약 존재할 경우에, 그 노드를 제거하고 현재 트리내에 있는 모든 노드의 데이터를 출력합니다. 삽입된 노드는 위에서 예로 설명드렸던 그림과 동일하게 노드가 존재합니다. 이러한 이진 트리 탐색에서는 한쪽으로만 몰린 사향 이진 트리에서 최악의 효율성을 보입니다. 사향 이진 트리에서의 시간 복잡도는 O(n)이며, 완전 이진 트리와 비슷한 경우는 O(log2(n))의 효율성을 보인다는 것입니다. 이 때문에, 이진 탐색 트리의 형태는 완전 이진 트리와 비슷하게 구성하시는게 좋습니다.