[자료구조] 11. 탐색 1

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다.

 

1. 탐색의 이해와 보간 탐색

1-1. 탐색의 이해

탐색이란 데이터를 찾는 방법이다.

굳이 따지자면 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다.

효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안된다.

그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다.

이때 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다.

따라서 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여 있다.

 

1-2. 보간 탐색

지금까지 크게 두 가지 탐색 알고리즘을 학습했다.

• 순차 탐색 : 정렬되지 않은 대상을 기반으로 하는 탐색
• 이진 탐색 : 정렬된 대상을 기반으로 하는 탐색

이진 탐색은 중앙에 위치한 데이터를 탐색한 후, 이를 기준으로 탐색 대상을 반씩 줄여나가면서 탐색을 진행하는 알고리즘이다. 찾는 대상이 중앙에 위치하건 맨 앞에 위치하건 그에 상관하지 않고 일관되게 반씩 줄여가면서 탐색을 진행한다. 따라서 찾는 대상의 위치에 따라 탐색의 효율에 차이가 발생한다. 이러한 이진 탐색의 비효율성을 개선시킨 알고리즘이 보간 탐색이다.

 

📌 보간 탐색 (Interpolation Search)

정렬된 배열에서 검색 대상 값의 상대적 위치를 추정하여 탐색 범위를 동적으로 조정하는 탐색 알고리즘

• 이진 탐색은 값에 상관없이 탐색 위치를 결정하지만, 보간 탐색은 그 값이 상대적으로 앞에 위치한다고 판단하면 앞쪽에서 탐색을 진행한다.
• 예를 들어, '김정수'라는 사람의 전화번호를 찾을 때 전화번호부의 인덱스를 보고 'ㄱ'에 해당하는 앞쪽에서 찾는 것과 유사하다.

• low & high : 탐색 대상의 시작과 끝에 해당하는 인덱스 값
•  s  : 찾는 데이터가 저장된 위치의 인덱스 값

보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정하기 때문에, 다음의 비례식을 구성한다.

위 식에서 찾는 값은  s  이므로 다음과 같이 정리해야 한다.

그리고 찾는 데이터의 값 arr[s] 를 x라 하면, 위의 식은 최종적으로 아래와 같이 정리가 된다.

이 식은 단순하지만 나눗셈 연산을 사용하고 오차율을 최소화하기 위해 실수형 나눗셈을 진행하는 단점이 있다.

 

1-3. 보간 탐색의 구현

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

 

✍🏻 이진 탐색의 구현

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target)
{
		int mid;
		if(first > last)
				return -1;
				
		mid = (first + last) / 2;
		
		if(ar[mid] == target)
				return mid;
		else if(target < ar[mid])
				return BSearchRecur(ar, first, mid-1, target);
		else
				return BSearchRecur(ar, mid+1, last, target);
}

int main(void)
{
		...
		return 0;
}

위 예제의 BSearchRecur 함수는 다음 문장을 통해 탐색의 위치를 계산한다.

이진 탐색과 보간 탐색의 유일한 차이점은 탐색의 대상을 선택하는 방법에 있으니, 이를 바꾸면 보간 탐색을 구현할 수 있다.

 

✍🏻 보간 탐색의 구현

#include <stdio.h>

int ISearch(int ar[], int first, int last, int target)
{
		int mid;
		
		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)
{
		...
		
		return 0;
}

 

탐색 대상이 존재하지 않는 경우, target에 저장된 값이 first가 가리키는 값보다 작거나 last가 가리키는 값보다 커지게 되므로 탈출 조건을 위와 같이 설정한다.

 

1-4. 보간 탐색의 특징과 장단점 by GPT

⏱️ 시간 복잡도

• 최선의 경우 : O(log(log(n))) 값이 균등하게 분포된 경우
• 최악의 경우 : O(n) 값이 균등하지 않게 분포된 경우

 

✍🏻 조건

• 보간 탐색은 배열이 정렬되어 있어야 한다.
• 값이 대체로 균등하게 분포되어 있어야 효과적이다.

 

🤔 장점과 단점

• 값이 균등하게 분포된 정렬 데이터에서 매우 빠른 검색이 가능하다.
• 값이 고르지 않게 분포된 경우 성능이 저하될 수 있다.
• 구현이 이진 탐색보다 복잡하다.

 

✍🏻 보간 탐색과 이진 탐색 비교

즉, 보간 탐색은 검색 대상 데이터가 균등 분포된 정렬 배열일 때 효율적이며, 이진 탐색보다 더 나은 성능을 발휘할 수 있다.

 

2. 이진 탐색 트리

2-1. 이진 탐색 트리의 이해

이진 트리에 저장된 데이터의 수가 10억 개 수준이더라도 트리의 높이는 30을 넘지 않는다.

