[Algorithm] 이진 탐색 트리

이진 탐색 트리 (Binary Search Tree)

이진탐색트리는 키(Key)를 기반으로 한 데이터들을 트리 구조로 관리하는 노드기반 자료구조이다.

루트 데이터의 키를 기준으로 더 작은 키 값을 갖는 데이터들은 왼쪽 하위 서브트리에 위치시키고,

더 큰 키 값을 갖는 데이터들은 오른쪽 하위 서브트리로 위치시킨다. 그리고 각 서브트리들은 재귀적으로 같은 전략을 통해 새로운 데이터들을 위치시킨다.

 

예제 트리

일반적인 리스트 형태로 구조화된 자료구조에서는 데이터를 탐색하기 위한 비용이 O(N) 정도인 반면,

이진 트리 형태로 자료를 구조화시키고 나면, 이진탐색을 통해 원하는 데이터를 찾기 위한 탐색비용을 O(logN)까지 줄일 수 있다. 예를 들어 7을 키로 갖는 데이터를 찾고자 한다면, 다음과 같은 순서로 찾을 수 있다.

 

7 < 8 왼쪽 서브트리로 이동

3 < 7 오른쪽 서브트리로 이동

6 < 7 오른쪽 서브트리로 이동

7 == 7 탐색 완료 

 

연산 (Operations)

이진 트리에서 기본적인 자료구조로서의 필수 연산들을 구현해보자.

먼저 트리 구조를 잡기 위해 TreeNode를 정의하고, 위 그림에서 보여진 예제 트리를 만들어보자.

class TreeNode
{
public:
    TreeNode(int key, int value) : key(key), value(value), left(nullptr), right(nullptr) {}
    TreeNode(int key, int value, TreeNode* left) : key(key), value(value), left(left), right(nullptr) {}
    TreeNode(int key, int value, TreeNode* left, TreeNode* right) : key(key), value(value), left(left), right(right) {}

public:
    int key;
    int value;
    TreeNode* left;
    TreeNode* right;
};

// Tree 생성
TreeNode* MakeTree()
{
    TreeNode* left_subtree = new TreeNode(3, 33, new TreeNode(1, 11), new TreeNode(6, 66, new TreeNode(4, 44), new TreeNode(7, 77)));
    TreeNode* right_subtree = new TreeNode(10, 1010, nullptr, new TreeNode(14, 1414, new TreeNode(13, 1313)));
    TreeNode* tree = new TreeNode(8, 88, left_subtree, right_subtree);

    return tree;
}

 

 

탐색 (Searching)

탐색은 어떤 데이터의 키를 입력으로 받을 때, 트리에서 이 키에 대한 데이터를 찾아올 수 있도록 하는 연산이다.

이진 트리는 구조 자체가 재귀적으로 형성되어 있다. 그리고 모든 노드들이 키를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누어지도록 구성되어 있기 때문에, 재귀함수를 이용하여 현재 루트를 계속 이동시켜가는 방법으로, 쉽게 이진 탐색을 구현할 수 있다. 이진탐색 과정은 다음과 같이 재귀적으로 정의할 수 있다.

 

1. 탐색 키가 현재 루트의 키보다 작으면, 왼쪽 서브트리에서 다시 탐색

2. 탐색 키가 현재 루트의 키보다 크면, 오른쪽 서브트리에서 다시 탐색

3. 탐색 키와 현재 루트의 키가 같으면, 현재 루트를 반환

4. 기저 조건

TreeNode* Search(int key, TreeNode* root)
{
    // 기저 조건
    if (root == nullptr)
        return nullptr;

    if (key == root->key)
        return root;

    if (key < root->key)
        return Search(key, root->left);

    if (key > root->key)
        return Search(key, root->right);
}

 

삽입 (Insertion)

삽입은 어떤 데이터의 키와, 값을 입력으로 받을 때, 트리의 적절한 위치에 데이터를 추가하는 연산이다.

이진 트리에 삽입을 하기 위해서는 먼저 적절한 삽입 위치부터 찾아야 할 것이다.

삽입 위치를 찾는 과정은 탐색 과정과 동일하고, 이 과정에서 다음과 같은 두 가지 상황이 생길 수 있다.

 

