[Data Structure] Binary Search Tree (이진 탐색 트리)

Binary Search Tree

📢 설명은 이전 Binary Tree 포스트를 참고해주세요!

이 포스트에서는 구현에 집중을 했습니다!!

Insert(삽입)

Binary Search Tree는 Parent을 기준으로 작은 값은 Left-Child, 큰 값은 Right-Child 예요. 그래서 특정 값을 Insert한다면 Root Node부터 값을 비교하기 시작해서 알맞은 곳으로 내려가기만 하면 돼요😁

Remove(제거)

Binary Search Tree에서 가장 구현하기 까다로운 부분이라고 할 수 있어요😥 특정 Node를 제거하려면 경우에따라 제거하는 방법이 다 달라요. 아래의 4가지 경우와 그림을 보고 설명하겠습니다.

1. Leaf-Node만 있는 경우

• 해당 Node만 제거하면 된다.

2. Left-Child만 있는 경우

• 해당 Node를 제외하고 나머지 노드를 그림처럼 연결시킨 후 제거한다.

3. Right-Child만 있는 경우

• 해당 Node를 제외하고 나머지 노드를 그림처럼 연결시킨 후 제거한다.

4. 둘 다 있는 경우

• 해당 Node를 제거하고 Right-SubTree에서 가장 작은 값을 가져오거나, Left-SubTree에서 가장 큰 값을 제거한 자리에 위치시킨다. (이렇게 해야 Binary Search Tree의 규칙을 위배하지 않아요)

---

🎨 C++ 구현

Binary Search Tree는 따로 C++ STL에 구현이 되어있지 않아요. 그래서 제가 직접 C++로 구현을 해봤습니다. 잘못된 점이 있다면 댓글 남겨주세요😄

#include <iostream>
#include <vector>
#include <list>

using namespace std;

struct Node {
    Node * parent;
    Node * left, * right;
    int value;
    Node(int _v) : value(_v), parent(NULL), left(NULL), right(NULL) {}
};

class LinkedBinaryTree {
private:
    Node * root;

public:
    LinkedBinaryTree() {
        root = NULL;
    }

    Node * getRoot() {
        return root;
    }

    // 특정 node가 left-child라면 1 아니면 0
    bool isLeftChild(Node * node) {
        return node->parent->left->value == node->value;
    }

    // 특정 node가 right-child라면 1 아니면 0
    bool isRightChild(Node * node) {
        return node->parent->right->value == node->value;
    }

    //isRoot - Root라면 1 아니면 0
    bool isRoot(Node * node) {
        return node->parent == nullptr;
    }

    bool isExternal(Node * node) {
        return (node->left == NULL) && (node->right == NULL);
    }

    // insert method - node를 child로 삽입
    void insert(int value) {
        Node * newNode = new Node(value);
        Node *here = root;

        // Root가 존재하지 않는경우
        if(root == NULL) {
            root = new Node(value);
            return;
        }
        // value가 이미 존재하는 경우
        else if(find(value)) {
            cout << value << " is already in Binary Tree" << endl;
            return;
        }
        // Root가 존재하는 경우
        else {
            while (true) {
                if (here->value < newNode->value) {
                    if(here->right == NULL) {
                        here->right = newNode;
                        newNode->parent = here;
                        break;
                    }
                    here = here->right;
                }
                else {
                    if(here->left == NULL) {
                        here->left = newNode;
                        newNode->parent = here;
                        break;
                    }
                    here = here->left;
                }
            }
        }
    }

    // remove method - node를 제거
    void remove(int value) {

        Node * foundNode = find(value);

        if(!foundNode) {
            cout << "There is no Node" << endl;
        }
        else {
            // 1. leaf-node인 경우
            if(isExternal(foundNode)) {
                if(isLeftChild(foundNode)) {
                    foundNode->parent->left = NULL;
                    foundNode->parent = NULL;
                }
                else {
                    foundNode->parent->right = NULL;
                    foundNode->parent = NULL;
                }
            }
            // 2. left-child만 있는 경우
            else if(foundNode->right == NULL && foundNode->left != NULL) {
                foundNode->left->parent = foundNode->parent;
                if(isLeftChild(foundNode))
                    foundNode->parent->left = foundNode->left;
                else
                    foundNode->parent->right = foundNode->left;
            }
            // 3. right-child만 있는 경우
            else if(foundNode->right != NULL && foundNode->left == NULL) {
                foundNode->right->parent = foundNode->parent;
                if(isLeftChild(foundNode))
                    foundNode->parent->left = foundNode->right;
                else
                    foundNode->parent->right = foundNode->right;
            }
            // 4. 둘 다 있는 경우
            else {
                Node * theMinNode = foundNode->right;
                while(theMinNode->left != NULL)
                    theMinNode = theMinNode->left;
                if(theMinNode->right != NULL) {
                    theMinNode->right->parent = theMinNode->parent;
                    theMinNode->parent->left = theMinNode->right;
                }
                theMinNode->parent = foundNode->parent;
                theMinNode->left = foundNode->left;
                if(isLeftChild(foundNode))
                    foundNode->parent->left = theMinNode;
                else
                    foundNode->parent->right = theMinNode;
            }
        }
    }

    // find method - 해당 node를 찾으면 node 반환 아니면 NULL
    Node * find(int value) {
        Node * here = root;
        while(true) {
            if(here->value < value)
                here = here->right;
            else
                here = here->left;

            if(here == NULL)    return NULL;
            if(here->value == value)    return here;
        }
    }

    // 전위순회
    void preorder(Node * here) {
        if(here == NULL)    return;

        cout << here->value << " ";
        preorder(here->left);
        preorder(here->right);
    }

    // 중위순회
    void inorder(Node * here) {
        if(here == NULL)    return;

        inorder(here->left);
        cout << here->value << " ";
        inorder(here->right);
    }

    // 후위순회
    void postorder(Node * here) {
        if(here == NULL)    return;

        postorder(here->left);
        postorder(here->right);
        cout << here->value << " ";
    }
};

int main() {
    LinkedBinaryTree * linkedBinaryTree = new LinkedBinaryTree();
    Node * root = linkedBinaryTree->getRoot();
    linkedBinaryTree->insert(10);
    linkedBinaryTree->insert(20);
    linkedBinaryTree->insert(5);
    linkedBinaryTree->insert(7);
    linkedBinaryTree->insert(2);
    linkedBinaryTree->insert(1);
    linkedBinaryTree->insert(30);
    linkedBinaryTree->remove(20);
    linkedBinaryTree->preorder(linkedBinaryTree->getRoot());

}

---

📋 예제

백준 5639 - 이진 검색 트리

백준 5639 - 해답