1. 탐색이란
- 탐색(search)은 컴퓨터가 가장 많이 하는 작업 중의 하나이다.
- 탐색은 많은 시간이 요구되므로 효율적으로 수행하는 것은 매우 중요하다.
- 탐색의 단위는 항목이다. 항목 안에는 항목과 항목을 구별시켜주는 키(key)가 존재한다. 이를 탐색 키(search key)라고 한다.
2. 정렬되지 않은 배열에서의 탐색
1) 순차 탐색(sequential search)
int seq_search(int key, int low, int high)
{
int i;
for (i = low; i <= high; i++)
if (list[i] == key)
return i; // 탐색에 성공하면 키 값의 인덱스 반환
return -1; // 탐색에 실패하면 -1 반환
}2) 개선된 순차 탐색
- 리스트의 끝에 찾고자 하는 키값을 저장, 비교 연산의 수를 반으로 줄일 수 있다.
int seq_search2(int key, int low, int high)
{
int i;
list[high + 1] = key;
for (i = low; list[i] != key; i++) // 키값을 찾으면 종료
;
if (i == (high + 1)) return -1; // 탐색 실패
else return i; // 탐색 성공
}
3. 정렬된 배열에서의 탐색
1) 이진 탐색
- 정렬된 배열의 탐색에는 이진 탐색(binary search)이 가장 적합하다.
- 10억 명의 이름이 정렬된 배열에서 이진 탐색을 이용하면 단지 30번의 비교만으로 검색이 완료된다.
- 이진 탐색은 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다.
- 재귀 호출을 이용한 이진 탐색
int search_binary(int key, int low, int high)
{
int middle;
if (low <= high) {
middle = (low + high) / 2;
if (key == list[middle]) // 탐색 성공
return middle;
else if (key<list[middle]) // 왼쪽 부분리스트 탐색
return search_binary(key, low, middle - 1);
else // 오른쪽 부분리스트 탐색
return search_binary(key, middle + 1, high);
}
return -1; // 탐색 실패
}
- 반복을 이용한 이진 탐색
int search_binary2(int key, int low, int high)
{
int middle;
while (low <= high) { // 아직 숫자들이 남아 있으면
middle = (low + high) / 2;
if (key == list[middle])
return middle;
else if (key > list[middle])
low = middle + 1;
else
high = middle - 1;
}
return -1; // 발견되지 않음
}
2) 색인 순차 탐색
- 색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다.
- 인덱스 테이블은 주자료 테이블에서 일정 간격으로 발췌한 자료를 가지고 있다.
- 이때 주자료 테이블과 인덱스 테이블은 모두 정렬되어 있어야 한다.
int search_index(int key)
{
int i, low, high;
// 키 값이 리스트 범위 내의 값이 아니면 탐색 종료
if (key<list[0] || key>list[n - 1])
return -1;
// 인덱스 테이블을 조사하여 해당키의 구간 결정
for (i = 0; i<INDEX_SIZE; i++)
if (index_list[i].key <= key &&
index_list[i + 1].key>key)
break;
if (i == INDEX_SIZE) { // 인덱스테이블의 끝이면
low = index_list[i - 1].index;
high = n;
}
else {
low = index_list[i].index;
high = index_list[i + 1].index;
}
// 예상되는 범위만 순차 탐색
return seq_search(key, low, high);
}
3) 보간 탐색
- 보간 탐색(interpolation search)은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색 키가 존재할 위치를 예측하여 탐색하는 방법이다.
- 탐색 위치 = $$ \frac{k-list[low]}{list[high]-list[low]}*(high-low)+low $$
- 위의 식은 탐색 위치를 결정할 때 찾고자 하는 키 값이 있는 곳에 근접하게 되도록 가중치를 주는 것이다.
- 값과 위치는 비례한다는 가정
int search_interpolation(int key, int n)
{
int low, high, j;
low = 0;
high = n - 1;
while ((list[high] >= key) && (key > list[low])) {
j = ((float)(key - list[low]) / (list[high] - list[low])
*(high - low)) + low;
if (key > list[j]) low = j + 1;
else if (key < list[j]) high = j - 1;
else low = j;
}
if (list[low] == key) return(low); // 탐색성공
else return -1; // 탐색실패
}
4. 균형 이진 탐색 트리
- 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조
- 삽입, 삭제가 빈번히 이루어진다면 이진 탐색 트리를 사용하는 것이 적합하다.
- 이진 탐색 트리가 경사 트리가 되면 효율이 매우 떨어지므로 균형을 유지하는 것이 무엇보다 중요하다.
1) AVL 트리
- 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리를 말한다.
- 균형 인수(balance factor)는 (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)로 정의된다.
- 모든 노드의 균형 인수가 ±1이하이면 AVL 트리이다.
(1) AVL 트리의 탐색 연산
- AVL 트리도 탐색에서는 일반 이진 탐색 트리의 탐색 연산과 동일하다. 따라서 시간 복잡도는 O(log2n)이다.
(2) AVL 트리의 삽입 연산
- 균형 상태의 이진 탐색 트리에서 균형이 깨지는 것은 삽입 연산과 삭제 연산 때문이다.
- 균형 인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 한다. 그 외의 다른 노드들은 일체 변경할 필요가 없다.
- A는 ±2가 된 가장 가까운 조상 노드, N은 새로 삽입된 노드
- LL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.
- RR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.
- RL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽 - 왼쪽으로 회전시킨다.
- LR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽 - 오른쪽으로 회전시킨다.
- AVL 트리에서의 단순 회전 알고리즘
rotate_LL(A)
B(중간 노드)의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
A를 B의 오른쪽 자식 노드로 만든다.
rotate_RR(A)
B(중간 노드)의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.
A를 B의 왼쪽 자식 노드로 만든다.
- AVL 트리에서의 이중 회전 알고리즘
rotate_RL(A)
rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
rotate_RR(A)
rotate_LR(A)
rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
rotate_LL(A)
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
struct avl_node {
struct avl_node *left_child, *right_child; /* Subtrees. */
int data; /* Pointer to data. */
};
struct avl_node *root;
// 오른쪽 회전 함수
struct avl_node *
rotate_right(struct avl_node *parent)
{
struct avl_node *child = parent->left_child;
parent->left_child = child->right_child;
child->right_child = parent;
return child;
}
// 왼쪽 회전 함수
struct avl_node *
rotate_left(struct avl_node *parent)
{
struct avl_node *child = parent->right_child;
parent->right_child = child->left_child;
child->left_child = parent;
return child;
}
// 오른쪽-왼쪽 회전 함수
struct avl_node *
rotate_right_left(struct avl_node *parent)
{
struct avl_node *child = parent->right_child;
parent->right_child = rotate_right(child);
return rotate_left(parent);
}
// 왼쪽-오른쪽 회전 함수
struct avl_node *
rotate_left_right(struct avl_node *parent)
{
struct avl_node *child = parent->left_child;
parent->left_child = rotate_left(child);
return rotate_right(parent);
}
// 트리의 높이를 반환
int get_height(struct avl_node *node)
{
int height=0;
if( node != NULL )
height = 1 + __max(get_height(node->left_child), get_height(node->right_child));
return height;
}
// 노드의 균형인수를 반환
int get_height_diff(struct avl_node *node)
{
if( node == NULL ) return 0;
return get_height(node->left_child) - get_height(node->right_child);
}
// 트리를 균형트리로 만든다
struct avl_node *
rebalance(struct avl_node **node)
{
int height_diff = get_height_diff(*node);
if( height_diff > 1 ){
if( get_height_diff((*node)->left_child) > 0 )
*node = rotate_right(*node);
else
*node = rotate_left_right(*node);
}
else if ( height_diff < -1 ){
if( get_height_diff((*node)->right_child) < 0 )
*node = rotate_left(*node);
else
*node = rotate_right_left(*node);
}
return *node;
}
// AVL 트리의 삽입 연산
struct avl_node *
avl_add(struct avl_node **root, int new_key)
{
if( *root == NULL ){
*root = (struct avl_node *)
malloc(sizeof(struct avl_node));
if( *root == NULL ){
fprintf(stderr, "메모리 할당 에러\n");
exit(1);
}
(*root)->data = new_key;
(*root)->left_child = (*root)->right_child = NULL;
}
else if( new_key < (*root)->data ){
(*root)->left_child=avl_add(&((*root)->left_child), new_key);
*root = rebalance(root);
}
else if( new_key > (*root)->data ){
(*root)->right_child=avl_add(&((*root)->right_child), new_key);
(*root) = rebalance(root);
}
else{
fprintf(stderr, "중복된 키 에러\n");
exit(1);
}
return *root;
}
// AVL 트리의 탐색함수
struct avl_node *avl_search(struct avl_node *node, int key)
{
if( node == NULL ) return NULL;
printf("%d ", node->data);
if( key == node->data ) return node;
else if( key < node->data )
return avl_search(node->left_child, key);
else
return avl_search(node->right_child, key);
}
void main()
{
//8,9,10,2,1,5,3,6,4,7,11,12
avl_add(&root, 8);
avl_add(&root, 9);
avl_add(&root, 10);
avl_add(&root, 2);
avl_add(&root, 1);
avl_add(&root, 5);
avl_add(&root, 3);
avl_add(&root, 6);
avl_add(&root, 4);
avl_add(&root, 7);
avl_add(&root, 11);
avl_add(&root, 12);
avl_search(root, 12);
}
2) 2-3 트리
- 2-3트리는 차수가 2또는 3인 노드를 가지는 트리
- 2-노드는 일반 이진 탐색 트리처럼 하나의 데이터 k1과 두 개의 자식 노드를 가진다.
- 3-노드는 2개의 데이터 k1, k2와 3개의 자식 노드를 가진다.
- 2-3 트리에서의 탐색
tree23_search(Tree23Node *root, int key)
{
if (root == NULL) // 트리가 비어 있으면
return FALSE;
else if (key == root->data)// 루트의 키==탐색키
return TRUE;
else if (root->type == TWO_NODE) { // 2-노드
if (key < root->key)
return tree23_search(root->left, key)
else
return tree23_search(root->right, key)
}
else { // 3-노드
if (key < root->key1)
return tree23_search(root->left, key)
else if (key > root->key2)
return tree23_search(root->right, key)
else
return tree23_search(root->middle, key)
}
}
(1) 2-3 트리의 삽입 연산 리스트 ADT의 구현
- 2-3 트리의 노드는 2개의 데이터 값을 저장할 수 있다. 2-3 트리에 데이터 추가 시에 노드에 추가할 수 있을 때까지 데이터는 추가되고 더 이상 저장할 장소가 없는 경우에는 노드를 분리하게 된다.
- 중간 값을 한 레벨 위로 올리고 제일 작은 값을 왼쪽 노드로, 제일 큰 값을 오른쪽 노드로 만드는 것이다.
- 3가지의 경우로 나누어진다. 단말 노드를 분리 / 비단말 노드를 분리 / 루트 노드를 분리
- 2-3 트리에서 트리의 높이가 증가하게 되는 경우는 루트 노드를 분리하는 경우뿐이다.
3) 2-3-4 트리
- 2-3-4 트리는 하나의 노드가 4개의 자식까지 가질 수 있도록 2-3 트리를 확장한 것이다.
- 4-노드는 4개의 자식을 가질 수 있고, 3개의 데이터(small, middle, large)를 가질 수 있다.
- 2-3-4 트리에서 키를 삽입해야 할 단말 노드가 만약 2-노드 또는 3-노드이면 간단하게 삽입만 하면 된다. 문제는 삽입해야 할 단말 노드가 4-노드이면 후진 분할이 일어나게 된다.
- 이를 방지하기 위하여 삽입 노드를 찾는 순회(루트 → 단말)시에 4-노드를 만나면 미리 분할을 수행한다.
- 3가지 경우를 고려해서 알고리즘을 만들어야 한다.
- 4-노드가 루트인 경우 / 4-노드의 부모가 2-노드인 경우
- 4-노드의 부모가 3-노드인 경우
[Reference]
- 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년
'DataStructure' 카테고리의 다른 글
| Hashing(해싱) (0) | 2022.03.14 |
|---|---|
| Graph(그래프) - 2 (0) | 2022.03.11 |
| Graph(그래프) - 1 (0) | 2022.03.11 |
| Sorting(정렬) (0) | 2022.03.11 |
| Priority Queue(우선순위 큐)와 Heap(힙) (0) | 2022.03.11 |