[열혈자료구조] 11강. 탐색(Search) 1 : 보간탐색, 이진탐색트리

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를 기반으로 하는 탐색을 다룬다. 즉, 데이터를 어떻게 저장하는지가 탐색의 효율에 큰 영향을 미칠 수 있다.

 

단순 탐색과 이진 탐색은 이전 포스팅을 참고!! https://cascade.tistory.com/62

탐색 알고리즘 (백준 1920번)

 

보간 탐색(Interpolation Search)

보간 탐색은 이진 탐색처럼 중앙에서 탐색을 시작하는 것이 아니라, 탐색대상이 앞쪽에 있다면 앞쪽부터 탐색을 시작하는 방법이다. 이는 사전을 찾을 때 Apple이라는 단어를 찾으려면 A로 시작하는 곳을 먼저 찾는 것과 같은 원리이다.

 

이때, 중요한 가정은 데이터가 정렬되어 있으며, 데이터의 인덱스값은 데이터의 값과 어느 정도 비례할 것이라는 점이다. 

따라서, 어떤 arr의 가장 작은 인덱스를 low, 가장 큰 인덱스를 high라고 할 때, 찾고자 하는 데이터의 인덱스 값 s는 위와 같이 비율 관계를 이용하여 계한할 수 있다. 이를 코드로 옮겨 보다.

 

먼저, 탐색 키(Search Key)와 탐색 데이터(Search Data)를 구조체로 아래와 같이 정의한다.

typedef int Key;
typedef double Data;

typedef struct item
{
	Key searchKey;
	Data searchData;
}

 

이때 탐색 키는 중복되지 않는 고유한 값을 가지며 NULL이 아니다. 보간 탐색을 구현하는 방법은, 이전에 구현했던 이진 탐색에서 mid = (first + last)/2로 중점을 잡아 탐색하는 것을 위의 비례식으로 바꿔주기만 하면 된다.

#include <stdio.h>

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

	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);
}

 

이진 탐색과 마찬가지로 재귀적으로 구현된 것을 확인할 수 있다. 탐색 대상이 arr에 없으면, 여러 번 재귀 호출을 했을 때 탐색 대상의 값은 탐색 범위를 넘어가게 되는데, 이에 따라 위와 같이 탈출 조건을 구성할 수 있다.

 

---

이진 탐색 트리

이진 탐색 트리는 이진 트리의 일종이다. 이진 트리에 관한 내용은 포스팅 https://cascade.tistory.com/81에 정리되어 있다.

[열혈자료구조] 8강. 트리(tree)

이진 트리가 탐색에 효율적인 이유는, 데이터 수 N이 매우 커도 트리의 층 수는 log_2 N 근처에 지나지 않기 때문이다. 따라서, 원하는 데이터가 이진 트리에 저장되어 있다면, 루트 노드에서 이 데이터에 이르는 경로만 찾으면 된다. 탐색은 이진 트리의 키 값을 기준으로 할 것인데, 키는 아래 조건을 만족한다.

• 키 값은 유일하다.
• 루트 노드의 키 값은 왼쪽 서브 트리에 속한 어떤 키보다도 크고, 오른쪽 서브 트리에 속한 어떤 키보다도 작다.
• 왼쪽, 오른족 서브 트리도 이진 탐색 트리이다.

이진 탐색 트리에 새로운 숫자를 저장한다고 하면, 루트 노드에서부터 시작하여 새로운 수가 더 크다면 오른쪽으로, 작으면 왼쪽으로 보내는 과정을 반복하면 된다. 또한 탐색한다고 하면 루트 노드에서부터 시작하여 찾으려는 수와 노드에 저장된 데이터값을 비교해 가며 "길찾기"를 하면 된다.

 

8강에서 구현했던 트리(BinaryTree2.h)를 그대로 사용하여 이진 탐색 트리를 구현하자. BinaryTree2.h에는 아래와 같은 함수가 있었다.

(1) BTreeNode * MakeBTreeNode(void);
(2) BTData GetData(BTreeNode * bt);
(3) void SetData(BTreeNode * bt, BTData data);
(4) BTreeNode * GetLeftSubTree(BTreeNode * bt);
(5) BTreeNode * GetRightSubTree(BTreeNode * bt);
(6) void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
(7) void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

 

이 함수들을 이용하여, 아래 BinarySearchTree.h에 있는 함수들을 구현하자.

 

초기화 및 루트 노드 데이터 반환

 

