이진탐색트리(BST, Binary Search Tree)는 Data를 빠르게 검색할 수 있도록, 저장을 해두어 검색 시 최대 O(logⁿ)의 빠른 속도로 값을 검색하게 해주는 자료구조이다.
※이진탐색(Binary Search)는 알고리즘이며, 이진탐색(Binary Search Tree)는 자료구조이다. 이 둘을 혼동하지 않도록 하자!
BST 자료구조는 특정규칙을 갖는 이진트리 형태로 값을 저장해두며, 크게는 값을 저장하는 "INSERT", "SEARCH", "DELETE" 동작으로 세분화된다.
For문만 사용하면, 자료를 탐색하는데 문제가 없는데 왜 이진트리 형태로 저장할까?
당연히, 이는 데이터 탐색 시간 때문이다.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long vect[10000];
for (int i = 0; i < n; i++) {
cin >> vect[i];
}
int target;
cin >> target;
for (int i = 0; i < n; i++) {
if (vect[i] == target) {
cout << "발견!";
return 0;
}
}
return 0;
}일반적인 1중 For문을 선형탐색(Linear Search)할 경우, 최대 소요시간은 O(n)이다. 위 코드에서 n이 1만개라고 가정해볼 때, target이 가장 뒤에 있는 최악의 경우, 1만개를 모두 탐색해보아야 한다. 그러나, 이진트리를 사용할 경우 최대 13번만 탐색하면 자료를 탐색할 수 있다.
< 자료 저장하기 : insert >
그럼 이진트리를 사용해서 어떻게 값을 저장할 수 있을까?
왼쪽 자식을 저장하는 index는 '부모index2'로, 오른쪽 자식을 저장하는 index는 '부모index2+1'로 설정한다. 이 경우, 곱하기 연산의 편의성을 위해 root의 index는 1번으로 시작한다. BST는 while와 재귀를 사용해서 구현가능하며, 이 글에서는 재귀를 통해 구현하고자 한다.
#include <iostream>
using namespace std;
int bst[100];
void insert(int value, int now) {
if (bst[now] == 0) {
bst[now] = value; //아직 값이 안 들어갔으면, 넣고 함수 종료
return;
}
if (bst[now] >= value) {
insert(value, now * 2); //부모 값이 더 클 경우 왼쪽에 저장 (같음 포함)
}
else if (bst[now] < value) {
insert(value, now * 2 + 1); // 자식 값이 더 클 경우 오른쪽 저장
}
}
int main() {
//3,5,1,2,4,7을 저장하기
insert(3,1);
insert(5,1);
insert(1,1);
insert(2,1);
insert(4,1);
insert(7,1);
return 0;
}위와 같이 저장될 경우, 아래 그림에서 볼 수 있듯이 가장 밑단에 있는 5를 탐색하더라도 탐색회수는 최대 4번이다. 즉, 이는 트리의 높이(=재귀 호출 횟수)만큼이 걸리는 시간이라고도 해석할 수가 있으며, 이 경우 시간 복잡도는 O(logⁿ)이다.
< 자료 탐색하기 : search >
#include <iostream>
using namespace std;
int bst[100];
void insert(int value, int now) {
if (bst[now] == 0) {
bst[now] = value; //아직 값이 안 들어갔으면, 넣고 함수 종료
return;
}
if (bst[now] >= value) {
insert(value, now * 2); //부모 값이 더 클 경우 왼쪽에 저장 (같음 포함)
}
else if (bst[now] < value) {
insert(value, now * 2 + 1); // 자식 값이 더 클 경우 오른쪽 저장
}
}
void search(int value) {
int now = 1;
while (1) {
if (now >= 100 && bst[now] == 0) {
cout << "미발견..."; //index가 초과되었고, 자료가 없음
return;
}
if (bst[now] == value) {
cout << "찾았다!";
return;
}
if (bst[now] > value) {
now = now * 2;
}
else if (bst[now] < value) {
now = now * 2 + 1;
}
}
}
int main() {
//3,5,1,2,4,7을 저장하기
insert(3,1);
insert(5,1);
insert(1,1);
insert(2,1);
insert(4,1);
insert(7,1);
search(4);
return 0;
}search 소스코드는 insert코드와 매우 유사하며, insert 소스코드에서 못 찾았을 때 함수를 종료하는 조건만 추가해주면 완료된다
