[c++] 이진 트리 검색 알고리즘

15 Dec 2023

이진 트리 검색 알고리즘

이진 트리 검색 알고리즘은 재귀 혹은 반복문을 이용하여 구현할 수 있습니다.

재귀 알고리즘

class Node {
public:
    int data;
    Node* left;
    Node* right;
};

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);
}

반복문 알고리즘

Node* search(Node* root, int key) {
    while (root != nullptr && root->data != key) {
        if (key < root->data) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return root;
}

이진 트리 검색 알고리즘 시간 복잡도

BST에서 검색 알고리즘은 각 단계마다 현재 노드와 비교하고 왼쪽이나 오른쪽으로 이동하므로, 시간 복잡도는 O(h)입니다. 여기서 h는 트리의 높이를 나타냅니다. 가장 좋은 경우에는 O(log n), 최악의 경우에는 O(n)의 시간 복잡도를 갖습니다.

BST의 성능을 향상시키기 위해서는 균형 잡힌 트리(Balanced Tree)를 유지하는 것이 중요합니다.

참고문헌:

Introduction to Algorithms, 3rd Edition. Thomas H. Cormen et al.
Data Structures and Algorithms in C++, 2nd Edition. Michael T. Goodrich et al.