[Algorithm] 탐색 알고리즘(search algorithm)

---

순차탐색 (Sequential Search)

 

이름 그대로 순차적으로 탐색하는 알고리즘이다. 정렬되지 않은 상태에서는 순차탐색이 유일한 방법일 때가 많다.

int sequential_search(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

연결리스트라면 다음과 같을 것이다.

struct node sequential_search(struct node head, int key) {
    for (struct node* t = head->link; t != NULL; t = t->link) {
        if (t->key == key) {
            return t;
        }
    }
    return NULL;
}

• 평균적인 경우 시간복잡도: $ O(n)$
• 최악의 경우 시간복잡도: $ O(n) $

 

---

이진탐색 (Binary Search)

 

주어진 선형 리스트가 연속 공간에 저장되어 있고, 데이터 레코드들이 키 값에 대해서 미리 정렬되어 있는 경우 사용 가능한 탐색이다. 이진탐색은 중앙값을 탐색값과 비교하고, 중앙값이 더 크면 중앙값보다 작은 서브 리스트를, 더 작으면 중앙값보다 더 큰 서브 리스트를 탐색하는 방법으로 범위를 좁혀나가며 탐색을 효율적으로 수행한다.

int binary_search(int arr[], int n, int key) {
    int low = 1, high = n, mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        else if (arr[mid] > key) {
            high = mid - 1;
        }
        else if (arr[mid] < key) {
            low = mid + 1;
        }
    }
    return -1;
}

• 평균적인 경우 시간복잡도: $ O(\log n) $
• 최악의 경우 시간복잡도: $ O(\log n) $

단 탐색 성능은 우수하지만, 삽입/삭제에서는 정렬을 유지하기 위해 많은 비용이 발생하므로 적절하지 않다.

 

---

이진탐색트리 (Binary Search Tree)

 

배열에서 특정 값을 탐색할 때는 이진탐색을 이용해 빠른 탐색이 가능하다. 그러나 문제는 배열에서는 삽입, 삭제가 유연하지 못하기에 삽입/삭제가 빈번히 일어나는 경우 배열에 활용되는 이진탐색을 사용하기 부적절할 수 있다.

탐색, 삽입, 삭제 모두 유연하고, 빠르게 하기 위해 트리를 변형하여 이진탐색과 유사한 탐색이 가능하도록 만든 것이 이진탐색트리이다. 이진트리이기에 노드의 좌우측으로 자식노드가 있는데, 왼쪽 노드의 키값은 자신의 키값보다 작은 값, 오른쪽 노드의 키값은 자신의 키값보다 큰 값이 오도록 하여 탐색을 돕는다.

기본적으로 탐색은 이진탐색과 비슷하게 노드의 키값이 찾고자 하는 값보다 크면 왼쪽, 작으면 오른쪽 자식 노드로 이동하여 다시 노드의 키값과 비교하며 탐색한다.

삽입은 탐색과 똑같이 위치를 찾고, 삽입하면 된다.

삭제가 까다로운데 경우의 수를 나눠 확인한다. 이진탐색트리의 형태를 유지할 수만 있다면 삭제가 어떻게 이루어지느냐가 중요하지는 않아서 여러 방법이 있지만, 아래 코드에서는 오른쪽 자식이 없는 경우, 오른쪽 자식은 있지만 오른쪽 자식의 왼쪽 자식은 없는 경우, 둘 다 아닌 경우로 나눠 처리하였다. 오른쪽 자식이 없으면 간단하게 부모 노드가 왼쪽 자식을 가리키게 하고, 오른쪽 자식은 있지만 오른쪽 자식의 왼쪽 자식이 없다면 부모 노드가 오른쪽 자식을 가리키고, 오른쪼고 자식이 왼쪽 자식을 가리키게 만들었다. 가장 까다로운 둘 다 아닌 경우에는 오른쪽 자식의 가장 왼쪽 자식, 즉 오른쪽 서브트리의 가장 작은 키값을 가지는 노드를 찾아 삭제 노드를 대체하도록 하였다.

