[알고리즘/C++] 이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리 (Binary Search Tree, BST)란?

이진 탐색 트리(BST)는 중요한 데이터 구조 중 하나로, 데이터를 효과적으로 저장하고 검색하는 데 사용된다.

 

 

이진 구조

---

BST는 모든 노드가 최대 두 개의 자식 노드를 가지는 이진 트리다. 각 노드는 최대 두 개의 하위 노드를 가질 수 있으며, 하위 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 구분된다.

 

정렬된 순서

---

BST는 중요한 특징 중 하나는 모든 노드의 왼쪽 하위 트리에는 현재 노드보다 작은 값의 노드만 포함되고, 모든 오른쪽 하위 트리에는 현재 노드보다 큰 값의 노드만 포함된다는 것입니다. 이러한 특성 덕분에 BST의 모든 노드는 정렬된 순서로 구성되어 있다.

 

 

추가 및 삭제

---

BST에 데이터를 추가하거나 삭제하는 작업도 효율적으로 수행할 수 있디. 데이터를 추가할 때는 이진 탐색의 원리를 따라 위치를 찾아 삽입하면 되고, 데이터를 삭제할 때는 몇 가지 경우에 대해 고려하면서 삭제를 수행한다.

 

 

구현

---

#include <iostream>

// 이진 탐색 트리 노드를 표현하는 구조체
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
private:
    Node* root;

public:
    BinarySearchTree() {
        root = nullptr;
    }

    // BST에 노드 삽입
    Node* insert(Node* root, int value) {
        if (root == nullptr) {
            return new Node(value);
        }
        if (value < root->data) {
            root->left = insert(root->left, value);
        } else if (value > root->data) {
            root->right = insert(root->right, value);
        }
        return root;
    }

    void insert(int value) {
        root = insert(root, value);
    }

    // BST에서 값 찾기
    bool search(Node* root, int value) {
        if (root == nullptr) {
            return false;
        }
        if (root->data == value) {
            return true;
        } else if (value < root->data) {
            return search(root->left, value);
        } else {
            return search(root->right, value);
        }
    }

    bool search(int value) {
        return search(root, value);
    }
};

int main() {
    BinarySearchTree bst;
    bst.insert(10);
    bst.insert(5);
    bst.insert(15);
    bst.insert(3);
    bst.insert(7);
    bst.insert(18);

    std::cout << "Searching for 7: " << (bst.search(7) ? "Found" : "Not found") << std::endl;
    std::cout << "Searching for 12: " << (bst.search(12) ? "Found" : "Not found") << std::endl;

    return 0;
}

 

 

장단점

---

장점

1. 효율적인 검색: BST는 데이터를 검색하는 데 매우 효율적입니다. 이진 탐색 알고리즘을 이용하여 원하는 값을 찾아가므로 평균적으로 O(log n)의 시간 복잡도를 가진다.
2. 정렬된 데이터 저장: BST의 모든 노드는 정렬된 순서로 구성되어 있다. 따라서 데이터를 정렬된 상태로 저장하고 유지하는데 유용하며, 범위 기반 검색이나 범위 쿼리에 효과적이다.
3. 추가와 삭제의 용이성: 데이터를 추가하거나 삭제할 때, 적절한 위치를 찾아 삽입하거나 삭제하는 작업이 비교적 간단하다. 이진 탐색 트리의 특성을 유지하면서 데이터를 추가하거나 삭제할 수 있다.
4. 중위 순회(In-order traversal): BST는 중위 순회를 이용하여 데이터를 정렬된 순서로 순회할 수 있습니다. 이는 데이터 정렬 및 출력에 유용하다.

단점

1. 균형 잡힌 트리 필요: 이진 탐색 트리는 데이터가 정렬된 순서대로 삽입될 때 최상의 성능을 보이지만, 데이터가 무작위로 삽입될 경우 트리의 균형이 깨질 수 있다. 이로 인해 최악의 경우 시간 복잡도가 O(n)이 될 수 있다.
2. 최악의 경우 시간 복잡도: 균형 잡힌 트리가 아닌 경우, BST의 높이가 데이터 수에 따라 선형적으로 증가할 수 있으므로 최악의 경우 시간 복잡도가 O(n)이 된다.
3. 메모리 사용량: BST의 노드는 자식 노드를 가리키는 포인터를 저장하므로 메모리 사용량이 크다는 단점이 있다.
4. 트리 재구성: 데이터를 계속 삽입하거나 삭제하면 BST의 균형이 깨질 수 있으며, 이를 해결하기 위해서 트리 재구성이 필요할 수 있다. 이를 위한 별도의 알고리즘과 작업이 필요하다.

---

BST는 검색과 관련된 작업에 효과적이지만, 트리의 균형이 깨질 경우 최악의 경우 시간 복잡도가 O(n)이 될 수 있다. 따라서 효율적인 BST를 유지하기 위해 균형 잡힌 이진 탐색 트리(AVL 트리 등)나 자가 균형 트리(Red-Black 트리 등)와 같은 변형된 형태의 BST도 사용된다.

이렇듯 이진 탐색 트리는 정렬된 데이터의 효율적인 저장과 검색을 위한 중요한 데이터 구조 중 하나다.