[자료구조] 탐색

순차탐색

int seq_search(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; // 탐색 성공
}

 

 

이진탐색

• 정렬된 배열의 탐색에 적합함
• 배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.

search_binary(list, low, high):
	middle <- low에서 high사이의 중간 위치
	if (탐색값 == list[middle])
    	return middle;
    else if (탐색값 < list[middle])
    	return list[0]부터 list[middle - 1]에서의 탐색;
    else if (탐색값 > list[middle])
    	return list[middle + 1]부터 list[high]에서의 탐색;

 

 

 

색인 순차 탐색

• 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법
• 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있음
• 인덱스 테이블은 모두 정렬되어 있어야 함

int search_index(int key, int n)
{
	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);
}

 

 

 

 

보간 탐색

• 비례식을 이용한 것으로 값과 위치는 비례한다는 가정에서 탐색키에 해당되는 위치를 비례식으로 구한 것이다.
• (list[high] - list[low]) : (k - list[low]) = (high - low) : (탐색 위치 - low)
• 외부곱 = 내부곱
• 탐색 위치 = ((k - list[low]) (high - low) / (list[high] - list[low])) + low

int interpol_search(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;
}

 

 

 

이진 탐색 트리

• 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉, 자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 한다.
• 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조로 되어 있다.
• 따라서 삽입, 삭제가 빈번히 이루어진다면 반드시 이진 탐색트리를 사용해야 한다.

알고리즘	최악		평균
	탐색	삽입	탐색	삽입
순차탐색	N	N	N/2	N
이진 탐색	logN	N	logN	N/2
이진 탐색 트리	N	N	logN	logN

 

 

 

AVL 트리

• AVL 트리는 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리를 말한다.
• 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다.

4가지의 경우	해결방법	설명
LL 타입	J(0) ← Y(1) ← X(2)    => J(0) ← Y(0) → X(0)	LL 회전: 오른쪽 회전
LR 타입	Y(-1) ← X(2) Y(-1) → J(0) => Y(0) ← J(1) ← X(2) => Y(0) ← J(0) → X(0)	LR 회전: 왼쪽 회전 → 오른쪽 회전
RR 타입	X(-2) → Y(-1) → J(0) => X(0) ← Y(0) → J(0)	RR 회전: 왼쪽 회전
RL 타입	X(-2) → Y(1) J(0) ← Y(-1) => X(-2) → J(-1) → Y(0) => X(0) ← Y(0) → J(0)	RL 회전: 왼쪽 회전 → 오른쪽 회전

 

#include<stdio.h> 
#include<stdlib.h> 
#define MAX(a, b) (a)
// AVL 트리 노드 정의
typedef struct AVLNode
{
	int key;
	struct AVLNode *left;
	struct AVLNode *right;
} AVLNode;

// 트리의 높이를 반환
int get_height(AVLNode *node)
{
	int height = 0;

	if (node != NULL)
		height = 1 + max(get_height(node->left),
			get_height(node->right));

	return height;
}
// 노드의 균형인수를 반환
int get_balance(AVLNode* node)
{
	if (node == NULL) return 0;

	return get_height(node->left)
		- get_height(node->right);
}

// 노드를 동적으로 생성하는 함수
AVLNode* create_node(int key)
{
	AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
	node->key = key;
	node->left = NULL;
	node->right = NULL;
	return(node);
}

// 오른쪽으로 회전시키는 함수
AVLNode *rotate_right(AVLNode *parent)
{
	AVLNode* child = parent->left;
	parent->left = child->right;
	child->right = parent;

	// 새로운 루트를 반환
	return child;
}

// 왼쪽으로 회전시키는 함수
AVLNode *rotate_left(AVLNode *parent)
{
	AVLNode *child = parent->right;
	parent->right = child->left;
	child->left = parent;

	// 새로운 루트 반환
	return child;
}

// AVL 트리에 새로운 노드 추가 함수
// 새로운 루트를 반환한다. 
AVLNode* insert(AVLNode* node, int key)
{
	// 이진 탐색 트리의 노드 추가 수행
	if (node == NULL)
		return(create_node(key));

	if (key < node->key)
		node->left = insert(node->left, key);
	else if (key > node->key)
		node->right = insert(node->right, key);
	else	// 동일한 키는 허용되지 않음
		return node;

	// 노드들의 균형인수 재계산
	int balance = get_balance(node);

	// LL 타입 처리
	if (balance > 1 && key < node->left->key)
		return rotate_right(node);

	// RR 타입 처리
	if (balance < -1 && key > node->right->key)
		return rotate_left(node);

	// LR 타입 처리
	if (balance > 1 && key > node->left->key)
	{
		node->left = rotate_right(node->left);
		return rotate_right(node);
	}

	// RL 타입 처리
	if (balance < -1 && key < node->right->key)
	{
		node->right = rotate_right(node->right);
		return rotate_left(node);
	}
	return node;
}

// 전위 순회 함수
void preorder(AVLNode *root)
{
	if (root != NULL)
	{
		printf("[%d] ", root->key);
		preorder(root->left);
		preorder(root->right);
	}
}

int main(void)
{
	AVLNode *root = NULL;

	// 예제 트리 구축
	root = insert(root, 10);
	root = insert(root, 20);
	root = insert(root, 30);
	root = insert(root, 40);
	root = insert(root, 50);
	root = insert(root, 29);

	printf("전위 순회 결과 \n");
	preorder(root);

	return 0;
}