탐색(Search)

탐색은 원하는 키가 있는지 확인하고, 있으면 해당 값이나 위치를 찾는 작업이다. 정렬되지 않은 배열 한 번 검색에는 순차 탐색이 간단하다. 이미 정렬된 배열에 여러 번 질의하면 이진 탐색이 적합하다. 삽입·삭제와 범위 탐색도 함께 필요하면 탐색 트리를 고려한다. 각 방법의 전제 조건과 실패 반환값을 먼저 정해야 한다.

순차탐색(Sequential search = Linear Search)

데이터의 집합을 처음부터 마지막까지 순차적으로 찾고하는 데이터를 비교하여 탐색하는 방법
처음부터 끝가지 모든 요소를 검사

int sequential_search(const int data[], int length, int target) {
    for (int i = 0; i < length; i++) {
        if (target == data[i]) {
            return i;
        }
    }
    return -1;
}

배열 길이를 함께 받아 유효한 범위만 읽는다. 찾으면 인덱스, 없으면 유효 인덱스와 겹치지 않는 -1을 반환한다. 처음 값에서 찾으면 비교 1회, 없으면 length회이므로 최선 O(1), 최악 O(n)이다. 같은 값이 여러 개면 가장 앞의 인덱스를 반환한다.

자기구성 순차탐색

자주 찾는 항목, 자주사용하는 목록들을 다른 항목보다 우선하여 접근할 수 있게 가까이 배치하는 방법
- 전진이동법 (Move To Front) : 항목이 한번 탐색되고 나면 그 항목을 데이터 집합의 가장 앞에 위치시키는

Node* MoveTOFront(Node** head, int target) {
    Node* current = (*head);
    Node* previous = NULL;
    Node* match = NULL;

    while(current != NULL) {
      if (current->data == target) {
        match = current;
        if (previous != NULL) {
            previous->next = current->next;
            current->next = (*head);
            (*head) = current;
        }
        break;
      }
      else {
          previous = current;
          current = current->next;
      }
    }
    return match;
  }

전위법 (Transpose) : 탐색된 항목을 바로 이전 항목과 교환(같은 데이터가 자주 탐색될 수록 앞으로 이동)

Node* Transpose(Node** head, int target) {
    Node* current = (*head);
    Node* pprevious = NULL;
    Node* previous = NULL;
    Node* match = NULL;

    while(current != NULL) {
      if (current->data == target) {
        match = current;
        if (previous != NULL) {
          if (pprevious != NULL) {
            pprevious->next = current;
          }
          else {
            (*head) = current;
          }
          previous->next = current->next;
          current->next = previous;
        }
        break;
      }
      else {
        if (previous != NULL) {
          pprevious = previous;  
        }
        previous = current;
        current = current->next;
      }
    }
    return match;
  }

빈도계수법 (Frequency Count) : 데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해두고, 탐색된 횟수가 높은 순으로 데이터 집합을 재구성하는 알고리즘

자기 구성 리스트는 자주 찾는 항목이 앞에 오도록 탐색 후 순서를 바꾼다. A→B→C에서 C를 찾았을 때 전진 이동은 C→A→B, 전위법은 A→C→B가 된다. 반복해서 같은 키를 찾는 분포에서 평균 탐색 비용을 줄일 수 있지만 한 번의 최악 탐색은 여전히 O(n)이다. 원래 순서가 의미 있거나 동시에 순회 중이라면 순서를 바꾸는 방식은 부적합하다.

이진탐색(Binary Search)

탐색범위를 1/2씩 줄여나가는 알고리즘
1. 데이터의 집합의 중앙에 있는 요소를 선택
2. 중앙 요소 값과 찾고자 하는 목표 값을 비교
3. 목표값이 중앙 요소 값보다 작으면 중앙을 기준으로 왼편에 대해 새로 검색하고, 중앙 요소 값보다 크면 오른편에 대해 새로검색
4. 찾고자하는 값을 찾을 때 까지 1~3번 반복

public int binarySearch(int[] n, int target) {
		int left, right, mid;
		int length = n.length;

		left = 0;
		right = length-1;

		while(left <= right) {
			mid = left + (right - left) / 2;
			if (n[mid] == target) {
				return mid;
			}
			if (n[mid] > target) {
				right = mid - 1;
			}
			else if(n[mid] < target) {
				left = mid + 1;
			}
		}
		return -1;
	}

