탐색(Search)
[탐색이란?]
- 탐색(search)은 컴퓨터가 가장 많이 하는 작업 중의 하나임.
- 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업임과 동시에 많은 시간이 요구되므로 탐색을 효율적으로 수행하는 것은 매우 중요함.
- 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업.
- 탐색을 위하여 사용되는 자료 구조는 배열, 연결 리스트, 트리, 그래프 등 매우 다양할 수 있음.
- 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것.
- 그러나 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 더욱 진보된 방법으로 자료를 저장하고 탐색해야 함.
- 탐색의 단위는 항목이며, 항목은 간단하게 숫자일 수도 있고, 아니면 구조체가 될 수도 있음.
- 항목 안에는 항목과 항목을 구별시켜주는 키(key)가 존재함. 이를 탐색 키(search key)라고 함.
- 탐색 : 탐색 키와 데이터로 이루어진 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 것.
[정렬되지 않은 배열에서의 탐색]
(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 반환 } |
-> 탐색의 대상이 되는 배열은 list[]라고 가정.
-> 탐색의 범위는 low에서 high까지로 함수의 파라미터로 주어짐.
-> 탐색에 성공하면 그 항목이 발견된 인덱스를 반환하고 그렇지 않으면 -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; // 탐색 성공 } |
- 탐색이 성공하는 경우에는 리스트에 있는 키의 위치에 따라 비교 횟수가 결정되는데, 모든 키가 탐색될 확률이 동일하다고 가정하면 평균 비교 횟수는 다음과 같음.
(1 + 2 + 3 + … + n) / n = (n + 1) / 2
- 따라서 순차 탐색은 탐색에 성공할 경우 평균 (n+1)/2번 비교하고, 탐색이 실패한 경우 n번 비교함.
- 순차 탐색의 시간 복잡도는 O(n)이 됨.
// 순차 탐색 프로그램 (정렬되지 않은 배열)
#include <stdio.h>
#define MAX_SIZE 1000
int list[MAX_SIZE] = { 3, 9, 15, 22, 31, 55, 67, 88, 91 };
// 순차 탐색
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 반환
}
// 개선된 순차 탐색
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; // 탐색 성공
}
void main() {
int i, j;
// 순차 탐색
i = seq_search(67, 0, 10);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
// 개선된 순차 탐색
j = seq_search2(88, 0, 10);
if (j >= 0) {
printf("탐색 성공 j=%d\n", j);
}
else {
printf("탐색 실패\n");
}
}
[정렬된 배열에서의 탐색]
- 정렬되어 있지 않은 배열의 순차 탐색은 이해하고 구현하기가 쉬움.
- 만약 배열의 항목이 얼마 되지 않은 경우에는 충분히 가능한 알고리즘임.
- 그러나 배열이 많은 항목을 가지는 경우에는 순차 탐색은 너무나 비효율적인 방법임.
- 만약 100만 개 중에서 하나를 찾는 문제라면 순차 탐색으로는 상당한 시간이 소요됨.
- 따라서 훨씬 빠른 방법이 요구됨.
(1) 정렬된 배열에서의 순차 탐색
- 정렬하려는 배열이 정렬되어 있으면 순차 탐색 실행 중에 키 값보다 큰 항목을 만나면 배열의 마지막까지 검색하지 않고도 탐색 항목이 없음을 알 수 있음.
- 그러나 이 방법도 순차 탐색의 근본적인 비효율성을 없애지는 못함.
- 만약 찾고자 하는 항목이 배열의 뒷부분에 존재한다면 원래의 순차 탐색과 거의 차이가 나지 않음.
- 정렬된 배열에서의 순차 탐색 프로그램
// 순차 탐색 프로그램 (정렬된 배열)
#include <stdio.h>
#define MAX_SIZE 1000
int list[MAX_SIZE] = { 3, 9, 15, 22, 31, 55, 67, 88, 91 };
// 오름차순으로 정렬된 배열 리스트의 순차 탐색
int sorted_seq_search(int key, int low, int high) {
int i;
for (i = low; i <= high; i++) {
if (list[i] > key) return -1;
if (list[i] == key) return i;
}
}
void main() {
int i, j;
i = seq_search(67, 0, 10);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
}
- 비교 횟수는 배열에 해당 항목이 존재하여 탐색이 성공했을 경우에는 일반 순차 탐색과 동일하지만, 해당 항목이 리스트에 존재하지 않아서 탐색이 실패할 경우에는 비교 횟수가 반으로 줄어듦.
- 그러나 시간 복잡도의 차수는 원래의 순차 탐색과 동일하게 O(n)으로 변함이 없음.
(2) 이진 탐색
- 순차 탐색은 프로그램이 간단하고 작은 배열의 탐색에는 효과적일 수 있으나 큰 배열의 탐색에는 적합하지 않음.
- 정렬된 배열의 탐색에는 이진 탐색(binary search)이 가장 적합함.
- 이진 탐색은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 리스트에 있는지를 알아내어 탐색의 범위를 반으로 줄임.
- 이러한 방법에 의해 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄임.
- 10억 명의 이름이 정렬된 배열에서 이진 탐색을 이용하여 특정한 이름을 찾는다면 단지 30번의 비교만으로 검색이 완료됨.
- 반면에 순차 탐색에서는 평균 5억 번의 비교가 있어야 됨.
- 이진 탐색은 실제로 우리가 일상생활에서 많이 이용하고 있는 방법.
예) 영어사전에서 단어를 찾을 때 등
- 이진 탐색에서는 비교가 이루어질 때마다 탐색 범위가 반으로 줄어듦. (찾고자하는 항목이 속해 있지 않은 부분은 전혀 고려할 필요가 없기 때문.)
- 이러한 방법을 반복적으로 사용하는 방법이 이진 탐색.
- 이진 탐색을 적용하려면 탐색하기 전에 배열이 반드시 정렬되어 있어야 함.
- 따라서 이진 탐색은 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합함.
- 이진 탐색은 재귀 호출로도 구현할 수 있지만, 반복문을 사용하여 구현할 수도 있음. (효율성을 위해서는 반복 구조를 사용하는 것이 더 나음.)
- 이진 탐색 프로그램
// 이진 탐색 프로그램
#include <stdio.h>
int list[MAX_ELEMENTS] = { 2, 6, 11, 13, 18, 20, 22, 27, 29, 39, 34, 38, 41, 42, 45, 47 };
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; // 탐색 실패
}
void main() {
int i, j;
i = search_binary(11, 0, 10);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
}
- 이진 탐색 프로그램 (다른 방식)
// 이진 탐색 프로그램 (다른 방식)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ELEMENTS 10000000L
int list[MAX_ELEMENTS];
int count; // 수행횟수
// Another Version of Binary Search
// 이진 탐색
int binsearch(int list[], int n, int searchnum) {
int left = 0;
int right = n - 1;
int middle;
count = 0;
while (left <= right) { // 아직 숫자들이 남아 있으면
count++;
middle = (left + right) / 2;
if (searchnum == list[middle]) {
return middle;
}
else if (searchnum < list[middle]) {
right = middle - 1;
}
else {
left = middle + 1; break;
}
}
return -1; // 발견되지 않음
}
// 순차 탐색
int seqsearch(int list[], int n, int searchnum) {
int i;
count = 0;
for (i = 0; i < n; i++) {
count++;
if (searchnum == list[i]) {
return i;
}
}
return -1; // 발견되지 않음
}
int main()
{
int i;
int search_number;
int return_value;
clock_t start, finish;
clock_t duration;
for (i = 0; i<MAX_ELEMENTS; i++)
list[i] = i;
printf("숫자를 입력하세요.\n", &search_number);
scanf("%d", &search_number);
start = clock();
return_value = seqsearch(list, MAX_ELEMENTS, search_number);
finish = clock();
duration = finish - start;
printf("%d milliseconds\n", duration);
printf("문자의 수행횟수=%d\n ", count);
start = clock();
return_value = binsearch(list, MAX_ELEMENTS, search_number);
finish = clock();
duration = finish - start;
printf("%d milliseconds\n", duration);
printf("문자의 수행횟수=%d\n ", count);
if (return_value == -1) {
printf("숫자가 발견되지 않았습니다.\n", &search_number);
}
else {
printf("숫자가 위치 %d에서 발견되었습니다.\n", return_value);
}
return 0;
}
- 이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄임.
- 이러한 탐색 범위가 더 이상 줄일 수 없는 1이 될 때의 탐색 횟수를 k라 하면, 아래의 표와 같음.
- 표의 마지막 행에서 n./2^k = 1 이므로, k = log₂n임을 알 수 있음.
- 결국 이진 탐색의 시간 복잡도는 O(log₂n)이 됨.
| 비교 | 탐색 범위 |
| 0 | n |
| 1 | n/2 |
| 2 | n/4 |
| ... | ... |
| k | n/2^k |
(3) 색인 순차 탐색
- 색인 순차 탐색(indexed sequential search) : 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법.
- 인덱스 테이블은 주자료 테이블에서 일정 간격으로 발췌한 자료를 가지고 있음.
- 인덱스 테이블에 m개의 항목이 있고, 주자료 테이블의 데이터 수가 n이면 각 인덱스 항목은 주자료 테이블의 각 n/m번째 데이터를 가지고 있음.
- 이 때, 주자료 테이블과 인덱스 테이블은 모두 정렬되어 있어야 함.
- 색인 순차 탐색 알고리즘은 우선 인덱스 테이블에서 index[i] <= key < index[i+1]을 만족하는 항목을 찾음.
- 인덱스 테이블에서 위의 조건을 만족하는 항목으로부터 주자료 테이블에서 순차 탐색을 수행함.
- 이 방법은 주자료 테이블에서의 탐색 시간을 상당히 줄일 수 있으므로 빠른 시간 안에 원하는 항목을 발견할 수 있게 해주므로 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용하는 방법임.
- 색인 순차 탐색 프로그램
// 색인 순차 탐색 프로그램
#include <stdio.h>
#define MAX_SIZE 1000
#define INDEX_SIZE 10
int list[MAX_SIZE] = { 3, 9,15, 22, 31, 55, 67, 88, 91 };
int n = 9;
typedef struct {
int key;
int index;
} itable;
itable index_list[INDEX_SIZE] = { { 3,0 },{ 15,3 },{ 67,6 } };
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 반환
}
// INDEX_SIZE는 인덱스 테이블의 크기, n은 전체 데이터의 수
int index_search(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);
}
void main()
{
int i;
i = index_search(67);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
}
- 색인 순차 탐색 알고리즘의 탐색 성능은 인덱스 테이블의 크기에 좌우됨.
- 인덱스 테이블의 크기를 줄이면 주차료 테이블에서의 탐색 시간을 증가시키고, 인덱스 테이블의 크기를 크게 하면 인덱스 테이블의 탐색 시간을 증가시킴.
- 인덱스 테이블의 크기를 m이라 하고 주자료 테이블의 크기를 n이라 하면 색인 순차 탐색의 시간 복잡도는 O(m+n/m)과 같음.
- 색인 순차 탐색에서 데이터의 수가 증가하여 1차 인덱스 테이블의 크기가 매우 커지게 되면 2차 인덱스 테이블을 사용하고, 2차 인덱스 테이블은 1차 인덱스 테이블의 인덱스를 가리키도록 함.
- 따라서 탐색은 2차 인덱스 테이블의 탐색에서 시작하여 1차 인덱스를 거쳐서 주자료 테이블의 탐색으로 이어지게 됨.
(4) 보간 탐색
- 보간 탐색(interpolation search) : 사전이나 전화번호부를 탐색하는 방법과 같이 탐색 키가 존재할 위치를 예측하여 탐색하는 방법.
- 이는 우리가 사전을 찾을 때 'ㅎ'으로 시작하는 단어는 사전의 뒷부분에서 찾고, 'ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리임.
- 보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색함.
- 이진 탐색에서 탐색 위치는 항상 (low+high)/2이나, 보간 탐색에서는 찾고자 하는 키 값과 현재의 low, high 위치의 값을 고려하여 다음과 같이 탐색 위치를 결정함.
- 여기서 k는 찾고자 하는 키 값을, low와 high는 각각 탐색할 범위의 최소, 최대 인덱스 값을 나타냄.
- 즉, 위의 식은 탐색 위치를 결정할 때 찾고자 하는 키 값이 있는 곳에 근접하게 되도록 가중치를 주는 것임.
- 위의 식은 다음의 비례식을 정리한 것으로 생각할 수 있음.
- 즉, 값과 위치는 비례한다는 가정에서 탐색 키에 해당되는 위치를 비례식으로 구한 것.
예)
- 여기서 주의할 점은 계산되어 나오는 값은 일반적으로 실수이며 따라서 이 실수를 정수로 변환해주어야 함.
- 보통은 소수점 이하를 버리는 방법을 사용함.
- 많은 데이터가 비교적 균등하게 분포되어 있을 경우 보간 탐색은 이진 탐색보다 우수한 방법이 될 수 있으며. 보간 탐색 알고리즘은 이진 탐색과 비슷한 O(log₂n)의 시간 복잡도를 가짐.
- 보간 탐색 프로그램
// 보간 탐색 프로그램
#include <stdio.h>
#define MAX_SIZE 1000
int list[MAX_SIZE];
void init_list() {
int i;
for (i = 0; i < 1000; i++) {
list[i] = 7 * i;
}
}
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; // 탐색 실패
}
void main() {
int i = 0;
init_list();
i = search_interpolation(49, 999);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
}
[균형 이진 탐색 트리]
- 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조.
- 하지만, 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘듦.
- 즉, 자료를 삽입하고 삭제할 때마다 앞두의 원소들을 이동시켜야 함.
- 반면에, 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조로 되어 있음.
- 따라서 삽입과 삭제가 심하지 않은 정적인 자료를 대상으로 탐색이 이루어지는 경우에는 이진 탐색도 무난한 방법이나 삽입, 삭제가 빈번히 이루어진다면 이진 탐색 트리를 사용하는 것이 적합함.
- 이진 탐색 트리는 만약 트리가 균형 트리라면 탐색 연산은 O(log₂n)의 시간 복잡도를 가짐.
- 삽입, 삭제 연산은 이진 탐색 트리를 유지시키기는 하지만 균형 트리를 보장하지 않음.
- 만약 이진 탐색 트리가 균형 트리가 아닐 경우에는 탐색의 시간 복잡도가 O(n)으로 높아지게 됨.
- (a)의 이진 탐색 트리에서 최대 비교 횟수는 3회인 반면, (b)의 트리에서는 7회가 됨.
- 모든 항목이 균일하게 탐색된다는 가정하에 평균 비교 횟수를 비교해보면, (a)의 트리는 (1+2+2+3+3+3+3)/7=2.4회가 되는 반면, (b)는 (1+2+3+4+5+6+7)/7=4회가 됨.
- 따라서 만약 이진 탐색 트리가 (b)와 같이 경사 트리가 되면 탐색 시간은 순차 탐색과 같게 되어 매우 효율이 떨어짐.
- 따라서 이진 탐색 트리에서는 균형을 유지하는 것이 무엇보다 중요함.
(1) AVL 트리
- AVL 트리 : Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로, 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리
- AVL 트리는 트리가 비균형 상태로 되면 스스로 노드를 재배치하여 균형 상태로 만듦.
- 따라서 AVL 트리는 균형 트리가 항상 보장되기 때문에 탐색이 O(log₂n) 시간 안에 할 수 있음.
- 균형 인수(balance factor) : (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)
- 모든 노드의 균형 인수가 ±1 이하이면 AVL 트리임.
- AVL 트리도 탐색에서는 일반 이진 탐색 트리의 탐색 연산과 동일함.
- 따라서 시간 복잡도는 O(log₂n).
- 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입 연산과 삭제 연산 때문.
- 삽입 연산은 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있음.
- 따라서 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 함.
- 그외의 다른 노드들은 일체 변경할 필요가 없음.
예) (a)는 균형을 이룬 AVL 트리. 여기에 정수 1을 삽입하면 (b)처럼 노드 5와 노드 7이 균형 인수가 2가 되어 균형이 깨지게 됨. 따라서 여기서는 균형 인수가 2가 된 가장 가까운 조상 노드인 5부터 그 아래에 있는 노드들을 다시 배치하여 균형 상태로 만들어야 함.
- 균형이 깨진 트리를 다시 균형 있게 만들려면, 새로운 노드부터 균형 인수가 ±2가 된 가장 가까운 조상 노드까지를 회전시켜야 함.
- (b)의 경우, 노드 1, 3, 5를 오른쪽으로 회전 시키면 아래와 같이 되어서 다시 균형 트리가 됨. (다른 노드를 변경시키지 않음에 유의)
- AVL 트리에서 균형이 깨지는 경우에는 다음의 4가지의 경우가 있음.
(새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드를 A라 할 때)
1. LL 타입 : N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입됨.
2. RR 타입 : N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입됨.
3. RL 타입 : N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입됨.
4. LR 타입 : N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입됨.
- LL과 RR은 대칭이고, 역시 LR과 RL도 대칭임을 알 수 있음.
- 재균형시키는 방법도 각각의 경우에 따라 달라짐.
- 각각의 경우에 대해 균형 트리로 다시 만드는 방법
1. LL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킴.
2. RR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킴.
3. RL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킴.
4. LR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전 시킴.
- 단순 회전(single rotation) : 한 번만 회전시키는 것으로 LL 회전, RR 회전이 여기에 속함.
탐색 순서를 유지하면서 부모와 자식 원소의 위치를 교환하면 됨.
- 이중 회전(double rotation) : 두 번의 회전이 필요한 것으로 LR 회전, RL 회전이 여기에 속함.
1) LL 회전
- 일반적인 LL 타입은 조상 노드 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로써 발생함.
- LL 회전은 노드들을 오른쪽으로 회전시키면 됨.
2) RR 회전
- RR 타입은 조상 노드 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가됨으로써 발생함.
- 일반적인 경우의 RR타입은 노드 A와 B의 위치를 바꾸어 주고, 서브 트리들을 그림처럼 정리하면 균형 트리로 만들 수 있음.
3) RL 회전
- RL 타입은 조상 노드 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로써 발생함.
- RL 회전은 균형 트리를 만들기 위하여 2번의 회전이 필요함.
- RL 회전은 LL 회전을 한 다음, RR 회전을 하면 됨.
- AVL 트리의 노드 A의 오른쪽 서브 트리의 안쪽 서브 트리에 새로운 노드를 추가하면 비균형 트리가 되고, 이를 바로잡기 위해서는 LL 회전과 RR 회전의 2번의 회전이 필요함.
4) LR 회전
- LR 타입은 조상 노드 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가됨으로써 발생함.
- LR 회전은 균형 트리를 만들기 위하여 2번의 회전이 필요함.
- LR 회전은 RR 회전을 한 다음, LL 회전을 하면 됨.
- AVL 트리의 노드 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 새로운 노드를 추가하면 비균형 트리가 되고, 이를 바로잡기 위해서는 RR 회전과 LL 회전의 2번의 회전이 필요함.
- AVL 트리 구현 프로그램
// AVL 트리 구현 프로그램
#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인 노드를 가지는 트리로서 삽입이나 삭제 알고리즘이 AVL 트리보다 더 간단함.
- 2-3 트리는 하나의 노드가 두 개 또는 세 개의 자식 노드를 가짐.
- 차수가 2인 노드를 2-노드라고 하며, 2-노드는 일반 이진 탐색 트리처럼 하나의 데이터 k1과 두 개의 자식 노드를 가짐.
- 차수가 3인 노드를 3-노드라고 하며, 3-노드는 2개의 데이터 k1, k2와 3개의 자식 노드를 가짐.
- 왼쪽 서브 트리에 있는 데이터들은 모두 k1보다 작은 값임.
- 중간 서브 트리에 있는 값들은 모두 k1보다 크고 k2보다 작음.
- 오른쪽에 있는 데이터들은 모두 k2보다 큼.
- 2-3 트리의 탐색 연산은 이진 탐색 트리의 알고리즘을 조금만 확장하면 됨.
- 노드가 2-노드이냐 3-노드이냐에 따라서 해당하는 탐색을 진행하면 됨.
- 2-3 트리에서의 탐색
// 2-3 트리에서의 탐색
void tree23_search(Tree23Node *root, int key) {
if (root == NULL) { // 트리가 비어 있으면
return FALSE;
}
else if (key == root->key1) { // 루트의 키 == 탐색 키
return TRUE;
}
else if (root->type == TWO_NODE) { // 2-노드
if (key < root->key1) {
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);
}
}
}
- 2-3 트리의 노드는 2개의 데이터 값을 저장할 수 있음.
- 2-3 트리에 데이터 추가 시에 노드에 추가할 수 있을 때까지 데이터는 추가되고 더 이상 저장할 장소가 없는 경우에는 노드를 분리하게 됨.
- 2-3 트리 삽입의 예
- 노드가 분리되는 상황은 3가지의 경우로 나누어짐.
1. 단말 노드를 분리하는 경우
2. 비단말 노드를 분리하는 경우
3. 루트 노드를 분리하는 경우
1) 단말 노드를 분리하는 경우
- 만약 단말 노드가 이미 2개의 데이터를 가지고 있는데 새로운 데이터가 삽입되어야 한다면 이 단말 노드는 분리되어야 함.
- 단말 노드를 분리하는 데 부모 노드가 2-노드라면, (a)처럼 새로운 노드와 기존의 2개의 노드 중에서 중간 값은 부모 노드로 올라가게 되고, 작은 값과 큰 값은 새로운 노드로 분리되게 됨.
- 그러나 (b)처럼 만약 부모 노드가 이미 2개의 데이터를 가지고 있는 3-노드라면 부모 노드가 다시 분리되어야 함.
2) 비단말 노드를 분리하는 경우
- 비단말 노드가 분리되어야 하는 경우에는 역시 마찬가지로 중간 값을 다시 부모 노드로 올려보내고 작은 값과 큰 값을 별개의 노드로 분리함.
- 서브 트리들도 분리됨.
- 만약 다시 부모 노드에 추가 노드를 받을 만한 공간이 없다면 다시 이러한 분리 과정이 부모 노드에 대하여 되풀이됨.
(3) 루트 노드를 분리하는 경우
- 루트 노드는 이전 과정과 비슷함.
- 그러나 루트 노드를 분리하게되면 새로운 노드가 하나 생기게 되므로 트리의 높이가 하나 증가하게 됨.
- 새로 만들어지는 노드는 이 트리의 새로운 루트 노드가 됨.
- 2-3 트리에서 트리의 높이가 증가하게되는 것은 오직 이 경우뿐임.
(3) 2-3-4 트리
- 2-3-4 트리 : 하나의 노드가 4개의 자식까지 가질 수 있도록 2-3 트리를 확장한 것.
- 4개의 자식을 가질 수 있는 노드는 4-노드라고 불리며, 3개의 데이터를 가질 수 있음.
- 4-노드의 3개의 데이터를 각각 small, middle, large라고 하면 4-노드의 서브 트리에는 아래 그림과 같은 범위에 속하는 데이터들이 들어가게 됨.
- 2-3-4 트리를 탐색하는 것은 2-3 트리의 탐색 알고리즘에 4-노드를 처리하는 부분만 추가하면 됨.
- 2-3-4 트리에서 키를 삽입해야 할 단말 노드가 만약 2-노드 혹은 3-노드이면 간단하게 삽입만 하면 됨.
- 문제는 삽입해야 할 단말 노드가 4-노드이면 후진 분할(backward split)이 일어나게 됨.
- 따라서 2-3-4 노드에서는 후진 분할 연산을 방지하기 위하여 삽입 노드를 찾는 순회(루트->단말) 시에 4-노드를 만나면 미리 분할을 수행함.
- 미리 분할을 수행하였으므로 후진 분할을 할 필요가 없게 됨.
- 이는 2-3 트리와 비교됨.
- 2-3 트리는 삽입 또는 삭제를 위한 순회(루트->단말)와 분할과 합병의 영향으로 인한 순회(단말->루트)가 필요함.
- 따라서 2-3 트리에 비하여 2-3-4 트리의 장점은 루트에서 단말 노드로 한 번만 이동하면서 삽입이나 삭제가 가능하다는 것임.
- 2-3-4 트리에서는 삽입을 위하여 루트에서 단말 노드로 내려가는 동안 4-노드를 만나면 무조건 분할시킴.
- 따라서 단말 노드에 도달하게 되면 단말 노드의 부모 노드는 4-노드가 아니라는 것이 보장됨. -> 후진 이동을 막을 수 있음.
- 4-노드에 대하여 다음의 3가지 경우를 고려해서 알고리즘을 만들어야 함.
1. 4-노드가 루트인 경우
2. 4-노드의 부모가 2-노드인 경우
3. 4-노드의 부모가 3-노드인 경우
1) 4-노드가 루트인 경우
2) 4-노드의 부모가 2-노드인 경우
3) 4-노드의 부모가 3-노드인 경우
내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)
'Computer Science > Data Structure' 카테고리의 다른 글
| [C++] 인접 리스트를 이용하여 그래프 구현하기 (0) | 2021.05.19 |
|---|---|
| [C++] 인접 행렬을 이용하여 그래프 구현하기 (0) | 2021.05.19 |
| [C++] 이진 탐색 트리(Binary Search Tree) (0) | 2021.05.16 |
| [C++] 트리 순회(Tree Traversal) (0) | 2021.05.15 |
| [C] 해싱(Hashing) (0) | 2017.06.20 |
| [C] 그래프(Graph) (0) | 2017.06.19 |
| [C] 정렬(Sorting) (0) | 2017.06.18 |
| [C] 우선순위 큐(Priority Queue) (0) | 2017.06.17 |
