[알고리즘 알아보기] 이진 탐색 트리(Binary Search Tree)

개요

이진 탐색 트리에 대해서 알기 위해서는 그래프, 트리에 대한 이해가 필요하지만 이번에는 알고있다고 생각하고 이진 트리부터 설명하겠습니다.

 

이진트리란?

이진트리는 노드에 연결된 child node가 최대 2개인 트리입니다.

노드에 연결된 좌측 노드를 left child node, 우측 노드를 right child node라고 많이 표현합니다.

 

template <typename T>
class Node
{
    T data;
    Node *left, *right;
}

간단하게는 위와 같은 구조를 띕니다.

 

 

이진탐색트리란?

이진 탐색 트리(이하 BST)는 이진 트리의 하위 집합으로

parent node의 data value는 좌측 child node의 data보다 크며 우측 child node의 data보다 작아야한다는 조건이 필요합니다.

 

정리하면 아래와 같습니다.

 

• 왼쪽 서브트리의 모든 값 < 부모 노드 값
• 오른쪽 서브트리의 모든 값 > 부모 노드 값
• 각각의 서브트리도 BST여야 함

 

위에서 보았던 이진트리 사진도 BST의 일종입니다.

 

이 경우에는 어떤 데이터를 찾을 때 탐색하는 depth가 깊어질 때마다 경우의 수가 반으로 줄어드므로 평균적으 O(log n)의 복잡도를 가집니다.

 

다만 최악의 경우에는 아래와 같이 일렬로 늘어선 구조가 될 수 있기 때문에 O(n)의 복잡도가 걸릴 수 있습니다.

 

---

BST구현

 

노드 삽입

기본적으로 BST에서는 새로 삽입되는 노드의 위치를 찾기 위해 루트부터 탐색이 필수적입니다.

 

따라서 간단하게 구현하면 아래와 같습니다.

    void insert(Node*& node, int data)
    {
        if (node == nullptr)
        {
            node = new Node(data);
            return;
        }

        if (data < node->data)
        {
            insert(node->left, data);
        }
        else if (data > node->data)
        {
            insert(node->right, data);
        }
        else
        {
            return;
        }
    }

만약 node가 nullptr이라면 leaf 노드에 다다른 것이기 때문에 탐색을 마친 것이고 따라서 새로운 노드를 생성하고 return합니다.

여기서 주의해야할 점은 새로운 노드를 생성하고 지역변수가 아닌 실제 tree구조에 반영해야하기 때문에 Node*&형태로 인자를 받아주고 있다는 점입니다. (당연히 다른 형태의 구현도 가능합니다)

 

또한 추가적인 구현이 있지 않다면 기본적으로 탐색은 항상 root부터 시작해야 합니다.

insert(root, data)와 같은 형태로 반드시 시작하며, 따라서 public으로는 insert(data)를 보여주고 내부적으로 private insert(root, data)를 사용하는 형태가 될 수도 있습니다.

---

노드 삭제

노드 삭제의 경우에도 루트부터 탐색하며 삭제하려는 키를 찾습니다.

다만 찾은 노드가 양쪽 다 자식이 있는 노드라면 원래의 위치를 대체할 노드가 필요합니다.

 

이 경우에는 가장 간단하게 할 수 있는 방법이 후계자가 될 수 있는 리프 노드(successor)를 찾는 것입니다.

successor는 삭제하려는 노드의 좌측 자식 중 가장 큰 값(좌측 탐색 후 리프까지 우측 탐색) 또는 우측 자식 중 가장 작은 값(우측 탐색 후 리프까지 좌측 탐색)입니다.

 

만약 이렇게 대체한다면 후계자 노드는 리프이기 때문에 대체하더라도 자식 걱정을 하지 않아도 되며, 후계자 노드의 키는 삭제하려는 노드의 좌측 자식보다는 크며 우측 자식 보다는 작은 값이 될 것이기 때문입니다.

 

bool erase(Node*& node, int key)
{
    if (!node)
        return false;

    if (key < node->key)
    {
        return erase(node->left, key);
    }
    else if (key > node->key)
    {
        return erase(node->right, key);
    }
    else
    {
        // key == node->key

        if (!node->left)// 우측 자식만 존재 
        {
            Node* t = node; 
            node = node->right; 
            delete t; 
            return true;
        }
        else if (!node->right) // 좌측 자식만 존재
        {
            Node* t = node; 
            node = node->left;  
            delete t; return true;
        }
        else {
            // 오른쪽 최소값 찾기
            Node* s = node->right;
            while (s->left) s = s->left;
            node->key = s->key;
            return erase(node->right, s->key);
        }
    }
    
}

코드가 삽입보다는 약간 복잡하지만 논리자체는 간단합니다.

 

먼저 삭제할 key의 위치를 찾습니다.

만약에 자식이 없는 리프 노드라면 자연스럽게 nullptr로 대체될 것입니다.

좌측 자식만 존재한다면 좌측 자식, 우측 자식만 존재한다면 우측 자식으로 대체됩니다.

 

만약 양쪽 모두 자식이 존재한다면 후계자를 찾아 대체시킵니다.

---

이후...

BST는 위에서 언급했듯이 최악의 경우 O(n)의 탐색속도를 보여줄 수 있기 때문에

트리의 밸런스를 유지하는 기능이 존재하는 다른 트리 알고리즘을 사용합니다.

 

AVL트리와 레드블랙트리에 대해 가능하다면 추후 다뤄보겠습니다.