이 함수의 전제는 n이 오름차순으로 정렬되어 있다는 것이다. 탐색 구간 [left,right] 밖에는 목표값이 없다는 불변식을 유지한다. 예를 들어 [2,4,7,9,12]에서 9를 찾으면 처음 mid=2의 7과 비교해 왼쪽 0..2를 버리고, 다음 mid=3의 9를 찾는다. 매번 후보 수가 절반 이하로 줄어 최대 O(log n) 비교가 필요하며 추가 공간은 O(1)이다. 정렬되지 않은 배열에서는 이 판단 자체가 성립하지 않는다. 같은 값이 여러 개면 어떤 위치가 반환될지는 이 구현에서 보장하지 않는다.

이진 탐색 트리 (Binary Search Tree)

탐색 : 왼쪽 자식노드는 부모노드보다 작고, 오른쪽 자식노드는 부모노드보다 크다
노드 삽입
- 새 노드가 삽입될 곳은 이진 탐색을 통해 찾아내야 한다.
- 이진 탐색을 통해 새 노드가 놓일 곳을 찾아낸 후 그곳에 노드를 추가하면된다.

탐색 : 왼쪽 자식노드는 부모노드보다 작고, 오른쪽 자식노드는 부모노드보다 크다

BSTNode* BST_Search(BSTNode* tree, Element target) {
	      if (tree == NULL) {
	        return NULL;
	      }
	      if (tree->data == target) {
	        return tree;
	      } else if (tree->data > target) {
	        return BST_Search(tree->left, target);
	      } else {
	        return BST_Search(tree->right, target);
	      }
	    }

노드 삽입
- 새 노드가 삽입될 곳은 이진 탐색을 통해 찾아내야 한다.
- 이진 탐색을 통해 새 노드가 놓일 곳을 찾아낸 후 그곳에 노드를 추가하면된다.
아래 재귀 함수는 루트 포인터의 주소를 받아 빈 트리에도 첫 노드를 넣는다. 새 키가 작으면 왼쪽, 크면 오른쪽으로 내려간다는 BST 불변식을 유지한다. 같은 키는 이 예제에서 추가하지 않는다.
```
void BST_Insert(BSTNode** root, BSTNode* newNode) {
    if (*root == NULL) {
        *root = newNode;
        return;
    }
    if (newNode->data < (*root)->data) {
        BST_Insert(&(*root)->left, newNode);
    } else if (newNode->data > (*root)->data) {
        BST_Insert(&(*root)->right, newNode);
    }
}
```
반복 버전도 현재 노드가 NULL인 경우 루트에 넣은 직후 반환해야 한다. 기존 재귀 예제는 좌우 방향이 뒤집혔고, 동일한 이름의 함수를 두 번 정의해 C 컴파일 오류가 발생했다.
노드삭제
- Leaf 노드는 데이터를 찾고 NULL 초기화 시키면되지만 양쪽 자식노드를 가지고 있는경우는?
  1. 양쪽 자식노드를 모두 갖고 있는 경우
    - 삭제된 노드의 오른쪽 하위트리에서 가장 작은 값을 가진노드를 삭제된 위치에 옮겨 놓는다.
  2. 왼쪽/오른쪽 중 어느 한쪽 자식 노드만 갖고 있는 경우
    - 삭제된 노드의 부모노드가 자식 노드를 연결시키면 된다.

#include <stdlib.h>

/* 삭제 뒤의 새 서브트리 루트를 반환한다. target이 없으면 원래 루트를 반환한다. */
BSTNode* BST_Remove(BSTNode* root, Element target) {
    if (root == NULL) return NULL;
    if (target < root->data) {
        root->left = BST_Remove(root->left, target);
    } else if (target > root->data) {
        root->right = BST_Remove(root->right, target);
    } else {
        if (root->left == NULL) {
            BSTNode* next = root->right;
            free(root);
            return next;
        }
        if (root->right == NULL) {
            BSTNode* next = root->left;
            free(root);
            return next;
        }
        BSTNode* successor = root->right;
        while (successor->left != NULL) successor = successor->left;
        root->data = successor->data;
        root->right = BST_Remove(root->right, successor->data);
    }
    return root;
}

삭제 뒤에는 호출자가 반환된 루트로 자신의 자식 포인터를 바꾼다. 자식이 둘이라면 오른쪽 서브트리의 최솟값을 현재 노드에 복사하고, 그 최솟값 노드를 오른쪽 서브트리에서 삭제한다. 따라서 삭제 후에도 왼쪽 키는 작고 오른쪽 키는 크다. 실제 C 코드에서는 노드의 소유권과 해제 방식도 한 가지 규칙으로 관리해야 한다. 기존 코드는 루트를 삭제할 때 부모가 NULL인데 이를 역참조하고, 대입 연산을 조건식에 쓰는 등의 오류가 있었다.

이진 탐색 트리의 문제점

