[자료구조] 탐색

탐색 키: 항목과 항목을 구별해주는 키

---

Sequential Search (Linear Search, 순차 탐색)

정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사

 

Time Complexity: O(n)

 

비교 횟수

성공: (n+1)/2

실패: n

int seq_search(int key, iint low, int high){
    for(int i = low; i <= high; i++){
        if(list[i] == key)
            return i; //탐색 성공    
    }
    return -1; //탐색 실패        
}

 

개선된 순차 탐색 - 별로 개선 안 됨

리스트 끝에 탐색 키 저장

for문 안의 비교를 제거

int seq_search2(int key, int low, int high){
    list[high +1] = key;
    
    int i;
    for(i = low; list[i] != key; i++); //키 값을 찾을 때까지
    if(i == (high +1)) return -1; //탐색 실패
    else return i; //탐색 성공
}

---

Binary Search (이진 탐색)

정렬된 배열의 중앙에 있는 값 조사 후 범위를 반으로 줄여나감

삽입 / 삭제 비효율적

 

Time Complexity: O(logn)

int search_binaary(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_binary(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; //탐색 실패
}

반복

Indexed Sequential Search (색인 순차 탐색)

index table 사용 (주 자료에서 일정 간격으로 발췌)

index table을 먼저 탐색하여 key가 있을 범위를 알아낸 후 그 범위에 대해서만 순차 탐색 

 

Time Complexity: O(m + g)

m: index table의 크기

g: 일정한 간격(gap)

g = n/m

---

이진탐색트리 (BST - Binary Search Tree) 

https://shinyunha.tistory.com/13 여기서 가져옴 

 

중위순회하면 오름차순 정렬

key(왼쪽 sub 트리) < key(루트 노드) < key(오른쪽 sub 트리)

삽입 / 삭제 빠름 

 

Time Complexity: 트리의 높이 h

균형: O(logn)

불균형: O(n) - 순차탐색과 동일

TreeNode* search(TreeNode* node, int key){
    if(node == NULL) return NULL;
    
    if(key == node->key) return node;
    else{
        if(key < node->key)
            return search(node->left, key);
        else
            return search(node->right, key);
    }
}

순환탐색

TreeNode* search(TreeNode* node, int key){
    while(node != NULL){
        if(key == node->key) return node;
        else{
            if(key < node->key)
                node = node->left;
            else
                node = node->right;
        }
    }
    
    return NULL; //실패했을 때 
}

반복탐색

---

AVL 트리

Adelson-Velskii와 Landis가 제안

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리

스스로 노드들을 재배치하여 균형 상태 유지 

 

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

각 노드들이 자신의 balance factor를 저장, 모두 0/1면 AVL 

 

Time Complexity: O(logn)

 

항상 leaf node에 삽입

삽입할 때 불균형이 되면 삽입 노드부터 균형 인수가 2가 된 가장 가까운 조상 노드까지 회전

돌린다고 복잡하게 생각하지 말고 그냥 규칙 만족하게 배치하자

---

보간 탐색 (Interpolation Search)

탐색키가 존재할 위치를 예측하여 탐색

이진 탐색과 유사하나 불균등 분할

 

Time Complexity: O(logn)

 

value의 비와, index의 비가 같다는 점 이용

int interpol_search(int key, int n){
    int low = 0;
    int high = n - 1;
    int j; 
    
    while(low <= high){
        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 return j; //탐색 성공
    }
    return -1; //탐색 실패 
}