[Algorithm]탐색1

📚순차 탐색

📄탐색이란?

여러 개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 것

데이터의 형태: 리스트, 트리, 그래프 등

관련 연산 -> 탐색 + 초기화, 삽입, 삭제

• 탐색 방법
  • 리스트 형태 -> 순차 탐색, 이진 탐색
  • 트리 형태 -> 이진 탐색 트리, 2-3-4 트리
  • 레드-블랙 트리, B-트리
  • 해시 테이블 -> 해시 함수, 충돌 행결 방법

📄순차 탐색

리스트 형태(배열, 연결리스트)로 주어진 원소들을 처음부터 하나씩 차례로 순차 비교하면서 원하는 값을 갖는 원소를 찾는 방법

int SequentialSearch(int array[], int size, int target)
{
	int i = 0;

	// 배열의 크기 만큼 반복하고 target을 배열에서 찾을 때 까지 반복
	while (i < size && array[i] != target)
	{
		++i;
	}

	return i;
}

📄성능과 특징

• 탐색, 삭제 연산의 시간 복잡도: O(n)

탐색 성공 -> 1번 ~ n번 비교(평균 (n+1)/2번)

탐색 실패 -> 항상 n번 비교

삭제 -> 삭제할 원소의 순차 탐색 O(n) 후, 마지막 원소 이동 O(1)

• 삽입 연산의 시간 복잡도: O(1)

리스트의 마지막에 추가하는데 상수 시간만 필요

• 정렬되지 않고 크기가 작은 데이터에 적합: 모든 리스트 형태의 입력에 적용 가능 -> 비정렬 데이터 탐색에 적합하다.

📚이진 탐색

📄이진 탐색

정렬된 리스트 형태(배열)로 주어진 원소들을 절반씩 줄여 가면서 원하는 값을 가진 원소를 찾는 방법.

분할정복 방법이 적용된 알고리듬이다.

📄탐색 방법

배열의 가운데 원소 array[mid]와 탐색 키 key를 비교

mid = (시작 인덱스 left + 마지막 인덱스 right) / 2

1. array[mid] = key -> 탐색 성공(인덱스 mid 반환하고 종료)
2. key < array[mid] -> 이진탐색(원래 크기의 1/2인 왼쪽 부분배열) 순환 호출
3. key > array[mid] -> 이진탐색(원래 크기의 1/2인 오른쪽 부분배열) 순환 호출

int BinarySearch(int array[], int key, int left, int right)
{
	if (left > right)
	{
		return -1;
	}

	int mid = (left + right) / 2;

	if (array[mid] == key)
	{
		return mid;
	}
	else if (array[mid] > key)
	{
		BinarySearch(array, key, left, mid - 1);
	}
	else
	{
		BinarySearch(array, key, mid + 1, right);
	}
}

📄성능과 특징

이진 탐색은 주어진 배열이 정렬되어 있지 않으면 탐색을 할 수 없으므로 정렬을 먼저 수행해야 한다.

이진 탐색은 원소의 직접적인 접근(배열의 중간값에 접근)이 필요하기 때문에 연결 리스트 구조에서는 이진 탐색이 불가능하다.

• 성능
  • 탐색: O(logn)
  • 초기화 연산: O(nlogn) -> 처음에 배열을 정렬 시켜줘야 하기 때문
  • 삽입/삭제 연산: O(n) -> 삽입과 삭제할 위치를 찾았으면 나머지 원소들을 하나씩 옮겨줘야 하기 때문

이진 탐색은 삽입과 삭제가 빈번한 경우에 부적합하다. 연산 후 리스트의 정렬 상태를 유지하기 위해 O(n)의 데이터 이동이 필요하기 때문이다.

📚이진 탐색 트리

📄이진 트리

이진 탐색 트리는 모든 노드에 대해 아래 두 성질을 모두 만족하는 이진 트리이다.

• 한 노드의 왼쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 작다.
• 한 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 크다.

📄탐색 연산

루트 노드에서부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 탐색을 진행한다.

• 탐색 키 값이 루트 노드의 키 값과 같다면 원하는 키를 찾았으므로 탐색을 종료한다.

• 탐색 키 값이 루트 노드의 키 값보다 작다면 루트 노드의 왼쪽 서브트리를 대상으로 탐색한다.

• 탐색 키 값이 루트 노드의 키 값보다 크다면 루트 노드의 오른쪽 서브트리를 대상으로 탐색한다.

