13 탐색 (C언어로 쉽게 풀어쓴 자료구조)

13.1 탐색이란?

탐색(search): 여러 개의 자료 중에서 원하는 자료를 찾는 작업

-탐색의 단위: 항목(숫자일 수도, 구조체일 수도)

• 키(key): 항목과 항목을 구별 = 탐색키(search key)

=>탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것

 

13.2 정렬되지 않은 배열에서의 탐색

순차 탐색

순차 탐색(sequential search): 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법

 

 

ex: 탐색값과 일치하는 항목을 찾을 때까지 리스트의 앞부터 순차탐색

 

개선된 순차 탐색

=>비교횟수를 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;
}

-리스트의 끝에 찾고자 하는 키 값을 저장

-반복문의 탈출 조건: 키 값을 찾을 때까지

-이 경우 i값이 리스트의 끝에 도달하였는지를 매번 비교하지 않아도 된다

이 경우 리스트에 키값이 없더라도 반복문 탈출 가능

 

 

순차탐색의 시간 복잡도=O(n)

탐색이 성공: 리스트에 있는 키의 위치에 따라 비교 횟수 결정

평균 비교 횟수=(n+1)/2

 

13.3 정렬된 배열에서의 탐색

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

이진 탐색(binary search): 배열의 중앙에 있는 값을 조사->찾고자 하는 항목이 왼쪽/오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다

-비교가 이루어질 때마다 탐색 범위가 급격하게 줄어든다

 

 

이진 탐색 구현(순환 호출 버전)

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;
}

-복잡도: O(log2(n))

 

정렬된 배열에서의 색인 순차 탐색

색인 순차 탐색(indexed sequential search): 인덱스(index)라고 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법

-성능은 인덱스 테이블의 크기에 좌우된다

-인덱스 테이블의 크기를 m, 주자료 리스트의 크기를 n이라고 하면 복잡도는 O(m+n/m)

 

 

보간 탐색

보간탐색(interpolation search): 탐색키가 존재할 위치를 예측하여 탐색하는 방법

-이진탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색

 

k=찾고자 하는 키값, low=탐색학 범위의 최소 인덱스 값, high=탐색학 범위의 최대 인덱스 값

-탐색 위치를 결정할 때 찾고자 하는 키 값이 있는 곳에 근접하게 되도록 가중치를 주는 것

 

-많은 데이터가 비교적 균등하게 분포되어 있을 경우 이진탐색보다 우수한 방법

-복잡도 O(log2(n))

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]) high=j-1;
        else low=j;
    }
    if (list[low] == key) return(low); //탐색 성공
    else return -1; //탐색 실패
}

 

 

13.4 이진 탐색 트리

이진탐색 vs 이진탐색트리

-이진 탐색은 자료들이 배열에 저장->삽입과 삭제가 힘들다

-이진 탐색트리는 비교적 빠른 시간 안에 삽입과 삭제가 가능하다

 

이진탐색트리의 복잡도

if 균형트리라면 O(log2(n))

균형트리가 아니라면 O(n)

 

 

13.5 AVL 트리

AVL 트리: 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브트리의 높이차가 1 이하인 이진 탐색 트리

-AVL 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다->균형 트리가 항상 보장

-O(log n)

-균형인수(balance factor)= (왼쪽 서브 트리의 높이) - (오른쪽 서브트리의 높이)

-모든 노드의 균형인수가 ±1 이하이면 AVL 트리이다

 

AVL 트리의 탐색 연산

-이진탐색트리와 동일

-O(log2(n))

 

AVL 트리의 삽입 연산

-삽입 시 균형인수가 ±2가 된 가장 가까운 조상노드의 서브트리들에 대하여 다시 균형을 잡아야 한다

-새로운 노드부터 균형인수가 ±2가 된 가장 가까운 조상 노드까지를 회전시키는 것

 

4가지의 경우

 

 

AVL 트리 예제

 

AVL 트리의 정의

-AVL 트리도 이진탐색트리의 일종이다

 

 

13.6 2-3 트리

2-3트리: 차수가 2또는 3인 노드를 가지는 트리

-삽입/삭제 알고리즘이 AVL 트리보다 간단하다

-하나의 노드가 두 개 또는 세 개의 자식 노드를 가진다

-2-노드: 차수가 2인 노드(일반 이진 탐색 트리처럼 하나의 데이터와 두 개의 자식노드를 가진다)

-3-노드: 차수가 3인 노드(두 개의 데이터와 3개의 자식노드를 가진다)

 

2-3 트리의 삽입 연산

-2개의 데이터값만을 저장할 수 있다(넘어서면 노드 분리!)

 

 

• 단말노드를 분리하는 경우

다시 부모 노드가 2노드일때 / 부모노드가 3-노드일 때로 나눠서 생각한다

 

<부모 노드가 2노드일 때>

부모가 2-노드일 때는 중간 값이 부모의 남은 한 자리로 들어가고, 나머지가 새로운 노드로 분리된다

 

 

<부모 노드가 3노드일 때>

이 경우 부모 노드가 다시 분리되어야 한다

 

• 비단말노드를 분리하는 경우

마찬가지로 중간값을 다시 부모노드로 올려보내고 작은 값과 큰 값을 별개의 노드로 분리한다

 

 

• 루트노드를 분리하는 경우

새로운 루트노드가 하나 생기면서 트리의 높이가 하나 증가하게 된다.

2-3트리에서 트리의 높이가 증가하게 되는 것은 오직 이 경우 뿐이다

 

 

13.7 2-3-4 트리

-하나의 노드가 4개의 자식까지 가질 수 있도록 2-3 트리를 확장한 것

-데이터 3개까지 가질 수 있다

 

2-3-4 트리의 삽입 연산

-장점: 루트에서 단말노드로 한번만 이동하면서 삽입/삭제가 가능하다

-2-3-4 트리에서는 삽입을 위하여 루트->단말노드로 내려가는 동안 4-노드를 만나면 무조건 분할시킨다

  -이렇게 하면 단말노드의 부모노드는 4-노드가 아니라는 것이 보장된다->후진이동을 막을 수 있다

• 4-노드가 루트인 경우

 

• 4-노드의 부모가 2-노드인 경우

 

• 4-노드의 부모가 3-노드인 경우