Binary Search Tree

Binary Search Tree

이진 트리의 일종, 각 노드가 최대 두 개의 자식을 가지며, 특정한 규칙에 따라 정렬된 트리
왼쪽 < 부모 < 오른쪽 (값 크기 순서대로)

Implementation

#include<iostream>
using namespace std;

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

    explicit Node(int value) : data(value), left(nullptr), right(nullptr){}
};

class BinarySearchTree {
private:
    Node* root;

    // 삽입 함수 (재귀)
    Node* insert(Node* node, int value) {
        if(node == nullptr) {
            return new Node(value);
        }
        if(value < node->data) {
            node->left = insert(node->left, value);
        } else if(value > node->data) {
            node->right = insert(node->right, value);
        }
        return node;
    }

    // 탐색 함수 (재귀)
    bool search(Node* node, int value) {
        if(node == nullptr) return false;
        if(node->data == value) return true;
        if(value < node->data) return search(node->left, value);
        return search(node->right, value);
    }

    // 삭제 함수 (재귀)
    Node* deleteNode(Node* node, int value) {
        if(node == nullptr) return nullptr;

        // 삭제할 값이 현재 노드의 값보다 작으면 왼쪽 서브트리에서 탐색
        if(value < node->data) {
            node->left = deleteNode(node->left, value);
        } else if(value > node->data) {     // 삭제할 값이 현재 노드의 값보다 크면 오르쪽 서브트리에서 탐색
            node->right = deleteNode(node->right, value);
        } else {
            // 자식이 없는 경우
            if(node->left == nullptr && node->right == nullptr) {
                delete node;
                return nullptr;
            } else if(node->left == nullptr) {  // 자식이 하나: 오른쪽 자식이 있는 경우
                Node* temp = node->right;
                delete node;
                return temp;
            } else if(node->right == nullptr) { // 자식이 하나: 왼쪽 자식이 있는 경우
                Node* temp = node->left;
                delete node;
                return temp;
            } else {    // 자식이 둘인 경우
                // 오른쪽 자식에서 가장 작은 노드 찾기
                Node* temp = findMin(node->right);
                // 그 찾은 노드의 값을 넣기
                node->data = temp->data;
                // 오른쪽 자식에서 그 찾은 노드를 삭제
                node->right  = deleteNode(node->right, temp->data);
            }
        }
        return node;
    }

    // 최솟값 찾기 (삭제 연산에서 사용)
    Node* findMin(Node* node) {
        while(node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // In-order Traversal
    void inorderTraversal(Node* node) {
        if(node == nullptr) return;
        inorderTraversal(node->left);
        cout<<node->data<<" ";
        inorderTraversal(node->right);
    }
public:
    // 생성자
    BinarySearchTree() : root(nullptr){}

    // 삽입 함수
    void insert(int value) {
        root = insert(root, value);
    }

    // 탐색 함수
    bool search(int value) {
        return search(root, value);
    }

    // 삭제 함수
    void deleteNode(int value) {
        root = deleteNode(root, value);
    }

    // Inorder 출력
    void inorderTraversal() {
        inorderTraversal(root);
        cout<<endl;
    }
};

int main() {
    BinarySearchTree bst;

    bst.insert(10);
    bst.insert(5);
    bst.insert(20);
    bst.insert(3);
    bst.insert(7);

    cout<<"In-order Traversal: "<<endl;
    bst.inorderTraversal();

    cout<<"Search for 10: "<<bst.search(10)<<endl;
    cout<<"Sear for 15: "<<bst.search(15)<<endl;

    bst.deleteNode(5);
    bst.inorderTraversal();

    return EXIT_SUCCESS;
}

Output

Efficiency

Linked List 기반 효율표

	Time Complexity (Average)	Time Complexity (Worst)	Explaination
삽입	O(log n)	O(n)	삽입할 위치를 찾은 뒤 값을 추가하는 과정도 탐색과 동일
삭제	O(log n)	O(n)	삭제할 노드를 찾고, 자식 노드의 개수에 따라 적절히 처리해야 함
탐색	O(log n)	O(n)	균형잡힌 경우 로그 시간, 한쪽으로 치우쳐지면 n

Efficiency Summary

균형이 잘 잡혀있는 트리인 경우 탐색, 삽입, 삭제 연산 모두 효율적
정렬된 데이터에 대해 검색, 삽입, 삭제를 할때 효율적
탐색과 삽입의 빈도가 높은 경우 적합

트리가 한쪽으로 치우쳐진 경우 부적합 (비균형 트리)
중복된 값이 많은 경우 비효율적 (비균형 트리 가능성)
탐색보다 순차 데이터 접근이 빈번한 경우 부적합, vector가 적합
삭제가 빈번한 경우 부적합 (비균형 트리 가능성)

STL

std::set

unique한 값들을 정렬된 상태로 저장하는 컨테이너
중복값 허용 X
자동으로 오름차순 정렬

std::map

key-value 쌍을 저장, 키를 기준으로 정렬된 상태로 관리하는 컨테이너
중복 key 허용 X
모든 키가 자동으로 오름차순으로 정렬

std::multiset, std::multimap

std::set과 std::map과 유사. 단, 중복 값/키를 허용

위 STL 컨테이너들은 모두 Red-Black Tree로 구현됨