탐색
> 탐색의 단위는 항목이다. 항목은 가장 간단하게 숫자일 수 도 있고 아니면 구조체가 될 수 도 있다. 항목 안에는 항목과 항목을 구별시켜 주는 키가 존재한다. 이를 탐색키라고 한다. 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것이 탐색이다
순차탐색(sequential search)
- 순차탐색은 탐색 방법중에서 가장 간단하고 직접적인 탐색 방법이다. 순차 탐색은 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법이다
- 순차탐색의 시간복잡도 -
> 순차탐색은 탐색에 성공할 경우 평균 (n+1)/2번 비교하고 탐색이 실패한 경우 n번 비교하므로 순차 탐색의 시간 복잡도는 O(n)이다
- 정렬된 배열에서의 탐색
> 정렬되어 있지 않은 배열의 순차 탐색은 이해하고 구현하기 쉽다. 배열의 항목이 얼아 되지 않는 경우에는 충분히 가능한 알고리즘이다. 그러나 배열이 많은 항목을 가지고 있는 경우에는 순차 탐색은 비효율적이다.
- 정렬된 배열에서의 이진탐색
> 정렬된 배열에는 이진탐색이 가장 적합하다. 이진탐색은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내여 탐색의 범위를 반으로 줄인다. 이 방법에 의해 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다.
> 이진 탐색에서는 비교가 이루어질 때마다 탐색 범위가 급격하게 줄어든다. 찾고자 하는 항목이 속해있지 않은 부분은 전혀 고려할 필요가 없다. 이러한 방법을 반복적으로 사용하는 방법이 이진탐색이다. 이진 탐색을 적용하려면 탐색하기 전에 배열이 방드시 정렬되어 있어야 한다.
> 이진탐색은 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고 주로 고정된 데이터에 대한 탐색에 적합하다.
- 정렬된 배열에서의 색인 순차 탐색(indexed sequential search)
> 색인순차탐색 방법은 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m번째 데이터를 가지고 있다. 단 이때 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.
이진 탐색 트리
> 이진탐색와 이진탐색트리의 차이점을 살펴보면, 이진 탐색과 이진탐색트리는 근본적으로 같은 원리에 의한 탐색구조이다. 하지만 이진탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉 자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 한다. 이진탐색트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조로 되어 있다.
| 알고리즘 | 최악의경우 | 평균적인경우 | ||
| 탐색 | 삽입 | 탐색 | 삽입 | |
| 순차탐색 | N | N | N/2 | N |
| 이진탐색 | log N | N | log N | N/2 |
| 이진탐색트리 | N | N | log N | log N |
AVL 트리
- 각 노드에서 왼쪽 서브트리의 높이와 오른쪽서브 트리의 높이 차이가 1 이하인 이진트리를 말한다.
> AVL트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. 따라서 AVL트리는 균형트리가 항상 보장되기 때문에 탐색이 O(logn) 시간 안에 끝나게 된다.
- AVL트리의 탐색 연산
> 일반 이진탐색트리와 동일하며 시간복잡도는 O(log2n)이다
- AVL 트리의 연산
> 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입 연산과 삭제 연산 사이이다. 삽입 연산 시에는 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 따라서 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노드의 서브트리들에 대하여 다시 균형을 잡아야 한다. 그 외에 다른 노드들은 변경할 필요가 없다.
- 4가지 경우
- LL타입: 노드 Y의 왼쪽자식의 왼쪽 노드가 추가됨으로써 발생한다. 노드를 오른쪽으로 회전시키면 된다
- LL회전: 오른쪽 회전
- LR타입: 왼쪽 자식의 왼쪽에 노드가 추가됨으로서 발생한다. 균형 트리를 만들기 위해 2번의 회전이 필요하다
- LR회전: 왼쪽회전->오른쪽 회전
- RR타입: 노드 Y의 오른쪽자식의 오른쪽 노드가 추가됨으로서 발생한다. 노드를 왼쪽으로 회전시키면 된다
- RR회전: 왼쪽 회전
- RL타입: 오른쪽 자식의 왼쪽에 노드가 추가됨으로서 발생한다. 균형 트리를 만들기 위해 2번의 회전이 필요하다
- RL회전: 왼쪽회전->오른쪽 회전
- 트리의 높이 계산
- 순환 호출을 사용해서 구현된다. 루트 노드의 왼쪽 서브트리와 오른쪽 서브트리에 대하여 각각 순환호출을 하여 각각의 높이를 구한다
- 이들 중에서 더 큰 값에 1을 더하면 트리의 높이가 된다
- 양쪽 서브트리의 높이의 차이는 각각의 서브트리에 대하여 높이를 구한 다음에
- 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 빼면 된다
#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);
}
// 오른쪽으로 회전시키는 함수
//rotate_right함수
AVLNode *rotate_right(AVLNode *parent)
{
AVLNode* child = parent->left;
parent->left = child->right;
child->right = parent;
// 새로운 루트를 반환
return child;
}
// 왼쪽으로 회전시키는 함수
//rotate_left 함수
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;
}