CS/Data Structure (2021-1)

[자료구조] C++로 쉽게 풀어쓴 자료구조 : 14장, 탐색

샤아이인 2022. 1. 15.

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 14장 탐색

탐색은 하나 이상의 field로 구성된 record의 집합에서 원하는 레코드를 찾아내는 작업이다.

보통 이런 레코드의 집합을 table이라고 부른다. 레코드들은 각각 고유한 키값을 갖는데, 이를 탐색키(search key) 라고 부른다.

자료 검색은 테이블에서 해당 탐색키를 찾는 것 이다.

C++로 쉽게 풀어쓴 자료구조 (14장, 탐색)

데이터: 키와 값을 가진 요소 (key, value)의 집합

연산:

- create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성.

- getKey(): 레코드의 키를 반환한다.

- getValue(): 레코드의 값을 반환한다.

- update(value): 레코드의 값을 value로 변경한다.

맵 (map)

맵은 탐색을 위한 자료구조이다. map은 자료와 키를 저장하고 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조를 말한다.

맵은 키를 가진 레코드(key record) 또는 엔트리(entry)라 불리는 키-값 쌍을 테이블에 저장한다. 각 키들은 유일하다.

맵은 키를 가진 레코드들의 집합이다.

데이터: 유일한 키를 가진 엔트리(키를 가진 레코드)의 집합

연산:

- create(): 공백 상태의 맵을 생성한다.

- search(key): 테이블에서 주어진 탐색키를 가진 레코드를 찾아 반환.

- insert(entry): 테이블에서 주어진 entry를 삽입.

- delete(key): 테이블에서 주어진 탐색 key를 가진 레코드를 찾아 삭제한다.

- count(): 테이블에서 모든 레코드의 수를 반환.

맵을 가장 효율적으로 구현할 수 있는 방법이 해싱이다. 해싱은 탐색키의 비교가 아닌 탐색키를 수식에 적용시켜 바로 레코드가 저장된 위치를 얻는다.

정렬된 배열에서의 이진 탐색

정렬된 배열의 탐색에서는 binary search가 적용될 수 있다. 매 단계에서 검색해야 할 리스트의 크기가 반으로 줄어든다.

이러한 이진탐색은 탐색하기 전에 반드시 배열이 정렬되어 있어야 한다. 따라서 이진 탐색은 데이터의 삽입이나 삭제가 빈번한 경우에는 적합하지 않다.

이진 탐색의 유사 코드로 확인해 보자.

search_binary(list, key, low, high)

    middle <- low에서 high 사이의 중간 위치
    if( key = list[middle] )
        return middle;
    else if ( key < list[middle] )
        return search_binary(list, key, low, middle-1);
    else if ( key > list[middle] )
        return search_binary(list, key, middle+1, high);
    return -1

탐색이 진행해가면서 문제의 크기가 반으로 줄어들고, 이것을 순환으로 구현하면 된다. 이때 종료조건은 어떻게 되야 할까?

탐색 범위가 1보다 작다면, 즉 탐색할 항목이 더이상 없으면 종료해야 한다.

int binarySearch(int list[], 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 binarySearch(list, key, low, middle - 1);
        else
            return binarySearch(list, key, middle+1, high);
    }
    return -1;
}

이진탐색의 시간 복잡도는 O(logN) 이다.

색인 순차 탐색 (indexed sequential search)

색인 순차 탐색 방법은 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다.

인덱스 테이블에는 주 자료 list에서 일정한 간격을 잡고 발췌한 자료를 갖고있다.

예를 들어 m개의 인덱스 항목이 있고, 주 자료 list에 자료의 수가 n개이면 각 인덱스 들은 n/m의 정보량을 갖고있다.

주 자료 리스트와 인덱스 테이블 모두 정렬되있어야 한다.

1) 우선 인덱스 테이블에서 index[i] <= key < index[i+1] 을 만족하는 항목을 찾는다.

2) 주 자료 테이블에서 해당 범위의 항목들에 대해서만 검사한다.

int indexedSearch(int list[], int nList, Index* tbl, int nTbl, int key)
{
    if (key < list[0] || key > list[nList - 1])
        return -1;
    for (int i = 0; i < nTbl - 1; i++) {
        if (tbl[i].key <= key && tbl[i + 1].key > key)
            return sequentialSearch(list, key, tbl[i].index, tbl[i + 1].index);
    }
    return sequentialSearch(list, key, tbl[nTbl - 1].index, nList);
}

보간 탐색 (interpolation search)

보간 탐색은 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다. 보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.

보간탐색은 식을 이용하여 탐색위치값을 얻는다. 또한 탐색 값과 위치는 비례한다는 가정에서 탐색위치를 결정할때 우리가 원하는 키 값 인근에서 탐색을 시작할 수 있도록 돕는다.

이진 탐색같은 경우 항상 중간을 기점으로 나누기 때문에 탐색위치가 중간으로 고정되있다.

하지만 보간 탐색을 이용하면 근접한 곳에서부터 탐색을 시작할 수 있다는 것 이다.

예를들어 사전에서 a로 시작하는 단어를 찾을때 사전으 중간부터 찾지는 않는다.

이와 비슷한 논리로 탐색대상의 인근위치부터 시작하는 것 이다.

위의 비례식을 탐색 위치에 대한 식으로 바꿔주면 다음과 같다.

계산 결과는 일반적으로 실수이며 정수로 변환해주어야 한다. 보통 소수점 이하를 버린다.