위 과정을 순환적으로 수행하여 이진 탐색 트리에서 탐색 키를 찾거나, 탐색 대상이 되는 자식 노드가 없어 탐색 키를 찾지 못하는 것을 알게 된다.

📄삽입 연산

삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로서 새 노드를 추가한다. 이때 이진 탐색의 삽입 연산과 달리 다른 노드를 움직일 필요는 없다. 삽입할 원소가 이미 이진 탐색 트리에 존재하여 탐색으로 찾게 되면 그대로 탐색을 종료한다.

📄삭제 연산

• 후속 노드(Successor): 어떤 노드의 바로 다음 키 값을 갖는 노드

이진 탐색 트리의 삭제 연산은 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리한다.

1. 자식 노드가 없는 경우(리프 노드의 경우): 남는 노드가 없어 위치 조절을 안해도 된다.

2. 자식 노드가 하나인 경우: 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다.

3. 자식 노드가 두 개인 경우: 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고, 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리한다.

📄성능과 특징

• 탐색, 삽입, 삭제 연산의 시간 복잡도
  • 키값을 비교하는 횟수에 비례 -> 이진 트리의 높이가 h라면 O(h)
  • 모든 노드 차수가 2인 경우(리프 노드 제외) -> 노드의 자식이 2개 -> 평균 수행시간 O(log n)
  • 모든 노드의 차수가 1인 경우(리프 노드 제외) -> 노드의 자식이 1개 -> 평균 수행시간 O(n)
• 삽입/삭제 연산 시 기존 노드의 이동이 거의 발생하지 않음
  • 삽입 연산: 노드의 이동이 없음
  • 삭제 연산: 상수 번 이동
• 원소의 삽입/삭제에 따라 경사 트리 형태가 될 수 있다.
  • 최악의 수행시간 O(n)을 가짐

경사 트리가 만들어지지 않도록 트리의 균형을 유지해서 O(log n)을 보장하도록 하는 것이 균형 탐색 트리이다.(탐색 트리의 좌우 서브트리가 같은 높이를 유지하는 자료구조) 균형 탐색 트리에는 2-3-4 트리, 레드-블랙 트리, B-트리가 있다.

📚2-3-4 트리

📄균형 탐색 트리

다음 성질을 만족하는 균형 탐색트리를 2-3-4트리라고 한다.

• 2-노드 -> 1개의 키와 2개의 자식을 갖는 노드
• 3-노드 -> 2개의 키와 3개의 자식을 갖는 노드

• 4-노드 -> 3개의 키와 4개의 자식을 갖는 노드

• 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작다.

• 각 노드의 한 키의 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 크다.

• 모든 리프 노드의 레벨은 동일하다.

📄탐색 연산

이진 탐색 트리의 탐색 연산과 유사하게 루트 노드에서부터 탐색 키를 가진 원소를 찾아 나가는 방식이다. 단, 3-노드와 4-노드는 키값을 2개 이상 가지므로 탐색 키값이 해당 노드에 없는 경우 어느 자식을 탐색해야 할지를 정확하게 찾아야 한다.

📄삽입 연산

이진 탐색 트리의 삽입 연산과 유사하게 삽입할 원소를 이용하여 탐색하다가 탐색할 자식 노드가 없으면 현재 리프 노드에 키로 추가한다. 다만 탐색 과정에서 4-노드를 만나면 항상 노드 분할을 우선 수행한다.

노드 분할은 3개 키를 갖는 4-노드 하나를 1개의 키를 갖는 2-노드 셋으로 분할하는 것을 말한다. 이때 가운데 키로 만든 2-노드가 부모 노드가 되고 나머지 2개의 2-노드가 자식 노드가 되는데, 분할되는 4-노드의 부모 노드가 있다면 가운데 키로 2-노드를 만드는 대신 가운데 키를 부모 노드에 추가한다.

📄삭제 연산

이진 탐색 트리의 삭제 연산과 유사하다. 다만, 삭제할 원소를 탐색하여 찾은 키를 삭제한 후 2-3-4 트리의 성질을 만족하도록 노드의 구조를 조정하는 규칙이 필요하다.

📄성능 및 특징

• 탐색, 삽입, 삭제 연산의 시간 복잡도: O(logn)

• 삽입/삭제가 일어나도 경사 트리가 되지 않는다.
  • 루트 노드가 분할되는 경우에 한해서 모든 노드의 레벨이 동일하게 1씩 증가
• 2-3-4 트리를 그대로 구현하면 노드 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 존재한다. -> 레드-블랙 트리 고안