C++로 구현하는 이진 탐색 트리(BST) 최솟값 노드 찾기

이진 탐색 트리(Binary Search Tree, BST)가 주어졌을 때, 트리 내에서 가장 작은 값을 가진 노드를 찾는 방법을 알아보겠습니다. 예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 봅시다.

이 트리에서 최솟값은 1입니다.

핵심 아이디어

이진 탐색 트리의 가장 중요한 특징은 왼쪽 서브트리에는 항상 부모 노드보다 작은 값들이 위치한다는 점입니다. 따라서 왼쪽 자식 노드가 더 이상 존재하지 않을 때(즉, left가 NULL일 때)까지 계속해서 왼쪽으로 이동하면, 그 위치의 노드가 곧 트리 전체에서 가장 작은 값이 됩니다.

알고리즘 동작 순서

1. 루트 노드에서 시작합니다.
2. 현재 노드의 왼쪽 자식이 NULL이 아니면 왼쪽 자식으로 이동합니다.
3. 왼쪽 자식이 NULL인 노드에 도달하면, 해당 노드의 값이 최솟값입니다.

C++ 구현 예제

#include<iostream>
using namespace std;

class node {
public:
    node *left;
    int val;
    node *right;
};

node *bst = NULL;

node *getNode() {
    node *newNode;
    newNode = new node;
    return newNode;
}

void insert(node **root, int key) {
    node *newNode;
    newNode = getNode();
    newNode->val = key;
    newNode->left = NULL;
    newNode->right = NULL;

    if (*root == NULL) {
        *root = newNode;
        return;
    } else {
        if (key < (*root)->val)
            insert(&((*root)->left), key);
        else
            insert(&((*root)->right), key);
    }
}

int minElement() {
    node* current = bst;
    while (current->left != NULL) {
        current = current->left;
    }
    return(current->val);
}

main() {
    int item[] = {3, 2, 1, 6, 5, 8};
    int n = sizeof(item)/sizeof(item[0]);
    int i;
    for(i = 0; i<8; i++){
        insert(&bst, item[i]);
    }
    cout << "Minimum element is: " << minElement();
}

실행 결과

Minimum element is: 1

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 트리의 높이에 비례합니다. 균형 잡힌 이진 탐색 트리의 경우 O(log n), 최악의 경우(노드가 한쪽으로 치우친 편향 트리)에는 O(n)이 됩니다. 공간 복잡도는 반복문을 사용했기 때문에 O(1)입니다.

마무리

이진 탐색 트리에서 최솟값을 찾는 것은 트리의 정렬된 구조적 특성을 활용하는 대표적인 예제입니다. 같은 원리로 오른쪽 끝 노드까지 이동하면 최댓값도 손쉽게 구할 수 있으니, 함께 응용해 보시기 바랍니다.