[c++] 이진 검색 트리 (BST)

08 Dec 2023

BST에서의 검색, 삽입, 삭제 연산은 각각 O(h)의 시간 복잡도를 가집니다. 이때 h는 트리의 높이입니다. 이진 검색 트리가 균형적으로 구성되어 있지 않을 때는 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다. 균형을 맞추기 위해 AVL 트리, 레드-블랙 트리 등의 균형을 유지하는 트리로 변형될 수 있습니다.

아래는 C++로 작성된 간단한 BST의 예시입니다.

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
}

class BST {
public:
    Node* root;
    
    BST() {
        root = NULL;
    }

    Node* insert(Node* node, int key) {
        if (node == NULL) {
            Node* newNode = new Node();
            newNode->key = key;
            newNode->left = NULL;
            newNode->right = NULL;
            return newNode;
        }

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

        return node;
    }

    Node* search(Node* node, int key) {
        if (node == NULL || node->key == key) {
            return node;
        }

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

여기서 insert와 search 함수는 각각 노드를 삽입하고 찾는 역할을 합니다. 각 연산은 재귀적으로 수행됩니다.

관련 참고 자료:
https://en.wikipedia.org/wiki/Binary_search_tree