C++로 이진 탐색 트리(BST)의 최솟값 찾기 – 알고리즘과 예제 코드

이 글에서는 C++를 사용하여 이진 탐색 트리(Binary Search Tree, BST)에서 최솟값을 찾는 프로그램을 소개합니다.

이진 탐색 트리의 핵심 성질 덕분에 최솟값을 찾는 것은 매우 간단합니다. BST에서는 모든 노드에 대해 왼쪽 자식은 부모보다 작거나 같고, 오른쪽 자식은 부모보다 크거나 같은 규칙이 유지됩니다. 따라서 루트 노드에서 시작해 왼쪽 자식 노드를 계속 따라 내려가면, 더 이상 왼쪽 자식이 없는 가장 왼쪽 끝 노드의 값이 곧 트리의 최솟값이 됩니다.

알고리즘

최솟값을 찾는 절차는 다음과 같습니다.

시작
    구조체 nd를 선언한다.
    정수형 변수 d를 선언한다.
    nd 구조체 타입의 포인터 lt(왼쪽 자식)를 선언한다.
    nd 구조체 타입의 포인터 rt(오른쪽 자식)를 선언한다.

    [new_nd() 함수 - 새 노드 생성]
    정수 d를 매개변수로 받는다.
    nd 포인터에 malloc으로 메모리를 할당한다.
        nd = (struct nd*) malloc(sizeof(struct nd))
    nd->d = d 로 값을 저장한다.
    nd->lt = NULL, nd->rt = NULL 로 초기화한다.
    nd를 반환한다.

    [add_node() 함수 - 노드 삽입]
    nd 포인터와 정수 d를 매개변수로 받는다.
    만약 nd == NULL 이면
        new_nd(d)를 반환한다. (새 노드 생성)
    아니라면
        만약 d <= nd->d 이면
            nd->lt = add_node(nd->lt, d)  // 왼쪽 서브트리에 삽입
        아니라면
            nd->rt = add_node(nd->rt, d)  // 오른쪽 서브트리에 삽입
    nd를 반환한다.

    [minimum_val() 함수 - 최솟값 탐색]
    nd 포인터를 매개변수로 받는다.
    cur 포인터를 선언하고 nd로 초기화한다.
    cur->lt != NULL 인 동안 반복
        cur = cur->lt  // 왼쪽 자식으로 계속 이동
    cur->d 를 반환한다.  // 가장 왼쪽 노드의 값이 최솟값

    [main 함수]
    root 포인터를 선언하고 NULL로 초기화한다.
    root = add_node(root, 54)
    add_node(root, 32)
    add_node(root, 25)
    add_node(root, 45)
    add_node(root, 65)
    add_node(root, 75)
    "주어진 이진 탐색 트리의 최솟값은: " 을 출력한다.
    minimum_val(root)의 결과를 출력한다.
끝.

예제 코드

위 알고리즘을 그대로 구현한 전체 C++ 코드입니다.

#include <bits/stdc++.h>
using namespace std;

struct nd {
    int d;
    struct nd* lt;
    struct nd* rt;
};

// 새 노드를 생성하는 함수
struct nd* new_nd(int d) {
    struct nd* nd = (struct nd*)
    malloc(sizeof(struct nd));
    nd->d = d;
    nd->lt = NULL;
    nd->rt = NULL;
    return(nd);
}

// 트리에 노드를 삽입하는 함수
struct nd* add_node(struct nd* nd, int d) {
    if (nd == NULL)
        return(new_nd(d));
    else {
        if (d <= nd->d)
            nd->lt = add_node(nd->lt, d);
        else
            nd->rt = add_node(nd->rt, d);
        return nd;
    }
}

// 최솟값을 찾는 함수
int minimum_val(struct nd* nd) {
    struct nd* cur = nd;
    while (cur->lt != NULL) {
        cur = cur->lt;
    }
    return(cur->d);
}

int main() {
    struct nd* root = NULL;
    root = add_node(root, 54);
    add_node(root, 32);
    add_node(root, 25);
    add_node(root, 45);
    add_node(root, 65);
    add_node(root, 75);

    cout << "The Minimum value of the given binary search tree is: " << minimum_val(root);
    getchar();
    return 0;
}

코드 동작 원리

minimum_val() 함수가 이 프로그램의 핵심입니다. 현재 노드를 가리키는 cur 포인터를 루트로 초기화한 뒤, 왼쪽 자식(lt)이 NULL이 아닌 동안 계속 왼쪽으로 이동합니다. 반복문이 종료되는 시점의 cur는 트리에서 가장 왼쪽에 있는 노드, 즉 값이 가장 작은 노드이므로 해당 노드의 데이터를 반환하면 됩니다.

이 방식의 시간 복잡도는 트리의 높이에 비례합니다. 균형 잡힌 BST라면 O(log n), 최악의 경우(편향 트리)에는 O(n)이 됩니다.

출력 결과

The Minimum value of the given binary search tree is: 25

삽입된 값 54, 32, 25, 45, 65, 75 중 가장 작은 값인 25가 올바르게 출력되는 것을 확인할 수 있습니다.