1. 삽입 키가 이미 트리에 있는 경우

이 경우는 기존 키를 갖고있는 데이터를 새로운 데이터로 갱신해준다.

 

2. 삽입 키가 트리에 없는 경우

이 경우는 탐색 과정을 통해 최종적으로는 루트가 nullptr인 위치까지 도달할 것이다.

루트가 nullptr에 도달한 시점에 새 노드를 생성하고, 해당 루트를 갖고있는 변수가 새 노드를 참조하도록 한다.

 

참조자를 이용한 방법

// 참조자를 이용한 방법
void Insert(int key, int value, TreeNode*& root)
{
    // root는 TreeNode 포인터의 참조자이기 때문에,
    // root가 nullptr인 시점에 그 nullptr을 담고있는 변수 자체일 것이다. (즉, 이 root의 parent의 left나 right 중 하나일 것이다.)
    // 포인터의 참조로 root를 가져왔기 때문에, root = new TreeNode(key, value)를 통해, 해당 변수가 직접 새 노드를 참조할 수 있을 것이다.
    if (root == nullptr)
        root = new TreeNode(key, value);

    else if (key == root->key)
        root->value = value;

    else if (key < root->key)
        Insert(key, value, root->left);

    else if (key > root->key)
        Insert(key, value, root->right);
}

 

반환을 이용한 방법

// 반환을 이용한 방법
TreeNode* Insert2(int key, int value, TreeNode* root)
{
    // 삽입되는 경우에만 새로 생성된 노드를 반환하여, root->left나 root->right가 새 노드를 참조하도록 한다.
    if (root == nullptr)
        return new TreeNode(key, value);

    else if (key == root->key)
        root->value = value;

    // root->left는 왼쪽 서브트리의 루트를 참조하도록 한다.
    // 물론 이미 참조하고 있지만, 새 노드가 삽입되는 상황에 대한 예외 반환을 가능하도록 하기 위함이다.
    else if (key < root->key)
        root->left = Insert2(key, value, root->left);

    // left와 마찬가지
    else if (key > root->key)
        root->right = Insert2(key, value, root->right);

    // 특별한 일이 없다면 자기자신을 반환하여, root->left나 root->right의 참조가 변하지 않도록 한다.
    return root;
}

 

 

삭제 (Deletion)

삭제는 어떤 데이터의 키를 입력으로 받을 때, 트리에서 이 키에 매칭되는 데이터를 제거하는 연산이다.

이진 트리에 어떤 데이터를 삭제하기 위해서 마찬가지로 데이터의 키에 대한 탐색 과정이 필요할 것이다. 

이 과정은 탐색 연산과 동일하게 진행된다.

 

탐색 과정 중 다음과 같은 상황들이 생길 수 있다.

1. 삭제 키가 트리에 없는 경우

삭제 키를 발견하지 못할 것이고 특별한 작업 없이 종료하면 될 것이다.

 

2. 삭제 키가 트리에 있는 경우

삭제 키를 발견하게 될 것이고, 노드 삭제 과정을 진행하면 될 것이다.

 

노드 삭제 과정 중에는 다음과 같은 상황들이 생길 수 있다.

2 - 1. 삭제 노드의 자식이 없는 경우

현재 노드를 삭제한다.

 

2 - 2. 삭제 노드의 자식이 하나인 경우

재 노드를 삭제하고, 자식이 현재 노드를 대체한다.

 

2 - 3. 삭제 노드의 자식이 둘인 경우

현재 루트를 삭제하기 전,

자신의 왼쪽 서브트리의 최대노드 or 자신의 오른쪽 서브트리의 최소노드를 찾고,

해당 노드를 현재 루트를 대체할 새로운 루트로 지정하고,

해당 노드를 삭제한다.

(왼쪽 서브트리의 최대노드 or 오른쪽 서브트리의 최소노드는 절대 두 개의 자식을 가질 수 없으므로, 재귀적으로 삭제 연산을 다시 활용한다면, 1번 혹은 2번 형태로 노드가 삭제될 것이다.)

 