이러한 이진 트리 구조는 탐색에 효율적이라는 사실을 쉽게 알 수 있다.

 

📌 이진 탐색 트리 (BST, Binary Search Tree)

이진 트리에 데이터의 저장 규칙을 더한 트리 기반 자료구조

• 이진 탐색 트리의 노드는 유일하다.
• 모든 노드는 왼쪽 서브 트리의 모든 노드보다 크다.
• 모든 노드는 오른쪽 서브 트리의 모든 노드보다 작다.
• 왼쪽과 오른쪽 서브 트리도 각각 이진 탐색 트리이다.

        8
      /   \
     3    10
    / \     \
   1   6    14
      / \   /
     4   7 13

 

2-2. 이진 탐색 트리의 삽입

위 그림을 통해 비교 대상보다 값이 작으면 왼쪽 자식 노드로, 값이 크면 오른쪽 자식 노드로 이동한다는 사실을 알 수 있다.

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

 

2-3. 이진 탐색 트리의 삭제

위 이진 탐색 트리에서 8이 담긴 노드를 삭제한다고 가정하자.

이때 그냥 이 노드만 삭제해서는 안되고, 그 자리를 누군가 대신 채워야만 이진 탐색 트리가 유지된다.

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

 

🤔 이진 탐색 트리 삭제에 대한 경우의 수

1. 삭제할 노드가 리프 노드인 경우
2. 삭제할 노드가 하나의 자식 노드를 갖는 경우
3. 삭제할 노드가 두 개의 자식 노드를 갖는 경우

하지만, 구현 방법에 따라 삭제 대상이 루트 노드인 경우와 그렇지 않은 경우를 나눠야 하기 때문에 삭제에 대한 경우의 수는 최대 여섯 가지로 구분할 수 있다.

 

1. 삭제할 노드가 리프 노드인 경우

위 그림과 같이 리프 노드를 삭제하는 것으로 삭제 과정이 완료된다.

 

2. 삭제할 노드가 하나의 자식 노드를 갖는 경우

위 그림과 같이 부모 노드와 자식 노드를 연결하는 것이 관건이다. 위 그림의 왼쪽 트리에서 10이 저장된 노드가 왼쪽 자식 노드이든 오른쪽 자식 노드이든 상관 없이 부모 노드인 8이 저장된 노드의 오른쪽 노드가 되어야 한다. 이는 10이 저장된 노드가 9가 저장된 노드를 대신하는 관계이기 때문이다.

 

3. 삭제할 노드가 두 개의 자식 노드를 갖는 경우

위 트리에서 8을 삭제할 경우 이를 대체할 후보로 다음 두 개의 노드를 꼽을 수 있다.

• 8이 저장된 노드의 왼쪽 서브 트리에서 가장 큰 값인 7을 저장한 노드
• 8이 저장된 노드의 오른쪽 서브 트리에서 가장 작은 값인 9를 저장한 노드

이렇듯 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값이나, 오른쪽 서브 트리에서 가장 작은 값을 저장한 노드로 대체하면 된다. 이는 서브 트리에서 가장 큰 값이나 가장 작은 값을 저장한 노드를 찾는 것은 어렵지 않기 때문에 가능한 방법이다.

위 그림과 같이 가장 큰 값을 찾을 때는 NULL을 만날 때까지 계속해서 오른쪽 자식 노드로 이동하고,

가장 작은 값을 찾을 때는 NULL을 만날 때까지 계속해서 왼쪽 자식 노드로 이동하면 된다.

어느 방법을 선택해도 이진 탐색 트리의 유지에는 문제가 없으므로 아래 방법을 선택한다고 생각하자.

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

위 그림과 같이 삭제의 결과를 이루기 위해 해야 할 일은 다음과 같다.

삭제가 되는 8이 저장된 노드를 9가 저장된 노드로 대체한다.

그리고 이로 인해서 생기는 빈자리는 9가 저장된 노드의 자식 노드로 대체한다.

위 그림은 8이 저장된 노드의 위치에 9가 저장된 노드를 가져다 놓지 않고, 값의 대입을 통해 노드의 교체를 대신하고 있다. 이 방법을 사용할 경우, 삭제 대상인 8이 저장된 노드의 부모 노드와 자식 노드의 연결을 유지하기 위해 별도의 코드를 삽입할 필요가 없기 때문에 여러모로 편리하다. 이때 10을 저장하고 있는 자식 노드의 값을 단순히 대입만 하는 것은 리프 노드가 아닐 경우가 있어서 불가능하다.

 

✍🏻 삭제할 노드가 두 개의 자식 노드를 갖는 경우 삭제 과정

1. 삭제할 노드를 대체할 노드를 찾는다.
2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
3. 대체할 노드의 부모 노드와 자식 노드를 연결한다.

 

참고자료

책 - 윤성우의 열혈 자료구조 (2012년 1월)