이진 탐색 트리(Binary Search Tree)란?
이진 탐색 트리는 모든 노드가 다음 두 가지 성질을 만족하는 정렬된 이진 트리입니다.
- 노드의 오른쪽 서브트리에 있는 키는 항상 부모 노드의 키보다 크다.
- 노드의 왼쪽 서브트리에 있는 키는 부모 노드의 키보다 작거나 같다.
- 각 노드는 최대 두 개의 자식 노드만 가질 수 있다.
이러한 구조 덕분에 탐색·삽입·삭제 연산을 평균적으로 O(log n) 시간 복잡도로 빠르게 처리할 수 있습니다. 이 글에서는 C++를 활용해 사전(Dictionary) 자료구조에서 데이터를 삽입하고, 검색하고, 삭제하는 프로그램을 단계별로 살펴보겠습니다.
핵심 알고리즘
아래 구현은 키 값을 해시 함수(k mod max)로 분류하여 버킷(bucket)에 저장하고, 각 버킷을 연결 리스트로 관리하는 방식으로 동작합니다.
1. 삽입(Insert)
Begin
Declare function insert(int k)
in = int(k mod max)
p[in] = (n_type*) malloc(sizeof(n_type))
p[in]->d = k
if (r[in] == NULL) then
r[in] = p[in]
r[in]->n = NULL
t[in] = p[in]
else
t[in] = r[in]
while (t[in]->n != NULL)
t[in] = t[in]->n
t[in]->n= p[in]
End.
2. 검색(Search)
Begin
Declare function search(int k)
int flag = 0
in= int(k mod max)
t[in] = r[in]
while (t[in] != NULL) do
if (t[in]->d== k) then
Print “Search key is found”.
flag = 1
break
else
t[in] = t[in]->n
if (flag == 0)
Print “search key not found”.
End.
3. 삭제(Delete)
Begin
Declare function delete_element(int k)
in = int(k mod max)
t[in] = r[in]
while (t[in]->d!= k and t[in] != NULL)
p[in] = t[in]
t[in] = t[in]->n
p[in]->n = t[in]->n
Print the deleted element
t[in]->d = -1
t[in] = NULL
free(t[in])
End
C++ 전체 예제 코드
#include<iostream>
#include<stdlib.h>
using namespace std;
# define max 20
typedef struct dictionary {
int d;
struct dictionary *n;
} n_type;
n_type *p[max], *r[max], *t[max];
class Dict {
public:
int in;
Dict();
void insert(int);
void search(int);
void delete_element(int);
};
int main(int argc, char **argv) {
int v, choice, n, num;
char c;
Dict d;
do {
cout << "\n1.Create";
cout << "\n2.Search for a value";
cout<<"\n3.Delete a value";
cout << "\nEnter your choice:";
cin >> choice;
switch (choice) {
case 1:
cout << "\nEnter the number of elements to be inserted:";
cin >> n;
cout << "\nEnter the elements to be inserted:";
for (int i = 0; i < n; i++) {
cin >> num;
d.insert(num);
}
break;
case 2:
cout << "\nEnter the element to be searched:";
cin >> n;
d.search(n);
case 3:
cout << "\nEnter the element to be deleted:";
cin >> n;
d.delete_element(n);
break;
default:
cout << "\nInvalid choice....";
break;
}
cout << "\nEnter y to continue......";
cin >> c;
}
while (c == 'y');
}
Dict::Dict() {
in = -1;
for (int i = 0; i < max; i++) {
r[i] = NULL;
p[i] = NULL;
t[i] = NULL;
}
}
void Dict::insert(int k) {
in = int(k % max);
p[in] = (n_type*) malloc(sizeof(n_type));
p[in]->d = k;
if (r[in] == NULL) {
r[in] = p[in];
r[in]->n = NULL;
t[in] = p[in];
} else {
t[in] = r[in];
while (t[in]->n != NULL)
t[in] = t[in]->n;
t[in]->n= p[in];
}
}
void Dict::search(int k) {
int flag = 0;
in= int(k % max);
t[in] = r[in];
while (t[in] != NULL) {
if (t[in]->d== k) {
cout << "\nSearch key is found!!";
flag = 1;
break;
} else
t[in] = t[in]->n;
}
if (flag == 0)
cout << "\nsearch key not found.......";
}
void Dict::delete_element(int k) {
in = int(k % max);
t[in] = r[in];
while (t[in]->d!= k && t[in] != NULL) {
p[in] = t[in];
t[in] = t[in]->n;
}
p[in]->n = t[in]->n;
cout << "\n" << t[in]->d << " has been deleted.";
t[in]->d = -1;
t[in] = NULL;
free(t[in]);
}
실행 결과
1.Create
2.Search for a value
3.Delete a value
Enter your choice:1
Enter the number of elements to be inserted:3
Enter the elements to be inserted:111 222 3333
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:111
Search key is found!!
Enter the element to be deleted:222
222 has been deleted.
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:222
Invalid choice....
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:222
search key not found.......
Enter the element to be deleted:0
마무리
이 프로그램은 메뉴 기반 반복 루프를 통해 사용자 입력에 따라 데이터 생성(Create), 검색(Search), 삭제(Delete) 세 가지 연산을 선택적으로 수행합니다. 존재하지 않는 메뉴 번호를 입력하면 "Invalid choice" 메시지를 출력하며, 삭제된 키는 다시 검색되지 않는 것을 실행 결과에서 확인할 수 있습니다. 참고로 실습 환경에서는 case 2 다음에 break 문이 누락되어 검색 후 삭제 로직이 이어서 실행될 수 있으므로, 필요에 따라 break 문을 추가하여 의도치 않은 동작을 방지하는 것이 좋습니다.