13.1 탐색이란?
여러 개의 자료 중에서 원하느 자료를 찾는 작업이다.
13.2 정렬되지 않은 배열에서의 탐색
순차탐색
- 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾는 방법
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 imporved_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; // 탐색 성공
}
리스트 마지막에 찾고자 하는 키 값을 넣는(보초 기법) 이유
보통 탐색 알고리즘에서는 찾으려는 값이 없을 경우 탐색 범위를 벗어나야 하는데, 첫 번째 코드처럼 if (list[i] == key)를 매번 검사하면 성능이 떨어진다.
하지만 high+1 위치에 key를 넣어두면,
- list[i] == key가 될 때까지 i를 증가시키면서 반복
- 만약 원래 리스트에 key가 있으면 정상적으로 인덱스를 반환
- 리스트에 key가 없으면 i가 high+1까지 증가하여 탐색 종료
성능 향상이 되는 이유?
- if 문이 루프 안에서 반복되지 않아 불필요한 조건 검사를 줄임
- 탐색할 원소가 많아질수록 첫 번째 코드보다 비교 연산을 덜 수행
- 보초(sentinel) 기법을 사용해 반복 횟수를 줄이고 코드가 더 간결해짐
13.3 정렬된 배열에서의 탐색
정렬된 배열에서의 이진 탐색
- 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.
순환호출로 구현한 이진 탐색
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; // 발견되지 않음
}
정렬된 배열에서의 색인 순차 탐색
- 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높임
- 인덱스 테이블에 m개의 항목
- 주자료 테이블의 데이터 수 n
- 각 인덱스 항목은 주 자료 리스트의 각 n/m번째 데이터를 가지고 있다.
- 인덱스 테이블을 조사하여 해당키의 구간을 설정한다
- key가 속한 범위를 찾으면 해당 범위에서만 탐색한다.
- 찾은 index_list[i]를 기반으로 low와 high를 설정
- 해당 범위에서 순차 탐색을 진행한다.
더보기
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);
}
보간탐색
- 탐색키가 존재할 위치를 예측하여 탐색하는 방법
- 이진탐색과 유사하나 리스트를 반으로 분할하지 않고, 불균등하게 분할하여 탐색한다.
- 보간탐색은 key값과 위치가 비례한다고 가정한다.
더보기
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); //found(r[low])
else return -1; // notfound(key)
}13.4 이진 탐색 트리
- 8장- Ⅱ 참고
2024.12.12 - [C언어로 쉽게 풀어쓴 자료구조] - [C언어로 쉽게 풀어쓴 자료구조] 8장 트리 - Ⅱ
13.5 AVL 트리
- 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리
- AVL 트리가 비균형 상태가 되면 스스로 노드를 재배치하여 균형 상태로 만든다.
- 균형인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이
비균형 트리에서 균형 트리로의 연산
- 균형인수 -1, 1에서 회전시킨다.
1. LL 타입
- 노드 Y의 왼쪽 자식의 자리에 노드가 추가됨
- 노드를 오른쪽으로 회전시킨다.
2. RR 타입
- 노드 Y의 오른쪽 자식의 자리에 노드가 추가됨
- 노드를 왼쪽으로 회전시킨다.
3. RL 타입
- 노드 Y의 왼쪽 자식 자리에 노드가 추가됨
- 노드를 오른쪽으로 한번, 왼쪽으로 한번 회전시킨다.
→ 책에 균형인자가 잘못 나왔네요. 한참 고민했네;
4. LR 타입
- 노드 Y의 왼쪽 자식의 자리에 노드가 추가됨
- 노드를 왼쪽으로 한번, 오른쪽으로 한번 회전시킨다.
→ 이것도 균형인자 오류
오른쪽 회전 함수
- 왼쪽으로 치우친 트리를 균형 잡기 위해 오른쪽으로 회전
- 부모(parent)의 왼쪽 자식(child)을 새로운 부모로 변경
- 새로운 부모의 오른쪽 서브트리를 원래 부모의 왼쪽 서브트리로 이동
AVLNode *rotate_right(AVLNode *parent) {
AVLNode* child = parent->left; // 부모의 왼쪽 자식을 가져옴
parent->left = child->right; // child의 오른쪽 서브트리를 parent의 왼쪽에 배치
child->right = parent; // 부모를 child의 오른쪽 자식으로 설정
return child; // 회전 후 새로운 루트 반환
}
전
10
/
5
/
2
후
5
/ \
2 10
- 5가 루트로 이동하고, 10은 5의 오른쪽 자식이 됨.
- 기존의 child->right였던 부분이 parent->left로 이동.
왼쪽 회전 함수
- 오른쪽으로 치우친 트리를 균형 잡기 위해 왼쪽으로 회전
- 부모(parent)의 오른쪽 자식(child)을 새로운 부모로 변경
- 새로운 부모의 왼쪽 서브트리를 원래 부모의 오른쪽 서브트리로 이동
AVLNode *rotate_left(AVLNode *parent) {
AVLNode *child = parent->right; // 부모의 오른쪽 자식을 가져옴
parent->right = child->left; // child의 왼쪽 서브트리를 parent의 오른쪽에 배치
child->left = parent; // 부모를 child의 왼쪽 자식으로 설정
return child; // 회전 후 새로운 루트 반환
}
전
5
\
10
\
15
후
10
/ \
5 15
- 10이 루트가 되고, 5는 10의 왼쪽 자식이 됨.
- 기존의 child->left였던 부분이 parent->right로 이동.
새로운 노드 추가 함수
// AVL 트리에 새로운 노드를 추가하는 함수
// 새로운 루트를 반환한다.
AVLNode* insert(AVLNode* node, int key)
{
// 1️⃣ 기본적인 BST(이진 탐색 트리) 삽입 수행
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;
// 2️⃣ 노드의 높이를 업데이트
node->height = 1 + ((get_height(node->left) > get_height(node->right)) ? get_height(node->left) : get_height(node->right));
// 3️⃣ 균형 인수(Balance Factor) 계산
int balance = get_balance(node);
// 4️⃣ 불균형 처리: LL, RR, LR, RL 케이스 확인
// LL (Left-Left) 불균형 → 오른쪽 회전 수행
if (balance > 1 && key < node->left->key)
return rotate_right(node);
// RR (Right-Right) 불균형 → 왼쪽 회전 수행
if (balance < -1 && key > node->right->key)
return rotate_left(node);
// LR (Left-Right) 불균형 → 왼쪽 회전 후 오른쪽 회전
if (balance > 1 && key > node->left->key)
{
node->left = rotate_left(node->left); // 왼쪽 서브트리를 왼쪽 회전
return rotate_right(node); // 부모 노드를 오른쪽 회전
}
// RL (Right-Left) 불균형 → 오른쪽 회전 후 왼쪽 회전
if (balance < -1 && key < node->right->key)
{
node->right = rotate_right(node->right); // 오른쪽 서브트리를 오른쪽 회전
return rotate_left(node); // 부모 노드를 왼쪽 회전
}
// 5️⃣ 균형을 유지한 상태에서 노드 반환
return node;
}13.6 2-3 트리
- 하나의 노드가 두 개 또는 세 개의 자식을 가진다.
- 이진 트리와 유사
- 2-노드:
- 차수가 2인 노드
- 데이터 한개와 두 개의 자식 노드를 가진다
- 3-노드:
- 차수가 3인 노드
- 2개의 데이터와 3개의 자식노드를 가진다.
2-3 트리의 탐색 연산
30탐색
- 2-노드의 50과 비교
- 30 < 50이므로 왼쪽 서브 트리로 간다.
- 3-노드의 10과 35와 비교
- 10 < 30 < 35이므로 중간 서브 트리로 간다.
- 30이 존재하면 탐색 성공
더보기
Tree23Node *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);
}
}
2-3 트리의 삽입 연산
- 데이터 추가시에 노드에 추가할 수 있을 때까지 데이터 추가
- 더 이상 공간이 없을시 노드를 분리
- 중간값을 위로 올리고 작은값을 왼쪽, 큰 값을 오른쪽 노드로 만든다.
데이터 삽입 시 노드가 분리되는 경우
- 단말 노드를 분리하는 경우
- 비단말 노드를 분리하는 경우
- 루트 노드를 분리하는 경우
단말 노드를 분리하는 경우
- 새로운 노드의 중간값은 부모노드로 올라간다.
- 작은값과 큰값은 새로운 노드로 분리
※ 만약 위 그림처럼 이미 2개의 데이터를 가지고 있는 3노드라면 부모노드가 다시 분리되어야 한다.
비단말 노드를 분리하는 경우
- 중간값을 부모 노드로 올려보냄
- 작은값과 큰값을 별개의 노드로 분리한다.
- 부모노드에 추가 노드를 받을 공간이 없다면 다시 분리
루트 노드를 분리하는 경우
- 루트 노드를 분리하게 되면 트리의 높이가 하나 증가하게 된다.
- 나머지 과정을 위와 동일
13.7 2-3-4 트리
- 하나의 노드가 4개의 자식까지 가질 수 있도록 2-3 트리를 확장
- 4-노드:
- 4개의 자식을 가질 수 있다.
- 3개의 데이터를 가질 수 있다.
'C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] 14장 해싱 (0) | 2025.03.14 |
|---|---|
| [C언어로 쉽게 풀어쓴 자료구조] 12장 정렬 (0) | 2025.01.31 |
| [C언어로 쉽게 풀어쓴 자료구조] 11장 그래프 Ⅱ (2) | 2025.01.30 |
| [C언어로 쉽게 풀어쓴 자료구조] 10장 그래프 Ⅰ (1) | 2025.01.14 |
| [C언어로 쉽게 풀어쓴 자료구조] 9장 우선순위 큐 (1) | 2025.01.02 |