Binary Search Tree

개요

노드에 키(또는 {키, 값} 쌍)를 저장하는 이진트리로, 다음 성질을 만족한다.

 

• 노드 v와 왼쪽 자식 u, 오른쪽 자식 w에 대해 key(u) ≤ key(v) ≤ key(w) 를 만족한다.

리프 노드는 아무것도 저장하지 않고, 트리를 중위 순회하면 키 오름차순으로 방문하게 된다.

 

 

탐색

키 k를 찾으려면, 루트 노드에서 출발해 k와 현재 노드의 키를 비교하며 탐색한다.

 

k가 현재 노드의 키보다 작다면 왼쪽 노드로, 크다면 오른쪽 노드를 탐색한다.

 

리프 노드에 도달하면 키 k가 존재하지 않음을 의미한다.

 

 

삽입

먼저, 탐색과 같은 방법으로 키 k가 이미 존재하는지 판단한다.

 

리프 노드에 도달하면 해당 위치에 k를 삽입한다.

 

 

삭제

먼저 k에 대해 탐색하여 노드 v를 찼았다고 가정하자.

 

v의 두 자식이 모두 리프 노드라면 v를 삭제한다.

 

둘 중 하나가 리프 노드 w라면, w에 대해 removeAboveExternal를 시행한다.

 

둘 모두 internal 노드라면, 트리 inorder순 다음 노드 w를 v에 덮어 씌운다.

 

w의 왼쪽 자식(반드시 리프 노드)에 대해 removeAboveExternal를 시행한다.

 

* removeAboveExternal: 부모 노드와 자신을 삭제하고, Sibling Node를 부모 노드에 덮어 씌운다.

 

 

효율

N개의 item을 가지는 높이 h의 BST에 대해

 

공간복잡도 O(N)

 

find, insert, erase O(h)

 

이다.

 

h는 최선의 경우 log N이지만, 최악의 경우를 고려하여 O(N)이다.

 

 

구현

아래는 이론에서 배운 내용을 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int dat;
    Node* lc, * rc, * par;
    Node() { lc = rc = par = nullptr; }
    Node(int d) { dat = d; lc = rc = par = nullptr; }

    void inorder() {
        if (lc) lc->inorder();
        cout << dat << " ";
        if (rc) rc->inorder();
    }
};

struct BST {
    Node* root;

    BST() { root = nullptr; }

    void put(int k) {
        Node* newNode = new Node(k);
        if (!root) { root = newNode; return; }

        Node* tar = nullptr;
        for (Node* cur = root; cur; cur = (k < cur->dat ? cur->lc : cur->rc)) {
            if (k == cur->dat) { delete newNode; return; } // duplicate
            tar = cur;
        }

        newNode->par = tar;
        if (k < tar->dat) tar->lc = newNode;
        else tar->rc = newNode;
    }
    Node* get(int k) {
        for (Node* cur = root; cur; cur = (k < cur->dat ? cur->lc : cur->rc)) {
            if (cur->dat == k) return cur;
        } return nullptr;
    }
    void erase(int k) {
        Node* tar = get(k);
        Node* par = tar->par;
        int childCnt = bool(tar->lc) + bool(tar->rc);

        if (childCnt == 0) {
            if (tar == root) { delete root; root = nullptr; }
            else {
                if (tar->dat < par->dat) par->lc = nullptr;
                else par->rc = nullptr;
                delete tar;
            }
        }
        else if (childCnt == 1) {
            if (tar == root) { root = (tar->lc ? tar->lc : tar->rc); }
            else {
                Node* child = (tar->lc ? tar->lc : tar->rc);
                child->par = par;
                if (child->dat < par->dat) par->lc = child;
                else par->rc = child;
            }
        }
        else {
            Node* minNode = getMin(tar->rc); // next inorder node
            int t = minNode->dat;
            erase(minNode->dat);
            tar->dat = t;
        }
    }

    Node* getMin(Node* N) {
        for (Node* cur = N; cur; cur = cur->lc) {
            if (!cur->lc) return cur;
        } return N;
    }

    void inorder() {
        if (!root) {
            cout << "EMPTY\n";
            return;
        }
        root->inorder();
        cout << "\n";
    }
};

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

    BST T;

    int TEST; cin >> TEST; while (TEST--) {
        string oper; int p;
        cin >> oper; if (oper != "print") cin >> p;
        if (oper == "put") T.put(p);
        if (oper == "get") cout << (T.get(p) ? "YES\n" : "NO\n");
        if (oper == "erase") T.erase(p);
        if (oper == "print") T.inorder();
    }
}