CS 공부 & 면접 맛보기 0x07 [자료구조] : 이진 탐색 트리(Binary Search Tree, BST) 설명

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

---

질문

이진 탐색 트리(Binary Search Tree, BST)란 무엇인가요?

---

답변

이진 탐색 트리(Binary Search Tree, BST)는 정렬된 데이터를 효율적으로 관리하기 위한 트리(Tree) 자료구조입니다.

특징:

• 이진 트리: 각 노드는 최대 두 개의 자식 노드를 가집니다.
• 정렬 규칙:
  • 왼쪽 서브트리의 노드는 부모보다 작은 값을 가짐.
  • 오른쪽 서브트리의 노드는 부모보다 큰 값을 가짐.
• 모든 노드는 고유한 키(Key)를 가짐.
• 시간 복잡도:
  • 트리의 높이가 h일 때, 탐색, 삽입, 삭제 연산은 O(h)의 시간 복잡도를 가집니다.
  • 평균적인 경우: O(log n)
  • 최악의 경우: O(n) (한쪽으로 치우친 트리)

---

이진 탐색 트리의 핵심 연산 및 동작 원리

1. 탐색 (Search)

• 원리:
  • 루트 노드에서 시작.
  • 찾는 값이 현재 노드의 값보다 작으면 왼쪽으로,
  • 더 크면 오른쪽 자식 노드로 이동.
  • 일치하는 값을 찾으면 검색 성공,
  • 리프 노드까지 도달했을 때 찾지 못하면 검색 실패.

C++ 코드 예제:

#include <iostream>
using namespace std;

// 노드 정의
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// BST 탐색 함수
Node* search(Node* root, int key) {
    if (root == nullptr || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

int main() {
    Node* root = new Node(8);
    root->left = new Node(3);
    root->right = new Node(10);
    root->left->left = new Node(1);
    root->left->right = new Node(6);
    
    int key = 6;
    Node* result = search(root, key);
    if (result) {
        cout << "Key " << key << " found in the BST." << endl;
    } else {
        cout << "Key " << key << " not found." << endl;
    }
    return 0;
}

 

---

2. 삽입 (Insert)

• 원리:
  • 탐색과 동일한 방식으로 진행.
  • 검색 실패 지점에 새로운 노드를 삽입.

C++ 코드 예제:

#include <iostream>
using namespace std;

// 노드 정의
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// BST 삽입 함수
Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else if (key > root->data) {
        root->right = insert(root->right, key);
    }
    return root;
}

// 중위 순회 (Inorder Traversal) - 트리의 정렬 확인
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 8);
    insert(root, 3);
    insert(root, 10);
    insert(root, 1);
    insert(root, 6);

    cout << "Inorder Traversal: ";
    inorder(root);  // 정렬된 순서로 출력
    cout << endl;
    return 0;
}

---

3. 삭제 (Delete)

삭제의 경우 3가지 시나리오로 나뉩니다:

(1) 삭제하려는 노드가 단말 노드인 경우 (리프 노드)

• 부모 노드의 해당 포인터를 nullptr로 설정.

(2) 삭제하려는 노드가 하나의 서브트리만 있는 경우

• 부모 노드의 해당 포인터를 자식 노드로 연결.

(3) 삭제하려는 노드가 두 개의 서브트리를 가진 경우

• **오른쪽 서브트리에서 최소값(후계자 노드)**을 찾아 삭제할 노드의 위치로 값을 옮기고, 해당 노드를 제거.

C++ 코드 예제:

#include <iostream>
using namespace std;

// 노드 정의
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// 최소값 찾기 (서브트리에서)
Node* findMin(Node* root) {
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

// BST 삽입 함수
Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else if (key > root->data) {
        root->right = insert(root->right, key);
    }
    return root;
}

// BST 삭제 함수
Node* deleteNode(Node* root, int key) {
    if (root == nullptr) {
        return root;
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // Case 1: 리프 노드 삭제
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // Case 2: 자식이 하나만 있는 경우
        else if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        // Case 3: 자식이 둘 다 있는 경우
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

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

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    cout << "트리 중위 순회: ";
    inorder(root);
    cout << "\n노드 50 삭제 후: ";
    root = deleteNode(root, 50);
    inorder(root);
    cout << endl;

    return 0;
}

 

---

시간 및 공간 복잡도

연산 | 평균 시간 복잡도 | 최악의 시간 복잡도 | 공간 복잡도

탐색	O(log n)	O(n)	O(n)
삽입	O(log n)	O(n)	O(n)
삭제	O(log n)	O(n)	O(n)

---

결론

• 이진 탐색 트리(BST)는 정렬된 데이터를 효율적으로 관리할 수 있는 자료구조입니다.
• 삽입, 삭제, 탐색의 평균 시간 복잡도는 O(log n)이지만, 불균형 트리의 경우 O(n)까지 성능이 저하될 수 있습니다.
• C++에서는 재귀적으로 구현하는 것이 일반적이며, 균형 유지를 위해 AVL 트리와 같은 구조도 고려될 수 있습니다.