삽입 과정과 마찬가지로, 현재 루트를 대체하는 과정에서 루트 포인터의 참조자를 활용한다.

(이 코드는 오른쪽 서브트리의 최소노드를 사용하는 형태로 작성되었다.)

void Delete(int key, TreeNode*& root)
{
    // search
    // key not found
    if (root == nullptr)
    {
    }
    else if (key < root->key)
    {
        Delete(key, root->left);
    }
    else if (key > root->key)
    {
        Delete(key, root->right);
    }
    // key found
    else
    {
        // has no child
        if (root->left == nullptr && root->right == nullptr)
        {
            delete root;
            root = nullptr;
        }

        // has right child
        else if (root->left == nullptr && root->right != nullptr)
        {
            TreeNode* delete_node = root;
            root = root->right;
            delete delete_node;
        }

        // has left child
        else if (root->left != nullptr && root->right == nullptr)
        {
            TreeNode* delete_node = root;
            root = root->left;
            delete delete_node;
        }
        // has two childs
        else
        {
            // find minimum node from right subtree
            TreeNode* min = FindMin(root->right);

            // replace to min node key & value
            root->key = min->key;
            root->value = min->value;

            // delete
            Delete(min->key, root->right);
        }
    }
}

 

 

순회 (Traversal)

순회는 모든 데이터를 방문하는 연산이다.

이진트리의 방문방법은 세 가지가 있다.

 

전위 순회

전위순회는 현재 루트를 먼저 방문하고,

왼쪽 서브트리로 이동 후 방문,

오른쪽 서브트리로 이동 후 방문한다.

트리를 복사하는 경우와 같은 상황에 사용된다.

 

void PreOrder(TreeNode* root)
{
    if (root == nullptr)
        return;

    cout << root->key << " ";
    PreOrder(root->left);
    PreOrder(root->right);
}

 

 

중위 순회

중위순회는 왼쪽 서브트리로 이동 후 방문하고,

현재 루트를 방문하고,

오른쪽 서브트리로 이동 후 방문한다.

가장 자주 사용되는 순회방법으로, 트리의 원소를 순서대로 순회하기 위한 방법으로 사용된다.

 

void InOrder(TreeNode* root)
{
    if (root == nullptr)
        return;

    InOrder(root->left);
    cout << root->key << " ";
    InOrder(root->right);
}

 

 

후위 순회

후위순회는 왼쪽 서브트리로 이동 후 방문,

오른쪽 서브트리로 이동 후 방문,

현재 루트를 방문한다.

트리 전체를 파괴하는 경우와 같은 상황에 사용된다.

 

void PostOrder(TreeNode* root)
{
    if (root == nullptr)
        return;

    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->key << " ";
}

 

 

전체 삭제 (Delete All)

트리를 통째로 삭제해야 하는 상황도 생길 수 있다.

트리를 삭제하는 상황에 위의 노드부터 파괴한다면, 하위 서브트리에 대한 참조관계도 끊어지기 때문에,

아래에서부터 차근차근 파괴하며 올라오는 전략을 취해야 할 것이다.

이 과정을 수행하기 위한 방법으로 후위순회(Postorder Traversal)이 적합하다.

후위순회는 기본적으로 모든 노드들이 자기자신의 좌, 우 서브트리에 대한 작업을 마친 후에 작업을 진행한다.

여기서 일반적인 작업이 진행되는 시점에 노드에 대한 파괴작업을 진행하면 된다. 그러면 모든 노드들은 자기자신의 좌, 우 서브트리들이 파괴되고 나서 자기자신을 파괴하기 때문에, 중간에 참조관계가 끊어질 일 없이 모두 파괴시킬 수 있다.

 

void DeleteTree(TreeNode* root)
{
    if (root == nullptr) return;

    // first delete both subtrees 
    DeleteTree(root->left);
    DeleteTree(root->right);

    cout << "delete : " << root->key << endl;

    delete root;
}

 

복사 (Copy)

트리를 통째로 복사해야 하는 상황도 생길 수 있다.

트리를 복사하는 과정은 위에서부터 노드를 생성하고 서브트리를 참조해가며 내려오는 방향으로 진행해야 할 것이다.

