[c++] 이진 탐색 트리(Binary Search Tree) 데이터 구조

08 Dec 2023

이진 탐색 트리는 데이터를 저장하고 탐색하는 데 사용되는 자료구조이다. 이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며 다음을 만족하는 트리이다.

모든 왼쪽 자식 노드의 값은 해당 노드의 값보다 작다.
모든 오른쪽 자식 노드의 값은 해당 노드의 값보다 크다.

이진 탐색 트리의 특징

추가, 탐색, 삭제 연산을 평균 O(log n)의 시간 복잡도로 수행할 수 있다.
데이터를 정렬된 상태로 유지할 수 있다.

이진 탐색 트리의 구현

#include <iostream>

class Node {
public:
    int key;
    Node* left;
    Node* right;

    Node(int value) {
        key = value;
        left = nullptr;
        right = nullptr;
    }
};

class BST {
private:
    Node* root;

public:
    BST() {
        root = nullptr;
    }

    void insert(int key) {
        root = insertRecursive(root, key);
    }

    Node* insertRecursive(Node* currentNode, int key) {
        if (currentNode == nullptr) {
            return new Node(key);
        }

        if (key < currentNode->key) {
            currentNode->left = insertRecursive(currentNode->left, key);
        } else if (key > currentNode->key) {
            currentNode->right = insertRecursive(currentNode->right, key);
        }

        return currentNode;
    }

    Node* search(int key) {
        return searchRecursive(root, key);
    }

    Node* searchRecursive(Node* currentNode, int key) {
        if (currentNode == nullptr || currentNode->key == key) {
            return currentNode;
        }

        if (key < currentNode->key) {
            return searchRecursive(currentNode->left, key);
        }

        return searchRecursive(currentNode->right, key);
    }
};

이진 탐색 트리의 활용

이진 탐색 트리는 자료의 삽입, 삭제 및 탐색에 효율적으로 사용될 수 있다. 또한 정렬된 자료의 유지 및 검색에도 유용하게 사용될 수 있다.

이진 탐색 트리의 특징

이진 탐색 트리의 구현

이진 탐색 트리의 활용

참고 자료