이 글에서는 이진 탐색 트리(Binary Search Tree, BST)에 특정 값이 존재하는지 확인하기 위해 이진 탐색을 C++로 구현하는 방법을 소개합니다. 이진 탐색의 최악의 경우 시간 복잡도는 O(n)이지만, 평균적인 경우에는 O(log n)으로 매우 효율적으로 동작합니다.
동작 원리
프로그램의 전체 흐름은 다음과 같습니다.
- 정렬되지 않은 데이터 배열의 값을 하나씩 트리에 삽입하여 이진 탐색 트리를 구성합니다.
- BST에서 찾고자 하는 값을 사용자로부터 입력받습니다.
- 루트 노드에서 시작해 입력값과 노드의 값을 비교하며 왼쪽 또는 오른쪽 자식으로 이동합니다.
- 값을 찾으면 해당 노드가 위치한 트리의 깊이를 출력하고, 찾지 못하면 '항목 없음' 메시지를 출력합니다.
알고리즘
시작
정렬되지 않은 데이터 배열의 값을 하나씩 삽입하여 이진 탐색 트리를 구성한다.
BST에서 검색할 데이터를 입력받는다.
루트 노드부터 시작하여 입력 데이터와 노드의 데이터 값을 비교한다.
만약 data < temp->d이면, temp 포인터를 왼쪽 자식으로 이동한다.
만약 data > temp->d이면, temp 포인터를 오른쪽 자식으로 이동한다.
만약 data == temp->d이면, 해당 노드가 발견된 트리의 깊이를 출력하고 main으로 돌아간다.
그렇지 않으면 항목을 찾을 수 없다는 메시지를 출력한다.
끝예제 코드
#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 = root;
if(root == NULL)
root = temp;
else {
while(t != NULL) {
if(t->d < d) {
if(t->right == 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;
}
// 값을 검색하는 함수
void Search(node *root, int d) {
int depth = 0;
node *temp = root;
while(temp != NULL) {
depth++;
if(temp->d == d) {
cout<<"\nitem found at depth: "<<depth;
return;
} else if(temp->d > d)
temp = temp->left;
else
temp = temp->right;
}
cout<<"\n item not found";
return;
}
int main() {
char ch;
int n, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};
node *root = NULL;
for (i = 0; i < 10; i++)
root = InsertIntoTree(root, a[i]);
up:
cout<<"\nEnter the Element to be searched: ";
cin>>n;
Search(root, n);
cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}참고: 원본 코드에 있던 변수 오타(c → ch)와 불필요한 메모리 할당 등 일부 오류를 수정하여 정상적으로 컴파일 및 실행되도록 정리했습니다.
실행 결과
Enter the Element to be searched: 26 item found at depth: 7 Do you want to search more...enter choice(y/n)? y Enter the Element to be searched: 1 item not found Do you want to search more...enter choice(y/n)? n
시간 복잡도
트리가 균형 잡혀 있는 경우 한 번의 비교마다 탐색 범위가 절반으로 줄어들어 평균 시간 복잡도는 O(log n)입니다. 반면 트리가 한쪽으로 치우친 편향 트리 형태가 되면 모든 노드를 순회해야 하므로 최악의 경우 시간 복잡도는 O(n)이 됩니다. 따라서 실제 서비스에서는 균형 이진 탐색 트리(AVL 트리, 레드-블랙 트리 등)를 활용하면 안정적인 성능을 기대할 수 있습니다.