[C++로 배우는 알고리즘과 자료구조] Day 7: 이진 탐색 트리 (BST)

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

이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식 노드를 가지는 이진 트리의 일종으로, 왼쪽 서브트리의 모든 값은 루트의 값보다 작고, 오른쪽 서브트리의 모든 값은 루트의 값보다 큰 속성을 가집니다. 이러한 속성 덕분에 BST는 효율적인 검색, 삽입, 삭제 연산을 지원합니다.

BST의 주요 연산:

1. 삽입 (Insert): 새로운 값을 트리에 삽입합니다.
2. 검색 (Search): 특정 값을 트리에서 검색합니다.
3. 삭제 (Delete): 트리에서 특정 값을 삭제합니다.
4. 순회 (Traversal): 트리의 노드를 특정 순서로 방문합니다.

BST 구현

BinarySearchTree.h

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include <iostream>

// 이진 탐색 트리의 노드 구조체
struct TreeNode {
    int data; // 데이터
    TreeNode* left; // 왼쪽 자식 노드
    TreeNode* right; // 오른쪽 자식 노드

    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {} // 노드 생성자
};

// 이진 탐색 트리 클래스
class BinarySearchTree {
public:
    BinarySearchTree() : root(nullptr) {} // 생성자
    ~BinarySearchTree(); // 소멸자

    void insert(int value); // 값 삽입
    bool search(int value) const; // 값 검색
    void remove(int value); // 값 삭제
    void inOrderTraversal() const; // 중위 순회

private:
    TreeNode* root; // 트리의 루트 노드

    void insert(TreeNode*& node, int value); // 값 삽입 (재귀)
    bool search(TreeNode* node, int value) const; // 값 검색 (재귀)
    TreeNode* remove(TreeNode* node, int value); // 값 삭제 (재귀)
    TreeNode* findMin(TreeNode* node) const; // 최소값 찾기 (재귀)
    void inOrderTraversal(TreeNode* node) const; // 중위 순회 (재귀)
    void destroy(TreeNode* node); // 트리 파괴 (재귀)
};

// 소멸자 정의 (메모리 해제)
BinarySearchTree::~BinarySearchTree() {
    destroy(root);
}

// 트리 파괴 함수 정의 (재귀)
void BinarySearchTree::destroy(TreeNode* node) {
    if (node != nullptr) {
        destroy(node->left);
        destroy(node->right);
        delete node; // 노드 메모리 해제
    }
}

// 값 삽입 함수 정의 (재귀)
void BinarySearchTree::insert(TreeNode*& node, int value) {
    if (node == nullptr) {
        node = new TreeNode(value); // 새로운 노드 생성
    } else if (value < node->data) {
        insert(node->left, value); // 왼쪽 서브트리에 삽입
    } else if (value > node->data) {
        insert(node->right, value); // 오른쪽 서브트리에 삽입
    }
}

// 값 삽입 함수 정의
void BinarySearchTree::insert(int value) {
    insert(root, value);
}

// 값 검색 함수 정의 (재귀)
bool BinarySearchTree::search(TreeNode* node, int value) const {
    if (node == nullptr) {
        return false; // 값을 찾지 못함
    } else if (value < node->data) {
        return search(node->left, value); // 왼쪽 서브트리에서 검색
    } else if (value > node->data) {
        return search(node->right, value); // 오른쪽 서브트리에서 검색
    } else {
        return true; // 값을 찾음
    }
}

// 값 검색 함수 정의
bool BinarySearchTree::search(int value) const {
    return search(root, value);
}

// 최소값 찾기 함수 정의 (재귀)
TreeNode* BinarySearchTree::findMin(TreeNode* node) const {
    while (node->left != nullptr) {
        node = node->left; // 왼쪽 자식 노드로 이동
    }
    return node;
}

// 값 삭제 함수 정의 (재귀)
TreeNode* BinarySearchTree::remove(TreeNode* node, int value) {
    if (node == nullptr) {
        return node; // 값을 찾지 못함
    } else if (value < node->data) {
        node->left = remove(node->left, value); // 왼쪽 서브트리에서 삭제
    } else if (value > node->data) {
        node->right = remove(node->right, value); // 오른쪽 서브트리에서 삭제
    } else {
        // 노드를 찾음
        if (node->left == nullptr && node->right == nullptr) {
            delete node; // 리프 노드인 경우 바로 삭제
            node = nullptr;
        } else if (node->left == nullptr) {
            TreeNode* temp = node; 
            node = node->right; // 오른쪽 자식 노드가 있는 경우
            delete temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node;
            node = node->left; // 왼쪽 자식 노드가 있는 경우
            delete temp;
        } else {
            // 양쪽 자식 노드가 있는 경우
            TreeNode* temp = findMin(node->right); // 오른쪽 서브트리에서 최소값 찾기
            node->data = temp->data; // 데이터 복사
            node->right = remove(node->right, temp->data); // 오른쪽 서브트리에서 최소값 삭제
        }
    }
    return node;
}

// 값 삭제 함수 정의
void BinarySearchTree::remove(int value) {
    root = remove(root, value);
}

// 중위 순회 함수 정의 (재귀)
void BinarySearchTree::inOrderTraversal(TreeNode* node) const {
    if (node != nullptr) {
        inOrderTraversal(node->left);
        std::cout << node->data << " ";
        inOrderTraversal(node->right);
    }
}

// 중위 순회 함수 정의
void BinarySearchTree::inOrderTraversal() const {
    inOrderTraversal(root);
    std::cout << std::endl;
}

#endif // BINARYSEARCHTREE_H

 

BST 예제

#include <iostream>
#include "BinarySearchTree.h"

int main() {
    BinarySearchTree bst;
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(2);
    bst.insert(4);
    bst.insert(6);
    bst.insert(8);

    std::cout << "중위 순회: ";
    bst.inOrderTraversal(); // 중위 순회 출력

    std::cout << "7 검색: " << (bst.search(7) ? "찾음" : "찾지 못함") << std::endl;
    std::cout << "10 검색: " << (bst.search(10) ? "찾음" : "찾지 못함") << std::endl;

    bst.remove(7);
    std::cout << "7 삭제 후 중위 순회: ";
    bst.inOrderTraversal(); // 중위 순회 출력

    return 0;
}

 

설명

1. 이진 탐색 트리 (Binary Search Tree, BST):
   • 이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 루트 노드보다 작은 값을, 오른쪽 자식 노드는 루트 노드보다 큰 값을 가집니다.
2. BST의 주요 연산:
   • 삽입 (Insert): 새로운 값을 트리에 삽입합니다. O(log n) 시간 복잡도를 가집니다.
   • 검색 (Search): 특정 값을 트리에서 검색합니다. O(log n) 시간 복잡도를 가집니다.
   • 삭제 (Delete): 트리에서 특정 값을 삭제합니다. O(log n) 시간 복잡도를 가집니다.
   • 순회 (Traversal): 트리의 노드를 특정 순서로 방문합니다.
3. 트리 순회:
   • 중위 순회 (In-order Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문합니다.
   • 전위 순회 (Pre-order Traversal): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문합니다.
   • 후위 순회 (Post-order Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 방문합니다.

이제 이진 탐색 트리의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 8: 균형 이진 탐색 트리 (AVL 트리)"에 대해 학습하겠습니다.