class Node{
public:
    Node* left;
    Node* right;
    int key;
    Node(int key = 0) {
        this->left = NULL;
        this->right = NULL;
        this->key = key;
    }
};

class BinarySearchTree{
private:
    Node* root;
public:
    BinarySearchTree() {
        this->root = NULL;
    }
    Node* search(int key) {
        Node* current = root;
        while (current != NULL) {
            if (key == current->key) {
                break;
            }
            else if (key < current->key) {
                current = current->left;
            }
            else if (key > current->key) {
                current = current->right;
            }
        }
        return current;
    }
    void insert(int key) {
        Node* parent = NULL;
        Node* current = root;
        if (root == NULL) {
            root = new Node(key);
            return;
        }
        while (current != NULL) {
            parent = current;
            if (key == current->key) {
                return;
            }
            else if (key < current->key) {
                current = current->left;
            }
            else if (key > current->key) {
                current = current->right;
            }
        }
        current = new Node(key);
        if (key < parent->key) {
            parent->left = current;
        }
        else if (key > parent->key) {
            parent->right = current;
        }
    }
    void remove(int key) {
        Node* parent = NULL;
        Node* target = root;
        Node* min_parent = NULL;
        Node* replacement = NULL;
        if (root == NULL) {
            return;
        }
        while (target != NULL && target->key != key) {
            parent = target;
            if (key < target->key) {
                target = target->left;
            }
            else {
                target = target->right;
            }
        }
        if (target == NULL) {
            return;
        }
        if (target->right == NULL) {
            replacement = target->left;
        }
        else if (target->right->left == NULL) {
            replacement = target->right;
            replacement->left = target->left;
        }
        else {
            min_parent = target->right;
            while (min_parent->left->left != NULL) {
                min_parent = min_parent->left;
            }
            replacement = min_parent->left;
            min_parent->left = replacement->right;
            replacement->left = target->left;
            replacement->right = target->right;
        }
        if (parent == NULL) {
            root = replacement;
        }
        else if (target == parent->left) {
            parent->left = replacement;
        }
        else {
            parent->right = replacement;
        }
        delete target;
    }  
};

탐색에 대한 시간복잡도는 아래와 같다.

• 평균적인 경우 시간복잡도: $ O(\log n) $
• 최악의 경우 시간복잡도: $ O(n) $

최악의 경우는 완전 불균형한 경사트리(skewed tree)가 만들어지는 경우로 정렬된 수가 차례대로 삽입되는 경우 만들어진다. 따라서 탐색 성능을 유지하기 위해서는 트리를 균형트리로 유지시킬 필요가 있다.

 

---

2-3-4 트리 (2-3-4 Tree)

 

2-3-4 트리는 노드 안에 1개, 2개, 3개의 값을 저장할 수 있으며, 각각 2개, 3개, 4개의 자식을 가질 수 있는 트리이다. 이진 트리는 모든 노드가 하나의 값만 저장하고 최대 2개의 자식을 가지지만, 2-3-4 트리는 한 노드에 여러 값을 저장하고 더 많은 자식을 가질 수 있다는 점에서 차이가 있다.

탐색은 이진 트리와 비슷하게, 노드 내부의 값들과 비교하여 값이 작으면 왼쪽으로, 크면 오른쪽으로 이동하면서 진행된다.

삽입과 삭제 시, 노드에 값이 많아지거나 자식이 많아질 경우, 노드를 분할하거나 병합하여 트리의 균형을 유지한다. 이를 통해 2-3-4 트리는 항상 균형 잡힌 상태를 유지한다.

• 시간복잡도: $ O(\log n) $

균형트리이기에 일반적인 이진탐색트리보다 안정적인 성능을 유지한다. 그러나 구현이 복잡하고, 제약이 많으며, 키값을 비교하는 과정이 이진탐색트리보다 까다롭기 때문에 균형상태의 이진탐색트리와 비교하면 실제 성능이 더 떨어질 가능성이 높다.

 

---

레드블랙 트리 (Red-Black Tree)

 

이진탐색트리를 기본으로 하면서 규칙을 추가하여 높이를 균형 있게 유지하는 트리이다.

• 시간복잡도: $ O(\log n) $