[자료구조] 13장 - 탐색

1. 탐색

여러 개의 자료 중에서 원하는 자료를 찾는 작업, 컴퓨터가 가장 많이 하는 작업 중 하나이기 때문에 탐색을 효율적으로 수행하는 것은 매우 중요하다.

탐색을 위한 자료구조 = 배열, 연결 리스트, 트리, 그래프
탐색키 = 항목과 항목을 구별해주는 키

2. 이진 탐색 (binary search)

정렬된 배열의 탐색에 적합한 탐색방법. 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. 이러면 매 단계 검색해야 할 리스트의 크기가 반으로 줄어든다.

장점: 고정된 데이터에 대한 탐색에 적합 (데이터의 크기가 크고)
단점: 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않다.

low = 0, high = N-1
탐색되어야 할 범위는 low에서 high

int count;

int iBinarySearch(int A[], int key)
{
    int low = 0, high = N - 1, middle;

    while (low <= high)
    {
        count++;

        middle = (low + high) / 2;

        if (A[middle] == key)
            return middle;
        else if (A[middle] > key)
            high = middle - 1;
        else
            low = middle + 1;
    }

    return -1;
}

int rBinarySearch(int A[], int key, int low, int high)
{
    int middle

        if (low <= high)
    {
        count++;

        middle = (low + high) / 2;

        if (A[middle] == key)
            return middle;
        else if (A[middle] > key)
            rBinarySearch(A, key, low, middle - 1);
        else
            rBinarySearch(A, key, middle + 1, high);
    }

    return -1;
}

int main()
{
    int A[N];
    srand(time(NULL));

    for (int i = 0; i < N; i++)
        A[i] = rand() % 100;

    insertionSort(A);

    int key, idx;
    printf("Search key: ");
    scanf("%d", &key);

    // idx = iBinarySearch(A, key);
    idx = rBinarySearch(A, key, 0, N - 1);

    if (idx == -1)
        printf("No");
    else
        printf("%d Times : %d in A[%d]\n", count, key, idx);
}

📕 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다. 더이상 줄일 수 없는 1이 될때의 탐색 횟수를 k라 하자.

k=log2n, O(log2n)

3. 이진 탐색 트리 (Binary Search Tree)

이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 이한 탐색구조이다. 하지만 이진 탐색은 자료들이 배열에 저장되어 있어 삽입과 삭제가 힘들지만 BST는 빠르게 삽입 삭제를 수행할 수 있다.

이진 탐색 트리가 경사 트리가 되면 탐색 시간은 순차 탐색과 같게되어 효율이 떨어진다. 따라서 이진탐색트리는 균형을 유지하는 것이 무엇보다 중요하다.

4. AVL트리

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1 이하인 이진 탐색트리. 트리가 비균형상태로 되면 스스로 노드들을 재배치하여 균형 상태를 유지한다.

(1) 탐색 연산 = 일반적인 BST와 동일 O(log2n)

(2) 삽입 연산 = 균형이 깨지게 되는 연산

LL, LR 연산 -> 균형인수가 1 초과
RL, RR 연산 -> 균형 인수가 -1 미만

각 연산은 삽입된 위치만 보지 말고, 균형 인수가 깨진 지점에서 삽입된 위치를 보고 판단하기!

TreeNode* rotateRight(TreeNode* p) //c<p
{
   TreeNode* c = p->left; //중앙 값
   p->left = c->right; //swap 이라 생각하기
   c->right = p;

   return c;
}

TreeNode* rotateLeft(TreeNode* p) //p<c
{
   TreeNode* c = p->right; //중앙 값
   p->right = c->left; //swap 이라 생각하기
   c->left = p;

   return c;
}

• 균형인수 getBalance

  왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이

int getBalance(TreeNode* root)
{
    if (root == NULL)
        return 0;

    return getHeight(root->left) - getHeight(root->right);
}





TreeNode* insertNode(TreeNode* root, element key)
{
    if (root == NULL)
        return makeNode(key);

    if (key < root->key)
        root->left = insertNode(root->left, key);

    else if (key > root->key)
        root->right = insertNode(root->right, key);

    int balance = getBalance(root);

    if (balance > 1 && key < root->left->key) // LL
        return rotateRight(root); //균형인수가 깨진 노드를 전달, 돌아갈 노드를 줘야함

    if (balance > 1 && key > root->left->key) //LR
    {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }

    if (balance < -1 && key > root->right->key) //RR
        return rotateLeft(root);

    if (balance < -1 && key < root->right->key) //RL
    {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;

}