Chapter11 탐색(Search) 1

2018/02/23 - [프로그래밍/자료구조] - Chapter10 정렬(Sorting)

11-1 탐색의 이해와 보간 탐색

단순히 탐색의 방법만을 열거하지 않는다.

탐색의 이해
"효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다. 그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'을 우선 고민해야 한다.'

보간 탐색(interpolation Search)

- 정렬되지 않은 대상을 기반으로 하는 탐색      순차 탐색

- 정렬된 대상을 기반으로 하는 탐색                이진 탐색

"이진 탐색처럼 그냥 중앙에서 탐색을 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작하자!"

탐색 키(Search Key)와 탐색 데이터(Search Data)

보간 탐색의 구현

이진 탐색의 경우 다음 문장을 통해서 탐색의 위치를 계산한다.

mid = (first+last) / 2;

이진 탐색과 보간 탐색의 유일한 차이점은 탐색의 대상을 선택하는 방법에 있어 다음과 같이 바꾸면 보간 탐색이다.

mid = ((double)(target-ar[first]) / (ar[last]-ar[first]) * (last-first)) + first;

때문에 식을 바꾼 시점에서 변수의 이름 mid는 그 이름을 달리해야 한다 (더 이상 mid가 중간을 가리키지 않기 때문에). 이 문장을 제외하고는 이진 탐색에서 바뀌는 부분이 없다.

InterpolSearch.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
int ISearch(int ar[], int first, int last, int target) {
	int mid;

//	if (first > last) {
	if (ar[first] > target || ar[last] < target) {
		return -1;		// -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, 10);
	if (idx == -1) {
		printf("탐색 실패 \n");
	} else {
		printf("타겟 저장 인덱스: %d \n", idx);
	}
	// 배열에 저장되어 있지 않은 2를 찾기 위해서 ISearch 함수를 호출한다.
	idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 2);
	if (idx == -1) {
		printf("탐색 실패 \n");
	} else {
		printf("타겟 저장 인덱스: %d \n", idx);
	}

	return 0;
}

11-2 이진 탐색 트리

'탐색에 효율적인 자료구조'

이진 탐색 트리의 이해
이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있다.

"이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다."

'이진 트리'에 '데이터의 저장 규칙'을 더해놓은 것이 '이진 탐색 트리'이다.

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

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

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

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

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

이진 탐색 트리는 '작으면 왼쪽으로, 크면 오른쪽으로'라는 원칙을 기준으로 데이터를 삽입한다.

이진 탐색 트리의 헤더파일

이진 탐색 트리도 이진 트리이니, 이전에 구현한 이진 트리를 활용하여 구현한다.

#ifndef DATASTRUCTURES_SEARCH_BINARYSEARCHTREE_H_
#define DATASTRUCTURES_SEARCH_BINARYSEARCHTREE_H_

/*---- INCLUDES      --------------------------------------------------------*/
#include "../tree/BinaryTree2.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
typedef BTData BSTData;

// BST의 생성 및 초기화
void BSTMakeAndInit(BTreeNode **pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode *bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode **pRoot, BSTData data);

// BST를 대상으로 데이터 탐색
BTreeNode *BSTSearch(BTreeNode *bst, BSTData target);

#endif /* DATASTRUCTURES_SEARCH_BINARYSEARCHTREE_H_ */

이진 탐색 트리의 구현: 삽입과 탐색

"비교대상이 없을 때까지 내려간다. 그리고 비교대상이 없는 그 위치가 새 데이터가 저장될 위치이다."

이진 탐색 트리의 삭제 구현: 삭제에 대한 이론적 설명과 구현 일부

"이진 탐색 트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 한다."

- 상황 1: 삭제할 노드가 단말 노드인 경우

- 상황 2: 삭제할 노드가 하나의 자식 노드를(하나의 서브 트리를) 갖는 경우

- 상황 3: 삭제할 노드가 두 개의 자식 노드를(두 개의 서브 트리를) 갖는 경우
'상황 1'에서는 삭제 대상인 단말 노드를 삭제하는 것으로 삭제의 과정이 완료된다.

'상황 2'에서는 부모 노드와 자식 노드를 연결하는 것이 관건이다.

'상황 3'에서는 삭제 대상을 '왼쪽 서브 트리에서 가장 큰 값을 저장한 노드'나 '오른쪽 서브 트리에서 가장 작은 값을 저장한 노드'로 대체하면 된다.

"삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾아서 이것으로 삭제할 노드를 대체한다."

 - 단계1: 삭제할 노드를 대체할 노드를 찾는다.

 - 단계2: 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.

 - 단계3: 대체할 노드의 부모 노드와 자식 노드를 연결한다.