이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리(binary search tree)란 무엇일까?

이진 탐색 트리는 이진 검색을 사용할 수 있도록 노드가 연결된 트리 자료구조다.

 

왜 이진 탐색 트리를 사용할까?

이진 탐색 트리는 이진 검색을 사용하여 빠르게 데이터를 찾을 수 있기 때문에 검색, 범위 검색을 위해 사용된다.

 

배열 또한 이진 검색을 사용할 수 있다. 그러나, 왜 굳이 이진 탐색 트리를 사용할까? 배열은 데이터 삽입, 삭제 시마다 오름차순이 깨질 수 있기 때문에 이진 검색을 사용하기 전 항상 정렬이 필요하다. 하지만 이진 탐색 트리는 항상 정렬 상태를 유지하고 있기 때문에 정렬 없이 이진 검색을 사용할 수 있다.

 

따라서 데이터의 삽입, 삭제가 많은 환경에서 이진 검색을 사용하기 위해 추가적인 정렬이 필요없는 이진 색 트리를 사용한다. 

 

이진 탐색 트리의 조건

0. 기본 트리의 개념을 상속받는다.

1. 모든 노드는 자식 노드를 최대 2개까지 가질 수 있다.

2. 왼쪽 서브트리의 모든 노드는 현재 노드의 값보다 작다.

3. 오른쪽 서브트리의 모든 노드는 현재 노드의 값보다 크다.

---

이진 탐색 트리의 속성

1. 중위 순회(Inorder traversal) 결과의 키 값은 항상 오름차순으로 나열된다.

 

이진 탐색 트리의 용어 정리

용어	설명
후임자 (successor)	현재 노드의 키 값 다음으로 큰 수를 의미한다
선임자 (predecessor)	현재 노드의 키 값 직전의 작은 수를 의미한다

 

이진 탐색 트리의 중복 키 처리

이진 탐색 트리는 중복 키를 허용하지 않을 수도 있고, 허용하여 구현할 수도 있다.

본 블로그에서는 중복 키를 허용하지 않는다는 가정 하에 여러 트리를 구현하고 있다.

하지만, 만약 중복키를 허용한다면 어떻게 구현할 수 있을지 생각해보자.

일반적인 방법

중복 키를 가진 노드를 부모 노드의 오른쪽에 위치할 것인지, 왼쪽에 위치할 것인지만 결정한다면 이진 탐색 트리는 정상적으로 작동한다.

 

하지만 먼저 중복 키를 허용하기 전, 그것이 유용한지 생각해볼 필요가 있다.

 

Case 1. 키가 노드의 데이터인 경우

키가 노드의 데이터인 경우 중복된 데이터는 유용하지 않고 트리의 높이만 증가시키기 때문에 중복 키를 허용할 필요가 없다.

만약 키의 개수가 필요한 경우, 노드에 counter를 추가하여 구현할 수 있다.

 

Case 2. 키가 데이터의 인덱스로 사용되는 경우

키가 인덱스로 사용되는 경우 같은 키라 하더라도 다른 데이터를 담고 있을 수 있기 때문에 중복 키가 필요한 경우가 발생한다.

이 경우, 위에 서술한 방식대로 중복 키를 허용하여 구현할 수도 있으나,

같은 키를 가진 노드끼리 링크드 리스트로 연결하는 등 일반적인 방법 외에도 다양한 방법을 생각해 볼 수 있다.

---

이진 탐색 트리의 구현

삽입 (Insert)

삽입 연산의 구현은 간단하다.

새로운 노드의 키 값을 현재 노드와 비교하면서 말단 노드까지 이동한다.

그 다음, 규칙에 맞게 새로운 노드를 현재 노드의 자식으로 추가한다.

Node *insert(Node *root, int key)
{
    if (root == NULL)
    {
        return createNewNode(key);
    }

    if (key <= root->key)
    {
    	root->left = insert(root->left, key);
        return root;
    }
    else
    {
        root->right = insert(root->right, key);
        return root;
    }
    return root;
}

---

삭제 (Delete)

삭제 연산은 조금 복잡하며, 다음 문제를 어떻게 해결할지 생각해 볼 필요가 있다.

삭제할 노드의 자식 노드를 부모 노드와 어떻게 연결할 수 있을까?

자식 노드의 개수를 기준으로 경우의 수를 나눠 연결 방법을 생각해 볼 수 있다.

 

Case 1. 자식 노드가 없는 경우

삭제될 노드가 말단 노드이므로 그냥 삭제해도 문제될 것이 없다.

 

Case 2. 자식 노드가 1개인 경우

삭제될 노드의 자식 노드를 부모 노드와 연결해도 문제될 것이 없다.

 

Case 3. 자식 노드가 2개인 경우 

삭제될 노드의 자식 노드들을 부모 노드에 모두 연결할 수 없으므로

