탐색 알고리즘

바이너리 서치

정렬된 데이터 집합에서 사용할 수 있는 ‘고속’ 탐색 알고리즘

데이터 집합이 배열인 경우에만 사용할 수 있다.

 

1. 데이터 집합의 중앙에 있는 요소 선택

2. 요소의 값과 찾고자 하는 목표 값을 비교

3. 찾고자 하는 값이 작다면 요소의 값 왼쪽 데이터 집합에서 1~2 실행, 크다면 오른쪽 데이터 집합에서 1~2 실행

4. 찾고자 하는 값을 찾을 때까지 1~3번 과정 반복

 

int BinarySearch(int  DataSet[], int Size, int target)

{

int mid = 0;

int left = 0;

int right = Size - 1;

while (left <= right)

{

mid = (left + right) / 2;

if (target == DataSet[mid])

return DataSet[mid]; // OR return mid;

else if (DataSet[mid] < target)

left = mid + 1;

else 

right = mid - 1;

}

return NULL; //찾는 값이 없을 경우

}

int main()

{

int DataSet[] = { 1,2,3,4,5,6,7,8,9,10 };

int Length = sizeof DataSet / sizeof DataSet[0];

int i = 0;

int target = 10;

printf("target %d는 탐색결과 : DataSet[%d]\n",target, BinarySearch(DataSet, Length, target));

for (int i = 0; i < Length; i++)

printf("%d ", DataSet[i]);

printf("\n");

return 0;

}

바이너리 서치 트리
: 다른 이진 트리와 다르게 '왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다.' 는 규칙을 따른다.

헤더파일

#ifndef BINARY_SEARCH_TREE_H

#define BINARY_SEARCH_TREE_H

/*

BINARY_SEARCH_TREE_H이라는 상수가 선언되어 있는지 확인한다.

선언되어 있지 않다면 BINARY_SEARCH_TREE_H이라는 상수를 정의한다.

만약게 BINARY_SEARCH_TREE_H이라는상수가 선언이 되어있다면 해당 참조는 무시하게 된다.

=> 해더파일의 중복 선언 문제를 예방하기 위해서 쓰는 전처리문이다.

*/

#include <stdio.h>

#include <stdlib.h>

typedef int ElementType;

typedef struct tagBSTNode

{

struct tagBSTNode * Left;

struct tagBSTNode * Right;

ElementType Data;

}BSTNode;

BSTNode* BST_CreateNode(ElementType NewData);

void BST_DestroyNode(BSTNode* Node);

void BST_DestroyTree(BSTNode* Tree);

BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target);

BSTNode* BST_SearchMinNode(BSTNode* Tree);

void BST_InsertNode(BSTNode* Tree, BSTNode* Child);

BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target);

void BST_InorderPrintTree(BSTNode* Node);

#endif

소스 파일

#include "BinarySearchTree.h"

//노드 생성

BSTNode* BST_CreateNode(ElementType NewData)

{

BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));

NewNode->Left = NULL;

NewNode->Right = NULL;

NewNode->Data = NewData;

return NewNode;

}

//노드 파괴

void BST_DestroyNode(BSTNode* Node)

{

free(Node);

}

//트리 삭제

void BST_DestroyTree(BSTNode* Tree)

{

if (Tree->Right != NULL)

BST_DestroyTree(Tree->Right);

if (Tree->Left != NULL)

BST_DestroyTree(Tree->Left);

Tree->Left = NULL;

Tree->Right = NULL;

BST_DestroyNode(Tree);

}

BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target)

{

if (Tree == NULL)

return NULL;

if (Tree->Data == Target)

return Tree;

else if (Tree->Data > Target)

return BST_SearchNode(Tree->Left, Target);

else

return BST_SearchNode(Tree->Right, Target);

}

BSTNode* BST_SearchMinNode(BSTNode* Tree)

{

//바이너리 서치 트리에서는 제일 왼쪽 아래에있고 왼쪽 자식이 없는 노드가 최소값

if (Tree == NULL)

return NULL;

if (Tree->Left == NULL)

return Tree;

else

return BST_SearchMinNode(Tree->Left);

}

//중복되는 데이터가 들어오는 경우는 처리가 않되어있다.

void BST_InsertNode(BSTNode* Tree, BSTNode* Child)

{

if (Tree->Data > Child->Data){

if (Tree->Left == NULL)

Tree->Left = Child;

else

BST_InsertNode(Tree->Left, Child);

}

else if (Tree->Data < Child->Data){

if (Tree->Right == NULL)

Tree->Right = Child;

else

BST_InsertNode(Tree->Right, Child);

}

}

//삭제할 노드의 아래에 있는 노드중에서 최소값을 가지는 노드를 삭제할 노드의 위치에 위치시킨다.

BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target)

{

BSTNode* Removed = NULL;

//삭제할 노드가 없을 경우

if (Tree == NULL)

return NULL;

if (Tree->Data == Target){

Removed = Tree;

//잎 노드일 경우 바로 삭제

if (Tree->Left == NULL && Tree->Right == NULL){

if (Parent->Left == Tree)

Parent->Left = NULL;

else

Parent->Right = NULL;

}

//자식이 양쪽 다 있는 경우

else if (Tree->Left != NULL && Tree->Right != NULL){

BSTNode* MinNode = BST_SearchMinNode(Tree->Right);

MinNode = BST_RemoveNode(Tree, NULL, MinNode->Data);

Tree->Data = MinNode->Data;

}

//자식이 하나만 있는 경우

else {

BSTNode* Temp = NULL;

if (Tree->Left != NULL)

Temp = Tree->Left;

else

Temp = Tree->Right;

if (Parent->Left == Tree)

Parent->Left = Temp;

else

Parent->Right = Temp;

}

}

else if (Tree->Data > Target){

Removed = BST_RemoveNode(Tree->Left, Tree, Target);

}

else{

Removed = BST_RemoveNode(Tree->Right, Tree, Target);

}

return Removed;

}

void BST_InorderPrintTree(BSTNode* Node)

{

if (Node == NULL)

return;

BST_InorderPrintTree(Node->Left);

printf("%d ", Node->Data);

BST_InorderPrintTree(Node->Right);

}

int main()

{

BSTNode* Tree = BST_CreateNode(123);

BSTNode* Node = NULL;

BST_InsertNode(Tree, BST_CreateNode(22));

BST_InsertNode(Tree, BST_CreateNode(9918));

BST_InsertNode(Tree, BST_CreateNode(424));

BST_InsertNode(Tree, BST_CreateNode(17));

BST_InsertNode(Tree, BST_CreateNode(3));

BST_InsertNode(Tree, BST_CreateNode(98));

BST_InsertNode(Tree, BST_CreateNode(34));

BST_InsertNode(Tree, BST_CreateNode(760));

BST_InsertNode(Tree, BST_CreateNode(317));

BST_InsertNode(Tree, BST_CreateNode(1));

//트리 출력

BST_InorderPrintTree(Tree);

printf("\n");

//특정 노드 삭제

printf("Removing 98...\n");

Node = BST_RemoveNode(Tree, NULL, 98);

BST_DestroyNode(Node);

BST_InorderPrintTree(Tree);

printf("\n");

//새노드 삽입

printf("Inserting 111...\n");

BST_InsertNode(Tree, BST_CreateNode(111));

BST_InorderPrintTree(Tree);

printf("\n");

//트리 소멸시키기

BST_DestroyNode(Tree);

return 0;

}