[c++] 이진 검색 트리(Binary Search Tree)

12 Dec 2023

이진 검색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드를 가지며, 특정 순서로 정렬되어 있는 이진 트리입니다. BST는 다음과 같은 특징을 가지고 있습니다.

특징

정렬된 순서: 왼쪽 자식 노드는 해당 노드보다 작고, 오른쪽 자식 노드는 해당 노드보다 큽니다.
탐색 효율성: 이진 검색 트리는 데이터를 탐색하는 데에 있어 빠른 성능을 제공합니다.
삽입/삭제 용이성: 새로운 데이터를 삽입하거나 삭제할 때, 특정 조건을 만족시킴으로써 효과적으로 처리할 수 있습니다.

예시 코드

#include <iostream>
using namespace std;

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

    Node(int k) {
        key = k;
        left = right = nullptr;
    }
};

Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);
    }
    
    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    }
    
    return root;
}

Node* search(Node* root, int key) {
    if (root == nullptr || root->key == key) {
        return root;
    }
    
    if (key < root->key) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

void inorder(Node* root) {
    if (root != nullptr) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

위의 예시 코드는 C++로 이진 검색 트리의 생성, 삽입, 탐색, 및 중위 순회(inorder traversal)를 구현한 것입니다.

BST는 효율적인 데이터 탐색 및 정렬에 사용되므로, 많은 종류의 알고리즘과 데이터 구조에서 사용되고 있습니다.

참고 자료

Introduction to Algorithms, 3rd Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press. 2009.
Data Structures and Algorithms in C++, 2nd Edition. Michael T. Goodrich, Roberto Tamassia, and David M. Mount. Wiley. 2011.