아래와 같이 간단히 작성할 수 있다. 이때 pRoot가 이중 포인터임에 주의하자. 즉, pRoot는 루트노드를 가리키는 포인터의 주소를 가리킨다.

void BSTMakeAndInit(BTreeNode ** pRoot){
    * pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst){
    return GetData(bst);
}

 

데이터 삽입(BSTInsert)

 

먼저, 교재를 보지 않고 BinarySearchTree.h 파일을 보고 아래와 같이 구현해 보았다. 루트 노드부터 시작하여, 넣고자 하는 데이터의 위치를 크기비교를 통해 탐색하고, 탐색이 종료되면 그 노드의 자식 노드로 추가하는 식이다.

#include <stdio.h>
#include "BinarySearchTree.h"
#include "BinaryTree2.h"

void BSTMakeAndInit(BTreeNode ** pRoot){
    * pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode * bst){
    return GetData(bst);
}

void BSTInsert(BTreeNode ** pRoot, BSTData data){
    BTreeNode * currentNode = * pRoot;
    BTreeNode * newNode = NULL;
    while(currentNode != NULL){
        if(currentNode->data > data){
            currentNode = GetLeftSubTree(currentNode);
        }
        else{
            currentNode = GetRightSubTree(currentNode);
        }
    }
    newNode = MakeBTreeNode();
    SetData(newNode, data);
    if(data<currentNode->data){
        MakeLeftSubTree(currentNode, newNode);
    }
    else{
        MakeRightSubTree(currentNode, newNode);
    }
}

 

이러한 구현에서 문제점은, 첫째로 중복된 데이터가 들어왔을 때 오류를 잡을 수 없다. 둘째로, currentNode가 NULL이 된 상태로 while 문을 탈출하기 때문에, NULL이 되기 이전 노드를 가리키는 포인터가 있어야 그 아래 새로운 노드를 추가할 수 있다. 교재에서는 아래와 같이 구현하였다.

 

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	while(cNode != NULL)
	{
		if(data == GetData(cNode))
			return;

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}
	

	nNode = MakeBTreeNode();
	SetData(nNode, data);


	if(pNode != NULL)
	{
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else
	{
		*pRoot = nNode;
	}
}

 

즉 while문의 조건으로는 cNode를 이용하지만, 그 이전에 가리켰던 노드를 pNode에 저장하여 새로운 노드를 추가할 때는 pNode를 사용하는 것이다. 또한, 중복되는 데이터가 있을 경우 탈출 조건도 넣어 주었으며, 새 노드가 루트 노드인 경우도 처리해 주었다.

 

데이터 검색(BSTSearch)

 

마찬가지로 교재를 보지 않고 BSTSearch 함수를 아래와 같이 구현해 보았다.

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target){
    BTreeNode * searchNode = bst;
    while(GetData(searchNode) != target){
        if(GetData(searchNode)>target) searchNode = GetLeftSubTree(searchNode);
        else searchNode = GetRightSubTree(searchNode);
    }
    return searchNode;
}

 