int interpolationSearch(int list[], int nList, int key)
{
    int low = 0;
    int high = nList - 1;
    while ((list[low] < key) && (key <= list[high])) {
        int j = static_cast<int>((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 return j; // 탐색 성공
    }
    return -1;
}

균형 이진 탐색 트리

맵을 이진 탐색 트리로 구현하면 O(logN) 시간 안에 삽입과 삭제가 가능하다. 따라서 삽입과 삭제가 빈번하다면 이진 탐색 트리를 사용해야한다.

이진 탐색 트리는 균형을 유지하는 것 이 무엇보다 중요하다. 균형이 깨져 경사진 트리가 생기면 탐색의 시간이 n 으로 높아진다.

따라서 이진 탐색 트리가 스스로 균형을 유지하도록 하는 방법에 대하여 살펴보자.

AVL 트리 (Adelson-Velskii, Landis)

각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리 를 말한다. AVL트리는 항상 균형 트리를 보장하기 때문에 O(logN)의 탐색 시간을 보장한다.

- 균형인수

균형 인수는 (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이) 로 정의된다. 모든 노드의 균형인수가 +1 or -1 이하이면 AVL트리이다.

새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 2가된 조상 노드를 A라고 하자.

- LL회전: A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.

- LR회전: A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다.

- RR회전: A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.

- RL회전: A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.

LL, RR 회전은 한번만 회전하는 단순 회전 이고, 두번의 회전이 필요한 LR, RL회전은 이중 회전이다.

rotate_LL(A)
    B <- A의 왼쪽 자식
    B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
    A를 B의 오른쪽 자식 노드로 만든다.

rotate_RR(A)
    B <- A의 왼쪽 자식
    B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.
    A를 B의 왼쪽 자식 노드로 만든다.

rotate_RL(A)
    B <- A의 오른쪽 자식
    rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
    rotate_RR(A)

rotate_LR(A)
    B <- A의 왼쪽 자식
    rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
    rotate_LL(A)

해싱 (hashing)

해싱은 키값을 비교하는 것이 아니라 탐색키에 산술적인 연산을 적용하여 항목이 저장되있는 index를 바로 계산하는 방식이다.

키값을 연산하여 직접 접근이 가능한 구조를 해시 테이블(hash table) 이라 하며, 해시 테이블을 이용한 탐색을 해싱(hashing)이라고 한다.

해싱을 이용하여 맵을 구현하면 탐색 연산의 이론적인 시간복잡도는 O(1)이다.

현실적으로 키값이 항상 숫자라는 보장이 없고, 또한 숫자일지라도 매우 큰 숫자이기 때문에 이를 직접 배열의 index로 사용할수는 없다.

따라서 각 탐색키를 작은 정수로 mapping 시키는 어떠 함수가 필요하다.

이를 해시 함수(hash function)이라고 한다.

해시 함수는 탐색키를 입력 받아 해시 주소(hash address)를 output으로 생성하는데, 삽입 삭제 탐색 연산은 모두 이 주소로 이루어진다.

버켓 하나당 각 레코드를 저장할 수 있는 여러 slot을 갖는다. 이는 여러 탐색키가 해시 함수에 적용된후 나온 값이 동일할수있기 때문이다. 이렇게 테이블의 버켓의 수가 제한적인경우 경우에 따라 서로 다른 키인 k1과 k2가 해시함수에 의해 같은 결과값이 나올수 있다.

이를 충동(collision)이라고 하고, 이러한 키 k1과 k2를 동의어(synonym)이라고 한다.

또한 버켓에 여러 개의 슬롯이 있다면 k1과 k2를 다른 슬롯에 저장하면된다.

하지만 충돌이 슬롯의 수보다 더 많이 발생한다면 overflow 현상이 발생한다.

- 해시 함수

좋은 해시 함수의 조건은 다음 3가지 이다.

1) 충돌이 적어야 한다.

2) 해시 함수 값이 해시 테이블의주소 영역 내에서 고르게 분포되어야 한다.

3) 계산이 빨라야 한다.

● 제산 함수

가장 일반적인 나머지 연산자 %(mod)를 사용하는 방식. 테이블의 크기가 M일때 탐색키 k에 대하여 해시 함수는 다음과 같다.

h(k) = k mod M

이때 M은 소수(prime number)를 선택한다.

● 폴딩 함수

탐색키가 해시 테이블의 크기보다 더 큰 정수일때 사용된다. 탐색키를 몇 개의 부분으로 나누어 이를 더하거나 비트별로 XOR같은 연산을 하는것이 보다 좋은데, 이를 폴딩(folding)이라고 한다. 예를 들어 32비트 키를 2개의 16비트로 나누어 XOR 연산을 하는 코드는 다음과 같다.

h(k) = (short)( key ^ (key>>16) )

탐색키를 나누고 더하는 방법에는 shift folding과 boundray folding이 대표적이다.

● 중간 제곱 함수

이 방식은 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다.

● 비트 추출 방법

해시 테이블의 크기가 M = 2^k 일때 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것 이다.

해싱의 오버플로우 처리 방법

1) 선형 조사법(linear probing): 충돌이 일어나면 해시 테이블의 다른 위치를 찾아 항목을 저장한다.

2) 체이닝(chaining): 해시 테이블의 하나의 위치가 여러개의 항목을 저장할 수 있도록 구조를 변경.

저작자표시

'CS > Data Structure (2021-1)' 카테고리의 다른 글

[자료구조] Binary Search 증명 (5)	2022.01.22
[자료구조] 수학적 귀납법 증명 (2)	2022.01.22
[자료구조] C++로 쉽게 풀어쓴 자료구조 : 13장, 정렬 (0)	2022.01.15
[자료구조] C++로 쉽게 풀어쓴 자료구조 : 12장, 가중치 그래프 (0)	2022.01.15
[자료구조] C++로 쉽게 풀어쓴 자료구조 : 11장, 그래프 (0)	2022.01.15