이진 탐색 (Binary Search)

Binary Search

이진 탐색(Binary Search)은 정렬된 데이터 집합 안에서 사용할 수 있는 매우 빠른 탐색 알고리즘입니다. 이진 탐색이라는 이름은 찾고자 하는 요소를 찾지 못했을 때, 탐색 범위를 1/2로 좁혀 나가기 때문에 지어진 이름입니다. 성능이 매우 뛰어나면서도 구현이 간단하기 때문에, 기본 알고리즘부터 소개합니다.

const search = (arr, left, right, target) => {
  if (left >= right) {
    return -1;
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) return mid;
  else if (arr[mid] < target) return search(arr, mid + 1, right, n);
  else if (arr[mid] > target) return search(arr, left, mid - 1, n);
};

const arr = [1, 7, 11, 12, 14, 23, 67, 139, 871];
console.log(search(arr, 0, arr.length - 1, 161));

이진 탐색은 가장 먼저 데이터 집합의 가운데 값을 찾고자 하는 값인 target과 비교합니다. 만약 타겟보다 작으면 left의 값을 mid+1로, 반대로 타겟보다 크면 right의 값을 mid-1로 인자로 하여 함수를 재귀적으로 호출합니다. 이렇게 범위를 좁혀 나가는 식으로 타겟을 찾을 때까지 반복합니다.

본문 예제는 재귀 함수로 구현했지만, 반복문으로 구현하면 더 빠른 성능을 기대할 수 있습니다.

Binary Search Tree

이진 탐색 트리(Binary Search Tree, 일명 BST)는 이진 탐색을 위한 트리입니다. 이 트리는 일반적인 이진 트리와 다르게 새로 추가하고자 하는 노드가 루트보다 작다면 왼쪽 자식으로, 크다면 오른쪽 자식으로 연결한다는 규칙이 있습니다. 그렇기 때문에 방금 전에 알아 본 이진 탐색의 원리를 그대로 활용할 수 있습니다.

이진 탐색 트리에서 노드를 찾거나 추가하는 기능은 구현하기 쉽지만, 발견한 타겟을 제거하는 기능까지 구현 할 때는 노드를 제거 후 이진 탐색 트리를 재구성해야 하므로 몇 가지 추가 작업이 필요합니다.

노드 생성

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

이진 트리를 구성할 때와 마찬가지로 각 노드는 left와 right를 가집니다.

노드 탐색

const search = (tree, target) => {
  if (tree === null) return null;

  if (tree.data === target) return tree;
  else if (tree.data < target) return search(tree.right, target);
  else if (tree.data > target) return search(tree.left, target);
};

찾고자 하는 값(target)이 현재 참조 중인 트리의 값보다 작다면 왼쪽으로, 크다면 오른쪽으로 내려가 탐색합니다.

노드 추가

const insert = (tree, child) => {
  if (tree.data < child.data) {
    if (tree.right === null) tree.right = child;
    else insert(tree.right, child);
  } else if (tree.data > child.data) {
    if (tree.left === null) tree.left = child;
    else insert(tree.left, child);
  }
};

노드를 추가하는 기능은 탐색과 동일한 방식으로 동작하기에 크게 어려운 부분은 없습니다. 만약 추가하고자 하는 노드가 현재 참조 중인 트리의 값보다 작다면, 트리의 왼쪽 자식으로 들어가야 합니다. 왼쪽 자식이 비어 있다면 그대로 연결하면 되고, 비어있지 않다면 한 번 더 내려가 빈 자리를 찾습니다.

노드 제거

const searchMinNode = (tree) => {
  if (tree === null) return null;

  if (tree.left === null) return tree;
  else return searchMinNode(tree.left);
};

const remove = (tree, parent, target) => {
  if (tree === null) return null;

  let removed = null;

  if (tree.data > target) removed = remove(tree.left, tree, target);
  else if (tree.data < target) removed = remove(tree.right, tree, target);
  else {
    removed = tree;

    if (tree.left === null && tree.right === null) {
      // 잎 노드인 경우 바로 제거
      if (parent.left === tree) parent.left = null;
      else parent.right = null;
    } else {
      if (tree.left !== null && tree.right !== null) {
        // 자식이 양쪽 모두 있는 경우
        let minNode = searchMinNode(tree.right);
        minNode = remove(tree, null, minNode.data);
        tree.data = minNode.data;
      } else {
        // 자식이 한 쪽만 있는 경우
        let temp;
        if (tree.left !== null) temp = tree.left;
        else temp = tree.right;

        if (parent.left === tree) parent.left = temp;
        else parent.right = temp;
      }
    }
  }

  return removed;
};

target과 일치하는 노드를 제거하는 작업은 이진 탐색 트리를 다시 구성해야 하기 때문에 추가 작업이 필요합니다. 만약 제거하고자 하는 노드가 자식이 없거나, 한 쪽만 있는 경우라면 간단하게 처리할 수 있지만, 둘 다 가지고 있는 경우에는 오른쪽 하위 트리에서 가장 작은 값을 가진 노드를 가져와 대체 해야 합니다. 그리고 가장 작은 값을 가진 노드도 어떻게 보면 트리 안에서 제거 되는 것이기 때문에, 이 노드에 대해서도 후처리를 잊지 않아야 합니다.

References 📝

본문의 내용은 GeeksforGeeks의 Binary Search 자료를 참고해 작성했습니다 ❤️