이원 탐색 트리(binary search tree)
이진 트리로서 공백일 수 있다. 만약 공백이 아니라면 다음 성질을 만족한다.
1) 모둔 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.
2) 왼쪽 서브트리에 있는 키들은(만약 있다면) 그 루트의 키보다 작다.
3) 오른쪽 서브트리에 있는 키들을(만약 있다면) 그 루트의 키보다 크다.
4) 왼쪽과 오른쪽 서브트리도 모두 이원 탐색 트리이다.
3) 오른쪽 서브트리에 있는 키들을(만약 있다면) 그 루트의 키보다 크다.
4) 왼쪽과 오른쪽 서브트리도 모두 이원 탐색 트리이다.
첫 번째 트리가 이진 탐색 트리가 아닌 이유는 10이 15보다 작음 에도 오른쪽 자식에 위치해 있기 때문이다.
이진 탐색 트리는 정렬된 트리이다.
이원 탐색 트리의 탐색
키 값이 k인 원소를 탐색한다고 가정하자.
탐색은 루트에서부터 시작하는데 만약 루트가 NULL이면 탐색 트리는 원소를 갖지 않으므로 탐색은 실패로 끝난다.
그렇지 않으면 k 값을 루트의 키 값과 비교하여 만일 key가 루트의 키 값과 같다면 탐색은 성공적으로 종료된다.
이원 탐색 트리의 순환적 탐색
element *search(treePointer tree, int key)
{/*key 값이 k인 노드에 대한 포인터를 반환
그런 노드가 없는 경우 NULL을 반환*/
if (!root) return NULL;
if (k == root->data.key) return &(root->data);
if (k < root->data.key)
return search(root->leftChild, k); // k값을 찾아 키값이 루트보다 작으면 왼쪽
return search(root->rightChild, k); // 그렇지 않으면 오른쪽
}순환 탐색 함수는 동일한 기능의 반복 함수로 쉽게 변환할 수 있다.
이원 탐색 트리의 반복적 탐색
element *iterSearch(treePointer tree, int k)
{/* key 값이 k인 노드에 대한 포인터를 반환
그런 노드가 없는 경우 NULL을 반환*/
while (tree) {
if (k == tree->data.key) return &(tree->data);
if (k < tree->data.key)
tree = tree->leftChild;
else
tree = tree->rightChild;
}
}search vs iterSearch --> search는 추가적인 스택 공간을 필요로 한다.
이원 탐색 트리에서의 삽입
1.) 기존의 원소들이 가지고 있는 키 값과 다른지를 확인하기 위한 탐색을 수행
2.) 탐색에 실패하면 탐색이 종료된 그 지점에 쌍을 삽입
2.) 탐색에 실패하면 탐색이 종료된 그 지점에 쌍을 삽입
3.) 기존 포인터 변경
이원 탐색 트리에 사전 쌍의 삽입
void insert(treePointer *node, int k, iType theItem)
{/*트리 내 노드가 k를 가리키고 있으면 아무 일도 하지 않음
그렇지 않은 경우는 data = (k,theItem)인 새 노드를 첨가*/
treePointer ptr, temp = modifiedSearch(*node, k);
if (temp || !(*node)) {
/*k 가 존재 하지 않을 떄*/
MALLOC(ptr, sizeof(*ptr));
ptr->data.key = k;
ptr->data.item = theItem;
ptr->leftChild = ptr->rightChild = NULL;
if (*node) //임시 노드의 자식으로 삽입
if (k < temp->data.key)
temp->leftChild = ptr;
else
temp->rightChild = ptr;
else *node = ptr;
}
}
이원 탐색 트리에서의 삭제
1.) 제거할 원소를 제거
2.) 제거한 루트의 자식을 비교
3.) 작은 것 값이 root 로 재 포인터
3.) 작은 것 값이 root 로 재 포인터
실습 예제
다음을 만족하는 Binary Search Tree 프로그램을 구현하라
1) 입력 데이터는 정수이며 파일(input1.txt)로부터 입력받는다.
2) 숫자를 차례대로 입력받아 Binary Search Tree을 구성한다.
3) 최종 구성된 Binary Search Tree를 Pre/In/Postorder traversal 결과를 각각 출력한 다.
4) 파일(input2.txt)로부터 검색할 정수들을 입력받아 검색 결과를 출력한다. 해당 정수를 Binary Search Tree에서 찾았으면 1, 못찾았으면 0을 각각 출력한다.
입력 값
input1.txt
30 5 2 40 80 35
input2.txt
1 2 40 90
코드
/*
Description : 이진 탐색 순회의 생성 그리고 탐색 (insert로 트리 구성후 search로 탐색)
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENTS 24
int Temp[MAX_ELEMENTS];
int cnt = 0;
typedef struct element{
int key;
} element;
typedef struct node *treePointer;
typedef struct node {
element data;
treePointer leftchild, rightchild;
};
treePointer root;
void insert(treePointer *, int);
treePointer modifiedSearch(treePointer p, int x);
element* search(treePointer tree, int);
void open();
void inorder(treePointer tree);
void postorder(treePointer tree);
void preorder(treePointer tree);
int main()
{
element* status;
open();
printf("Preorder : ");
preorder(root);
printf("\n");
printf("Inorder : ");
inorder(root);
printf("\n");
printf("Postorder : ");
postorder(root);
printf("\n");
printf("Search : ");
for (int i = 0; i < cnt; i++)
{
status = search(root, Temp[i]);
if (status == NULL) printf("0 "); //NULL값이면 찾는 값이 없으므로 '0'
else printf("1 "); //포인터값이 반환되면 '1'
}
printf("\n");
return 0;
}
void open()
{
int temp;
FILE *fp1 = fopen("input1.txt", "r");
if (fp1 != NULL)
{
while ((fscanf(fp1, "%d", &temp) != EOF)) {
insert(&root, temp);
}
}
FILE *fp2 = fopen("input2.txt", "r");
if (fp2 != NULL)
{
while ((fscanf(fp2, "%d", &Temp[cnt])) != EOF)
cnt++;
}
}
void insert(treePointer *node, int k)
{
treePointer ptr, temp = modifiedSearch(*node, k);
if (temp || !(*node)) {
ptr = (treePointer)malloc(sizeof(*ptr));
ptr->data.key = k;
ptr->leftchild = NULL; ptr->rightchild = NULL;
if (*node)
if (k < temp->data.key) temp->leftchild = ptr;
// 여기서 temp는 부모이므로 ptr이 작은값으면 왼쪽으로
else temp->rightchild = ptr; //ptr 큰 값이면 오른쪽으로
else *node = ptr;
}
}
treePointer modifiedSearch(treePointer root, int k) //삽입이 가능한지 탐색하여 가능여부를 반환
{
treePointer temp = root;
while (root)
{
temp = root;
if (k < root->data.key) //삽입값이 작으면
root = root->leftchild; //왼쪽으로 가서 다시 검색
else if (k > root->data.key) //삽입값이 크면
root = root->rightchild; // 오른쪽으로 가서 다시 검색
else
return NULL;
}
return temp; // parent 위치 반환
}
void inorder(treePointer tree)
{
if (tree)
{
inorder(tree->leftchild);
printf("%d ", tree->data.key);
inorder(tree->rightchild);
}
}
void preorder(treePointer tree)
{
if (tree) {
printf("%d ", tree->data.key);
preorder(tree->leftchild);
preorder(tree->rightchild);
}
}
void postorder(treePointer tree)
{
if (tree) {
postorder(tree->leftchild);
postorder(tree->rightchild);
printf("%d ", tree->data.key);
}
}
element* search(treePointer tree, int k)
{
if (!tree) return NULL; //값이 없으면 NULL값 반환
if (k == tree->data.key)return &(tree->data); //값이 있으면 데이타 포인터 반환
if (k < tree->data.key) // 순회
return search(tree->leftchild, k); //root부터 찾는 값이 작으면 왼쪽 자식으로 이동
return search(tree->rightchild, k); //크면 오른쪽으로 이동
}출력 값
트리 관련 알고리즘