successor를 찾아 삭제할 노드와 키 값을 바꾸고 successor 노드를 삭제한다.

 

왜 successor를 삭제할까?

이진 탐색 트리의 조건을 깨지 않기 위함이다.

양쪽 자식 노드가 존재하는 것을 가정하기 때문에 successor가 부모노드인 경우는 발생하지 않는다.

Node *delete(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key)
    {
        root->left = delete(root->left, key);
        return root;
    }
    else if (key > root->key)
    {
        root->right = delete(root->right, key);
        return root;
    }

    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 *sucParent = root;
    Node *suc = root->right;
    while (suc->left != NULL)
    {
        sucParent = suc;
        suc = suc->left;
    }
    root->key = suc->key;
    if(sucParent == root) 
    {
        sucParent->right = suc->right;
    }
    else
    {
        sucParent->left = suc->right;
    }
    free(suc);
    return root;
}

---

검색 (Search)

검색 연산 또한 삽입 연산과 같이 간단하게 구현할 수 있다. 이진 검색의 원리를 응용하여 구현한다.

Node *search(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key)
    {
        root = search(root->left, key);
        return root;
    }
    else if (key > root->key)
    {
        root = search(root->right, key);
        return root;
    }
    return root;
}

---

범위 검색 (Range Search)

트리를 중위 순회(inorder traversal)하면서 범위 내의 요소일 경우 출력한다.

순회 중 범위 밖의 요소인 경우 탐색하지 않도록 하여 최적화 할 수 있다.

void rangeSearch(Node *root, int x, int y)
{
    if (root != NULL)
    {
        if (x <= root->key)
        {
            rangeSearch(root->left, x, y);
        }
        if (x <= root->key && root->key <= y)
        {
            printf("%d ", root->key);
        }
        if (root->key <= y)
        {
            rangeSearch(root->right, x, y);
        }
    }
}

---

시간 복잡도

이진 탐색 트리 또한 트리의 균형이 무너질수록 성능이 나빠지는 문제를 겪는다.

트리가 최악의 시간복잡도를 가지는 경우는 모든 노드가 일렬로 연결되어있는 경우이며,

이때 삽입, 삭제, 검색의 시간복잡도는 링크드 리스트와 같아진다.

연산	평균	최악
삽입	O(logN)	O(N)
삭제	O(logN)	O(N)
검색	O(logN)	O(N)

---

문제점

이진 탐색 트리는 이진 검색을 통해 빠르게 원소를 검색할 수 있지만, 균형이 나빠질 수록 O(logN)의 시간복잡도를 보장할 수 없다는 것이 문제점이다.

 

그렇다면 트리의 균형을 유지함으로써 O(logN)의 시간복잡도를 보장하게 만드는 방법을 생각해 볼 수 있다.

---

이진 탐색 트리 코드

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int key;
    struct Node *left, *right;
} Node;

Node *createNewNode(int key)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node *search(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key)
    {
        root = search(root->left, key);
        return root;
    }
    else if (key > root->key)
    {
        root = search(root->right, key);
        return root;
    }
    return root;
}

void rangeSearch(Node *root, int x, int y)
{
    if (root != NULL)
    {
        if (x <= root->key)
        {
            rangeSearch(root->left, x, y);
        }
        if (x <= root->key && root->key <= y)
        {
            printf("%d ", root->key);
        }
        if (root->key <= y)
        {
            rangeSearch(root->right, x, y);
        }
    }
}

Node *insert(Node *root, int key)
{
    if (root == NULL)
    {
        return createNewNode(key);
    }

    if (key <= root->key)
    {
        root->left = insert(root->left, key);
        return root;
    }
    else
    {
        root->right = insert(root->right, key);
        return root;
    }
    return root;
}

Node *delete(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key)
    {
        root->left = delete(root->left, key);
        return root;
    }
    else if (key > root->key)
    {
        root->right = delete(root->right, key);
        return root;
    }

    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 *sucParent = root;
    Node *suc = root->right;
    while (suc->left != NULL)
    {
        sucParent = suc;
        suc = suc->left;
    }
    root->key = suc->key;
    if(sucParent == root) 
    {
        sucParent->right = suc->right;
    }
    else
    {
        sucParent->left = suc->right;
    }
    free(suc);
    return root;
}

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

int main() {
    /* Let us create following tree
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Original BST: ");
    inorder(root);
  
    printf("\n\nDelete a Leaf Node: 20\n");
    root = delete(root, 20);
    printf("Modified BST tree after deleting Leaf Node:\n");
    inorder(root);

    printf("\n\nDelete Node with single child: 70\n");
    root = delete(root, 70);
    printf("Modified BST tree after deleting single child Node:\n");
    inorder(root);

    printf("\n\nDelete Node with both child: 50\n");
    root = delete(root, 50);
    printf("Modified BST tree after deleting both child Node:\n");
    inorder(root);

    return 0;
}