이진탐색트리(Binary Search Tree)

이진 탐색 트리 Binary Search Tree 는 탐색 효율을 높이기 위해 데이터를 정렬된 형태로 저장하는 트리 구조다.
트리 Tree 는 계층적인 구조를 가진 자료구조로, 부모 노드 Parent 와 자식 노드 Child 로 구성되어 있다.
이진 탐색 트리는 그중에서도 각 노드가 최대 두 개의 자식 노드를 가지며, 특정한 규칙에 따라 정렬되어 있는 트리다.

---

이진 탐색 트리의 특징

이진 탐색 트리에서는 각 노드에 대해 다음의 규칙이 적용된다.

1. 왼쪽 서브트리 Left Subtree 에 있는 모든 노드의 값은 부모 노드보다 작다.
2. 오른쪽 서브트리 Right Subtree 에 있는 모든 노드의 값은 부모 노드보다 크다.
3. 각 서브트리 역시 이진 탐색 트리의 성질을 만족한다.

이 규칙 덕분에 탐색, 삽입, 삭제 연산이 평균적으로 O log N 시간복잡도로 수행된다.

---

이진 탐색 트리의 구조 예시

아래는 간단한 예시다.

 

       8
     /   \
    3     10
   / \      \
  1   6      14
     / \    /
    4   7  13

• 루트 Root 는 8이다.
• 8보다 작은 값은 왼쪽으로, 8보다 큰 값은 오른쪽으로 배치되어 있다.
• 예를 들어 6은 3보다 크므로 3의 오른쪽 자식으로, 8보다 작으므로 8의 왼쪽 서브트리에 위치한다.

---

이진 탐색 트리의 주요 연산

이진 탐색 트리에서는 다음과 같은 연산이 가능하다.

1. 탐색 Search
   원하는 값이 트리에 존재하는지 찾는다.
   루트부터 시작해 찾는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다.
2. 삽입 Insert
   새로운 값을 트리에 추가한다.
   트리의 규칙을 유지하면서 적절한 위치를 찾아 삽입한다.
3. 삭제 Delete
   특정 값을 가진 노드를 트리에서 제거한다.
   삭제할 노드의 자식 수에 따라 처리 방식이 다르다.
   • 자식이 없는 경우 단순히 제거한다.
   • 자식이 하나인 경우 자식을 부모에 연결한다.
   • 자식이 두 개인 경우 오른쪽 서브트리에서 가장 작은 노드로 교체한다.

---

예시 코드

아래는 간단한 이진 탐색 트리의 구현 예제다.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(NULL), right(NULL) {}
};

// 삽입 함수
Node* insert(Node* root, int val) {
    if (root == NULL)
        return new Node(val);

    if (val < root->data)
        root->left = insert(root->left, val);
    else if (val > root->data)
        root->right = insert(root->right, val);

    return root;
}

// 탐색 함수
bool search(Node* root, int val) {
    if (root == NULL)
        return false;
    if (root->data == val)
        return true;
    else if (val < root->data)
        return search(root->left, val);
    else
        return search(root->right, val);
}

// 중위 순회 함수
void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = NULL;
    root = insert(root, 8);
    insert(root, 3);
    insert(root, 10);
    insert(root, 1);
    insert(root, 6);
    insert(root, 14);
    insert(root, 4);
    insert(root, 7);
    insert(root, 13);

    cout << "중위 순회 결과: ";
    inorder(root);
    cout << endl;

    int target = 6;
    if (search(root, target))
        cout << target << "을 찾았다" << endl;
    else
        cout << target << "이 존재하지 않는다" << endl;
}

---

이진 탐색 트리의 시간 복잡도

• 탐색, 삽입, 삭제 평균 시간복잡도: O log N
• 최악의 경우 시간복잡도: O N
  (한쪽으로만 계속 자식이 추가되어 선형 구조가 되었을 때)

이런 문제를 해결하기 위해 AVL 트리나 레드 블랙 트리처럼 자동으로 균형을 맞추는 균형 이진 탐색 트리 Balanced BST 가 사용되기도 한다.

---

정리

이진 탐색 트리는 데이터를 빠르게 탐색하고 정렬된 형태로 유지할 수 있는 효율적인 구조다.
탐색 성능이 배열이나 연결 리스트보다 훨씬 우수하며,
정렬된 데이터를 다루거나 탐색 속도가 중요한 프로그램에서 자주 활용된다.