탐색(Search) 1

탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 왜냐하면 효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안 되고 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야되기 때문이다.

보간탐색

이론적으로 보간 탐색과 이진 탐색의 유일한 차이점은 탐색의 대상을 선정하는 방법이다.

InterpolSearch.c

#include <stdio.h>

int ISearch(int ar[], int first, int last, int target)
{
	int mid;

//	if(first > last)
//		return -1;    // -1의 반환은 탐색의 실패를 의미

	if(ar[first]>target || ar[last]<target)
		return -1;
 
	// 이진 탐색과의 차이점을 반영한 문장
	mid = ((double)(target-ar[first]) / (ar[last]-ar[first]) *
			(last-first)) + first;

	if(ar[mid] == target)
		return mid;    // 탐색된 타겟의 인덱스 값 반환
	else if(target < ar[mid])
		return ISearch(ar, first, mid-1, target);
	else
		return ISearch(ar, mid+1, last, target);
}


int main(void)
{
	int arr[] = {1, 3, 5, 7, 9};
	int idx;
	
	idx = ISearch(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
	if(idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	idx = ISearch(arr, 0, sizeof(arr)/sizeof(int)-1, 2);
	if(idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}


/*
int main(void)
{
	int arr[] = {1, 3, 5, 7, 9};
	int idx;
	
	idx = ISearch(arr, 0, sizeof(arr)/sizeof(int)-1, 2);
	if(idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

*/

이진 탐색 트리

이진 트리에 데이터의 저장 규칙을 더해놓은 것

이진 탐색 트리가 되기 위한 조건

1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.

2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

BinarySearchTree2.c

0.00MB

BinarySearchTree2.h

0.00MB

BinarySearchTreeDelMain.c

0.00MB

BinaryTree3.c

0.00MB

BinaryTree3.h

0.00MB