이진 탐색 (Binary Search)

선형 탐색

정리가 안된 책장에서 원하는 책을 찾는 방법에는 뭐가 있을까?

출처: 이선협 강사님 데브코스 강의 자료

순서대로 하나씩 찾는 탐색 알고리즘이다. O(n) 시간 복잡도가 걸린다.

이진 탐색

나이 맞추기 게임 : Up & Down으로 기준점을 정하여 찾는다.

출처: 이선협 강사님 데브코스 강의 자료

정렬되어 있는 요소들을 반씩 제외하면서 찾는 알고리즘이다. O(log n)만큼 시간복잡도가 걸린다.

이진 탐색의 특징

• 반드시 정렬이 되어있어야 사용 가능하다.
  => 정렬하는데 시간이 소요되므로 선형 탐색보다 오래 걸릴 수도 있다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(log n) 시간 복잡도인만큼 상당히 빠르다. 정렬이 되어 있다면 이진 탐색!

배열을 이용한 이진 탐색 구현

출처: 이선협 강사님 데브코스 강의 자료

1. mid 값과 목표값을 비교한다.
2. mid 값이 목표값보다 크면 right를 mid 값 바로 왼쪽에 위치시키고 mid 값을 새로 설정한다.
   또는 mid 값이 목표값보다 작으면 left를 mid 값 바로 오른쪽에 위치시키고 mid 값을 새로 설정한다.
3. 과정을 반복하여 mid값과 목표값이 같아질 떄까지 찾는다.

하지만 이 방법은 중간에 요소를 추가하거나 삭제하려고 할 경우 선형 시간 복잡도가 소요되는 단점이 존재한다.
이를 해결하기 위해 이진 탐색 트리를 활용한다.

이진 탐색 트리

이진 탐색을 위한 이진 트리로써 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

출처: 이선협 강사님 데브코스 강의 자료

이진 탐색 트리 요소 추가

루트에서부터 비교 노드보다 작으면 왼쪽 서브 트리로 크면 오른쪽 서브 트리로 추가해나간다. 값이 같을 경우에는 임의로 왼쪽, 오른쪽 중 하나를 정해서 추가한다.

이진 탐색 트리 요소 삭제

• 단말 정점을 삭제하는 경우 (리프 노드 삭제)

  별다른 처리 없이 부모 정점과의 연결을 끊는다.
  

  출처: 이선협 강사님 데브코스 강의 자료

• 하나의 서브 트리를 가지는 경우

  제거되는 정점의 부모 간선을 자식 정점을 가르키게 바꾼다.
  

  출처: 이선협 강사님 데브코스 강의 자료

• 두 개의 서브 트리를 가지는 경우

  왼쪽 서브 트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 된다.
  이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체된다.
  

  출처: 이선협 강사님 데브코스 강의 자료

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
  => 이 경우에는 순차 탐색과 동일한 시간복잡도를 가지게 된다.
• 이를 해결하기 위해 AVL 트리, 레드-블랙 트리와 같은 자료구조를 사용한다.

JavaScript에서 이진트리 구현

Array

const array = [1, 2, 5, 6, 39, 414, 1515];

function binarySearch(array, findValue) {
  // left, right, mid 생성
  let left = 0;
  let right = array.length - 1;
  let mid = Math.floor((left + right) / 2);
  // 이진 탐색 시작 (left가 right랑 같거나 클때까지)
  while (left <= right) {
    // mid 값과 같으면 종료
    if (array[mid] === findValue) {
      return mid;
    }
    // mid 값이 목표값보다 작으면
    if (array[mid] < findValue) {
      left = mid + 1; // left를 mid 바로 오른쪽으로 이동
    } else {
      // mid 값이 목표값보다 크면
      right = mid - 1;
    }
    // mid 재설정
    mid = Math.floor((left + right) / 2);
  }

  return -1; // 찾지 못하면 -1
}

console.log(binarySearch(array, 414));
console.log(binarySearch(array, 1));
console.log(binarySearch(array, 7));

Binary Search Tree

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  // 추가 : 노드 생성 및 루트가 비었으면 추가한 노드가 루트가 됨
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return;
    }

    let currentNode = this.root;
    while (currentNode !== null) {
      // 추가할 값이 현재 노드의 값보다 크면
      // 오른쪽 노드의 값보다 추가할 노드의 값이 더 크면
      if (currentNode.value < value) {
        // 오른쪽 노드의 값이 null이면
        if (currentNode.right === null) {
          currentNode.right = newNode; // 바로 삽입
          break;
        }
        // 아니면 그대로 이동
        currentNode = currentNode.right;
      } else {
        // 추가할 값이 현재 노드의 값보다 작으면
        // 왼쪽 노드의 값보다 추가할 노드의 값이 더 크면
        // 왼쪽 노드의 값이 null이면
        if (currentNode.left === null) {
          currentNode.left = newNode; // 바로 삽입
          break;
        }
        currentNode = currentNode.left; // 그대로 이동
      }
    }
  }
  // 찾기
  has(value) {
    let currentNode = this.root;
    while (currentNode !== null) {
      if (currentNode.value === value) {
        return true;
      }

      if (currentNode.value < value) {
        currentNode = currentNode.right;
      } else {
        currentNode = currentNode.left;
      }
    }

    return false;
  }
}

const tree = new BinarySearchTree();
tree.insert(5);
tree.insert(4);
tree.insert(7);
tree.insert(8);
tree.insert(5);
tree.insert(6);
tree.insert(2);
console.log(tree.has(8));
console.log(tree.has(1));

과제

• 이진 탐색 트리의 요소 제거 부분을 작성해보자.

---

😅 해당 내용은 공부하면서 정리한 글입니다. 틀린 부분이나 오해하고 있는 부분이 있다면 피드백 부탁드립니다.