이러한 구현의 문제점은, 트리에 찾고자 하는 target 데이터가 없을 경우 무한루프를 돌 수 있다는 점이다. 따라서, 교재에서는 while 문의 조건을 현재 노드가 NULL을 가리키는 것으로 했고, target을 찾았을 때의 탈출조건을 while문 내부에 return으로 작성하였다.

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
	BTreeNode * cNode = bst;    // current node
	BSTData cd;    // current data

	while(cNode != NULL)
	{
		cd = GetData(cNode);

		if(target == cd)
			return cNode;
		else if(target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	return NULL;
}

 

데이터 삭제의 구현

이진 탐색 트리에서 데이터의 삭제는 데이터의 추가와 탐색에 비해 훨씬 어렵다. 예를 들어 아래와 같은 이진트리에서 8을 어떻게 삭제할까?

 

이진 탐색 트리에서 삭제가 까다로운 이유는 삭제한 후에도 이진 탐색 트리의 형태가 유지되어야 하기 때문이다.

 

(1) 삭제하려는 노드가 Terminal Node인 경우: 그 노드만 삭제하면 되므로 아주 간단하다.

 

(2) 삭제하려는 노드가 서브 트리를 하나만 갖는 경우: 삭제하려는 노드의 부모 노드와 삭제하려는 노드의 자식 노드를 연결하기만 하면 된다.

 

(3) 삭제하려는 노드가 서브 트리를 두 개 갖는 경우: 까다롭다.

 

위 세 가지 케이스 중 3번이 가장 까다롭기 때문에 이를 중점적으로 생각할 것이다. 삭제하려는 노드의 자리에 대신하여 들어갈 수 있는 후보는 2가지가 있다. 첫째는 왼쪽 서브 트리에서 가장 큰 값, 둘째는 오른쪽 서브 트리에서 가장 작은 값이다. 이렇게 대체하면 이진 트리 구조가 유지된다는 것을 수학적으로 증명할 수 있는데, 이 포스팅에서는 패스하려고 한다.

 

중요한 것은 왼쪽 서브 트리에서 가장 큰 값 혹은 오른쪽 서브 트리에서 가장 작은 값을 어떻게 찾는지이다. 가장 큰 값은 NULL이 나올 때까지 최대한 오른쪽으로 이동하면 되고, 가장 작은 값은 NULL이 나올 때까지 최대한 왼쪽으로 이동하면 된다. 둘 중 어느 것을 사용해도 상관없기 때문에 교재에서는 오른쪽에서 가장 작은 값을 찾는 방법을 택했다.

이는 세 단계로 구성된다.

1. 오른쪽 서브 트리에서 가장 작은 값을 갖는 노드를 찾는다.
2. 대체할 노드의 값을 삭제할 노드에 대입한다.
3. 대체할 노드의 부모 노드와 자식 노드를 연결한다.

이를 구현하기 위해, 이진 트리에 네 가지 함수를 추가로 정의하여 확장할 것이다.

(1) BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
(2) BTreeNode * RemoveRightSubTree(BTreeNode * bt)
(3) void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub)
(4) void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)

(1)~(2)는 왼쪽/오른쪽 자식 노드를 트리에서 제거하고, 제가한 노드의 주소를 반환하는 함수, (3)~(4)는 main의 왼쪽/오른쪽 자식 노드를 메모리 소멸 없이 변경하는 함수이다.

BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->left;
		bt->left = NULL;
	}
	return delNode;
}

BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->right;
		bt->right = NULL;
	}
	return delNode;
}

void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub) 
{
	main->left = sub;
}
 
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	main->right = sub;
}

 

이를 이용하여 삽입, 탐색, 삭제 기능까지 완전히 갖춘 이진 탐색 트리를 구현할 수 있다. 이 중 삭제에 관한 함수인 BSTRemove만 살펴보면 아래와 같다.

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{


	BTreeNode * pVRoot = MakeBTreeNode();  

	BTreeNode * pNode = pVRoot;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * dNode;    // delete node


	ChangeRightSubTree(pVRoot, *pRoot);
	

	while(cNode != NULL && GetData(cNode) != target)
	{
		pNode = cNode;

		if(target < GetData(cNode))
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	if(cNode == NULL) 
		return NULL;

	dNode = cNode; 


	if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
	{
		if(GetLeftSubTree(pNode) == dNode)
			RemoveLeftSubTree(pNode);
		else
			RemoveRightSubTree(pNode);
	}


	else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
	{
		BTreeNode * dcNode;

		if(GetLeftSubTree(dNode) != NULL)
			dcNode = GetLeftSubTree(dNode);
		else
			dcNode = GetRightSubTree(dNode);

		if(GetLeftSubTree(pNode) == dNode)
			ChangeLeftSubTree(pNode, dcNode);
		else
			ChangeRightSubTree(pNode, dcNode);
	}


	else
	{
		BTreeNode * mNode = GetRightSubTree(dNode);    // mininum node
		BTreeNode * mpNode = dNode; 
		int delData;


		while(GetLeftSubTree(mNode) != NULL)
		{
			mpNode = mNode;
			mNode = GetLeftSubTree(mNode);
		}
		
	
		delData = GetData(dNode);
		SetData(dNode, GetData(mNode));


		if(GetLeftSubTree(mpNode) == mNode)
			ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
		else
			ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

		dNode = mNode;
		SetData(dNode, delData); 
	}


	if(GetRightSubTree(pVRoot) != *pRoot)
		*pRoot = GetRightSubTree(pVRoot);

	free(pVRoot);
	return dNode;
}

 

먼저, 삭제하는 노드의 케이스를 서브트리의 개수에 따라 세 가지 케이스로 if-else로 분류하였다. 이 중 가장 중요한 경우는 서브트리가 두 개 있는 경우인데, 위에서 설명하였듯 세 부분으로 나누어 수행하면 된다.