트리 높이 h만큼만 내려가므로 탐색·삽입·삭제는 O(h)다. 균형이 잡히면 h=O(log n)이지만, 1,2,3,4를 차례로 넣은 일반 BST는 오른쪽으로만 이어져 h=n-1이고 최악 O(n)이 된다. 검색만 자주 한다면 정렬 배열의 이진 탐색이 단순할 수 있다. 삽입·삭제가 함께 많고 정렬 순서가 필요하면 균형 트리를 고려한다.

Red Black Tree(레드 블랙 트리)

이진탐색의 균형을 잡아주는 트리
트리와 다른점은 노드를 빨간색 또는 검은색으로 표시한다.

Red Black Tree의 구조체

typedef int Element;

typedef struct _RBTNode {
    struct _RBTNode *left;
    struct _RBTNode *right;
    struct _RBTNode * parent;
    enum {RED, BLACK} Color;
    Element data;
}RBTNode;

균형유지 방법

모든 노드는 빨간색 아니면 검정색이다.
루트노드는 검정색이다.
모든 NIL 잎(자식이 없는 자리의 센티널)은 검정색이다. 실제 왼쪽 자식이 반드시 검정색인 것은 아니다.
빨간 노드의 자식들은 모두 검정색이다. 하지만 검정색 노드의 자식이 빨간색일 필요는 없다.
한 노드에서 그 아래의 모든 NIL 잎까지 가는 경로의 검정색 노드 수는 같다.

빨간 노드 뒤에는 빨간 자식이 올 수 없고, 각 경로의 검정색 노드 수가 같으므로 가장 긴 경로의 높이가 가장 짧은 경로의 두 배를 넘지 않는다. 이 제약으로 높이가 O(log n)에 묶인다. 회전은 지역적인 부모·자식 포인터를 바꾸면서 BST의 중위 순서를 보존한다. 색 변경과 회전은 삽입·삭제 후 위 규칙을 회복하는 수단이다.

기본연산

레드블랙 트리는 삽입이나 삭제를 할 경유 규칙이 무너진다.
무너진 규칙이 무너지면 레드블랙 트리가 아니다.
그래서 삽입과 삭제를 하고 후처리를 해주어야 함

1. 회전(Rotation)

부모-자식 노드의 위치를 서로 바꾸는 연산
좌회전(Left Rotation)과 우회전(Right Rotation)로 나눈다.
- 우회전(Right Rotation) : 왼쪽 자식과 부모의 위치를 교환하는 것
  - 왼쪽 자식노드의 오른쪽 자식노드를 부모노드의 왼쪽 자식노드로 연결
- 좌회전(Left Rotation) : 오른쪽 자식과 부모의 위치를 교환하는 것
  - 오른쪽 자식 노드의 왼쪽 자식노드를 부모 노드의 오른쪽 자식으로 연결

void RBT_RouteRight(RBTNode** root, RBTNode* parent) {
    RBTNode* leftChild = parent->left;
    parent->left = leftChild->right;
    if (leftChild->right != NULL) {
      leftChild->right->parent = parent;
    }
    leftChild->parent = parent->parent;

    if (parent->parent == NULL) {
      (*root) = leftChild;
    }
    else {
      if (parent == parent->parent->left) {
        parent->parent->left = leftChild;
      }
      else {
        parent->parent->right = leftChild;
      }
    }
    leftChild->right = parent;
    parent->parent = leftChild;
  }

이 회전 코드는 NULL을 빈 자식으로 쓰는 축약 예제다. 완전한 레드 블랙 트리 구현에서는 NIL 센티널, 색 변경, 삽입·삭제 후 복구 루틴까지 일관되게 구현해야 한다. 회전 함수 하나만 호출한다고 균형 조건이 자동으로 회복되지는 않는다.

알고리즘 Algorithm 탐색 Search 이진 탐색 Binary Search

같은 카테고리의 글

브루트포스(Brute Force)2026.08.04 이전 16. 그래프 최단경로(다익스트라, 벨만-포드)2024.06.11 15. Spanning Tree2024.06.06

10. Divide and Conquer(분할정복)

Vue.js 정리

탐색(Search)

순차탐색(Sequential search = Linear Search)

자기구성 순차탐색

이진탐색(Binary Search)

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리의 문제점

Red Black Tree(레드 블랙 트리)

균형유지 방법

기본연산

1. 회전(Rotation)

같은 카테고리의 글

이어서 읽을 글

1. Algorithm 개요(Algorithm Overview)

브루트포스(Brute Force)

16. 그래프 최단경로(다익스트라, 벨만-포드)

15. Spanning Tree