C++로 구현하는 자료구조 (5) - Binary Search Tree

C++로 구현하는 자료구조

앞서 포스팅한 이진 트리에서 특별한 속성을 갖고 있는 이진 탐색 트리는 어떤 값을 검색하는 데에 좋은 성능을 보여주는 자료구조이다. 직접 구현해보면서 어려웠던 점이 많았었는데 하나씩 모르던 부분을 알게 되는 기분이다. 그럼 이진 탐색 트리에 대해 자세히 알아보자.

---

1. Binary Search Tree

이진 탐색 트리는 루트 노드를 기준으로 왼쪽에는 작은 값을, 오른쪽에는 큰 값을 갖는 이진 트리의 한 종류이다. 모든 노드는 자신을 기준으로 왼쪽 자식값은 자신보다 작고, 오른쪽 자식값은 자신보다 큰 구조를 갖고 있다.

 

출처 : https://www.geeksforgeeks.org/binary-search-tree-data-structure/

 

2. 검색, 삽입, 삭제

이진 탐색 트리에서 검색을 수행하는 방법은 지난 포스팅의 재귀적 탐색방법을 사용하면 되는데 로직이 하나 추가된다. 검색하고자 하는 값이 현재 노드보다 크다면 오른쪽으로, 작다면 왼쪽으로 탐색하는 것이다. 삽입과 삭제 로직은 위키백과를 참고해서 구현을 진행했는데 각각의 알고리즘은 아래와 같다.

 

삽입

• 삽입을 하기 전, 검색을 수행한다.

• 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교해서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

삭제

• 자식노드가 없는 경우 : 해당 노드를 단순히 삭제한다.

• 자식노드가 1개인 노드 삭제: 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.

• 자식노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

 

3. 구현 시 주의할 점

삭제 로직을 구현할 때 어려웠던 점이 많았다. 최대한 소스를 보지 않고 구현하고자 위키백과에서 로직만 참고하면서 구현했는데 문제가 많이 발생했었다. 그 중 가장 큰 문제는 노드를 삭제했을 때 부모노드가 삭제한 노드의 포인터를 아직도 가르키고 있을 때 나타나는 문제였다. 이런 문제를 허상 포인터 문제라고 하는데 트리 뿐만 아니라 모든 자료구조를 구현할 때 주의해야할 부분이다.

 

4. 소스코드

#pragma once
#include <queue>
#include <iostream>

class Node {
public:
    int value;
    Node* left;
    Node* right;
    Node(const int& value) : value(value) {}
};

class BinarySearchTree {
private:
    Node* root;

    Node* _find(Node* cursor, const int& value) {
        if (!cursor) {
            return nullptr;
        }

        if (cursor->value == value) {
            return cursor;
        }
        else {
            if (cursor->value > value) {
                return _find(cursor->left, value);
            }
            else {
                return _find(cursor->right, value);
            }
        }
    }

    void _insert(Node* cursor, const int& value) {
        Node* parent;
        while (cursor) {
            parent = cursor;
            if (parent->value > value) {
                cursor = cursor->left;
            }
            else {
                cursor = cursor->right;
            }
        }
        if (parent->value > value) {
            parent->left = new Node(value);
        }
        else if (parent->value < value) {
            parent->right = new Node(value);
        }
        else {
            std::cout << "이미 있는 값입니다." << std::endl;
        }
    }

    void _preorderTraversal(Node* cursor) {
        if (!cursor) {
            return;
        }
        
        std::cout << cursor->value << " ";
        this->_preorderTraversal(cursor->left);
        this->_preorderTraversal(cursor->right);
    }

public:
    void insert(const int& value) {
        if (!this->root) {
            this->root = new Node(value);
            return;
        }

        this->_insert(this->root, value);
    }

    Node* find(const int& value) {
        Node* cursor = this->root;
        if (!cursor) {
            return nullptr;
        }
        return this->_find(cursor, value);
    }

    void remove(const int& value) {
        Node* parent;
        Node* deleteTarget;
        Node* cursor = this->root;
        while (cursor) {
            // 노드를 삭제하기 위해서 부모값을 저장해둔다.
            if (cursor->left) {
                if (cursor->left->value == value) {
                    parent = cursor;
                }
            }
            else if (cursor->right) {
                if (cursor->right->value == value) {
                    parent = cursor;
                }
            }

            // 삭제할 노드를 탐색한다.
            if (cursor->value == value) {
                deleteTarget = cursor;
                break;
            }
            else if (cursor->value > value) {
                cursor = cursor->left;
            }
            else {
                cursor = cursor->right;
            }
        }

        // 자식노드가 하나도 없을 때
        if (deleteTarget->right == nullptr && deleteTarget->left == nullptr) {
            if (parent->left == deleteTarget) {
                parent->left = nullptr;
            }
            else if (parent->right == deleteTarget) {
                parent->right = nullptr;
            }   
            delete deleteTarget;
            return;
        }

        // 자식노드가 왼쪽 하나만 있을 때
        if (deleteTarget->right == nullptr && deleteTarget->left != nullptr) {
            if (!parent) {
                this->root = deleteTarget->left;
                delete deleteTarget;
            }
            else {
                if (parent->left == deleteTarget) {
                    parent->left = parent->left->left;
                }
                else if (parent->right == deleteTarget) {
                    parent->right = parent->right->left;
                }
                delete deleteTarget;
            }
            return;
        }
        // 자식노드가 오른쪽 하나만 있을 때
        else if (deleteTarget->right != nullptr && deleteTarget->left == nullptr) {
            if (!parent) {
                this->root = deleteTarget->right;
                delete deleteTarget;
            }
            else {
                if (parent->left == deleteTarget) {
                    parent->left = parent->left->right;
                }
                else if (parent->right == deleteTarget) {
                    parent->right = parent->right->right;
                }
                delete deleteTarget;
            }
            return;
        }
        // 자식노드가 두 개가 있을 때
        else {
            Node* tmp;
            cursor = deleteTarget->right;
            if (cursor->left) {
                while (cursor->left) {
                    tmp = cursor;
                    cursor = cursor->left;
                }

                int tmpValue = tmp->left->value;
                tmp->left->value = deleteTarget->value;
                deleteTarget->value = tmpValue;

                delete tmp->left;
                tmp->left = nullptr;
            }
            else if (cursor->right) {
                while (cursor->right) {
                    tmp = cursor;
                    cursor = cursor->right;
                }

                int tmpValue = tmp->right->value;
                tmp->right->value = deleteTarget->value;
                deleteTarget->value = tmpValue;

                delete tmp->right;
                tmp->right = nullptr;
            }
            return;
        }
    }

    void printTree() {
        this->_preorderTraversal(this->root);
        std::cout << std::endl;
    }
};

#include <iostream>
#include "datastructure/BinarySearchTree.h"

int main() {

    BinarySearchTree* bst = new BinarySearchTree();
    bst->insert(4);
    bst->insert(5);
    bst->insert(6);
    bst->insert(3);
    bst->insert(2);
    bst->insert(1);
    bst->insert(1); // 이미 있는 값입니다.

    std::cout << bst->find(3)->value << " 찾았습니다 !" << std::endl;

    bst->printTree();
    bst->remove(3);
    bst->printTree();
    bst->remove(1);
    bst->printTree();
    bst->remove(4);
    bst->printTree();
    bst->remove(2);
    bst->printTree();
    bst->remove(6);
    bst->printTree();

    return 0;
}