이 과정을 수행하기 위한 방법으로 전위순회(Preorder Traversal)이 적합하다.

전위순회의 방문순서에 맞게, 복사과정도 먼저 노드를 생성하고 좌, 우 서브트리에 대한 작업을 진행한다.

또한 좌, 우 서브트리에서 생성한 노드를 반환하도록 하여 left, right에 참조할 수 있도록 하고, 모든 작업이 끝났다면 현재 루트를 반환하도록 하여 부모 노드가 현재 루트를 참조할 수 있도록 한다.

TreeNode* CopyTree(TreeNode* root, TreeNode*& copy)
{
    if (root == nullptr)
        return nullptr;

    copy = new TreeNode(root->key, root->value);
    copy->left = CopyTree(root->left, copy->left);
    copy->right = CopyTree(root->right, copy->right);
    return copy;
}

 

구현

1차 구현 (객체화)

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/2-BST-Implement.cpp

insooneelife/AlgorithmTutorial

 

2차 구현 (ValueType 일반화)

 

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/3-BST-Template-Value-Implement.cpp

insooneelife/AlgorithmTutorial

 

 

3차 구현 (KeyType 일반화)

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/4-BST-Template-Key-Implement.cpp

insooneelife/AlgorithmTutorial

 

 

4차 구현 (CompareType 일반화)

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/5-BST-Template-Compare-Implement.cpp

insooneelife/AlgorithmTutorial

 

 

5차 구현 (Iterator 구현)

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/6-BST-Template-Iterator-Implement.cpp

insooneelife/AlgorithmTutorial

 

개선 사항

이상적인 상황만을 가정한다면 이진탐색트리의 탐색, 삭제, 삽입과 같은 필수연산들은 O(logN) 시간에 동작할 것이다. 

하지만, 삽입 or 삭제가 진행됨에 따라 트리 구조도 언제든지 최악의 상태로 변할 수 있다. 예를 들어 모든 노드의 자식들이 각각의 왼쪽 자식으로 붙어있는 상황을 생각해보자. 이 경우 탐색, 삽입, 삭제 과정은 모두 O(N) 시간으로 동작하게 될 것이다. 이런 형태의 트리를 편향 이진탐색트리(Skewed Binary Search Tree)라고 부른다.

이러한 문제는 결국 트리의 균형이 깨지기 때문에 발생하는 것인데, 그것을 방지하기 위해 자체적으로 균형을 유지하는 균형 이진탐색트리(Balanced Binary Search Tree)들이 고안되었다. 균형 이진탐색트리란, 노드의 삽입과 삭제 과정 속에서 자체적으로 높이와 너비의 균형을 유지하도록 동작하는 이진탐색트리를 의미한다.

 

AVL Tree

두 자식 서브트리의 높이는 항상 최대 1만큼 차이나도록 유지한다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해 트리 회전 알고리즘을 통해 스스로 균형을 잡는다.

탐색, 삽입, 삭제는 모두 최악 경우에도 O(logN)을 유지한다.

 

Red Black Tree

각 노드의 속성을 Red 혹은 Black으로 지정하고, 모든 nullptr 노드들과 가장 상단의 루트 노드를 Black 속성으로 지정한다. 그리고 레드 노드의 양쪽 자식은 반드시 블랙 노드가 되도록 하여, 레드 노드가 연속적으로 위치할 수 없도록 하여 균형을 잡는 트리이다.

탐색, 삽입, 삭제는 모두 최악 경우에도 O(logN)을 유지한다.

 

 

C++ Binary Search Tree (map, set)

C++에서는 STL을 통해 이진탐색트리(Red Black Tree) 컨테이너를 지원한다.

C++ map의 경우 삽입, 삭제, 참조 모두 O(logN) 정도에 근사하게 동작한다.

또한 string을 key로 하는 경우, 해시 테이블에 비해 조금 좋은 성능을 보인다.

 

사용 예제 1.

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/7-map.cpp

insooneelife/AlgorithmTutorial

 

사용 예제 2.

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BinarySearchTree/8-map-CustomKey.cpp

insooneelife/AlgorithmTutorial