이 글에서는 이진 검색 접근 방식을 사용하여 정렬되지 않은 배열에서 최소 요소를 찾는 C++ 프로그램을 소개합니다. 먼저 주어진 데이터로 이진 검색 트리(Binary Search Tree)를 구성한 뒤, 루트에서 가장 왼쪽 끝에 있는 노드로 이동하면 그 값이 곧 전체 데이터의 최솟값이 됩니다. 이 방식의 시간 복잡도는 O(log(n))입니다.
알고리즘
시작 주어진 정렬되지 않은 데이터 배열에 대해 이진 검색 트리를 구성합니다. 최소 요소를 찾기 위해 포인터를 가장 왼쪽 자식 노드로 이동합니다. 이 값을 주어진 데이터 집합의 최솟값으로 출력합니다. 종료
예제 코드
#include<iostream>
using namespace std;
struct node {
int d;
node *left;
node *right;
};
node* CreateNode(int d) {
node *newnode = new node;
newnode->d = d;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
node* InsertIntoTree(node* root, int d) {
node *temp = CreateNode(d);
node *t = new node;
t = root;
if(root == NULL)
root = temp;
else{
while(t != NULL) {
if(t->d < d) {
if(t->right == NULL) {
// 현재 노드의 자식이 NULL이면 새 노드를 삽입합니다.
t->right = temp;
break;
}
// 포인터를 오른쪽 자식 노드로 이동합니다.
t = t->right;
}
else if(t->d > d) {
if(t->left == NULL) {
t->left = temp;
break;
}
t = t->left;
}
}
}
return root;
}
int main() {
int n, i, a[10]={86, 63, 95, 6, 7, 67, 52, 26, 45, 98};
node *root = new node;
root = NULL;
cout<<"\nData set:\n";
for(i = 0; i < 10; i++) {
cout<<a[i]<<" ";
root = InsertIntoTree(root, a[i]);
}
cout<<"\n\nThe minimum element of the given data set is ";
i = 0;
while(root->left != NULL) {
i++;
root = root->left;
}
cout<<root->d<<" which found at "<<i<<" depth from the root.";
return 0;
}실행 결과
Data set: 86 63 95 6 7 67 52 26 45 98 The minimum element of the given data set is 6 which found at 2 depth from the root.
코드 설명
프로그램은 크게 세 부분으로 구성됩니다.
1. 노드 생성(CreateNode): 새로운 노드를 동적으로 할당하고, 데이터 값(d)과 좌우 자식 포인터(left, right)를 초기화합니다.
2. 트리 삽입(InsertIntoTree): 이진 검색 트리의 규칙에 따라 값을 삽입합니다. 삽입할 값이 현재 노드보다 크면 오른쪽 서브트리로, 작으면 왼쪽 서브트리로 이동하며 빈 자리를 찾아 노드를 연결합니다.
3. 최솟값 탐색(main): 모든 데이터를 트리에 삽입한 후, 루트에서 출발하여 left 포인터를 따라 가장 왼쪽 노드까지 이동합니다. 이때 이동한 깊이(depth)도 함께 계산하여 출력합니다.
실행 결과에서 볼 수 있듯이, 배열 {86, 63, 95, 6, 7, 67, 52, 26, 45, 98}의 최솟값은 6이며, 이 값은 루트에서 깊이 2에 해당하는 노드에서 발견됩니다. 이진 검색 트리에서는 루트보다 작은 값이 항상 왼쪽 서브트리에 저장되므로, 왼쪽으로만 이동하면 최솟값에 도달할 수 있습니다.
참고로 실무 코드에서는 new로 할당한 메모리를 사용이 끝난 후 delete로 해제하는 것이 좋으며, 스마트 포인터(std::unique_ptr 등)를 활용하면 메모리 누수를 더욱 안전하게 방지할 수 있습니다.