Binary Search(이진 탐색)

선형 탐색

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

이진 탐색

• 정렬이 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
• $O(logN)$ 시간 복잡도가 걸린다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.

이진 탐색 트리

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

이진 탐색 트리 요소 삭제

• 단말 정점을 삭제하는 경우
  • 별다른 처리 없이 부모 정점과 연결을 끊는다.
• 하나의 서브 트리를 가지는 경우
  • 제거되는 정점의 부모 간선을 자식 정점을 가르키게 바꾸면 된다.
• 두개의 서브 트리를 가지는 경우
  • "왼쪽 서브트리의 가장 큰 값" 혹은 "오른쪽 서브 트리의 가장 작은 값"과 교체한다.
  • 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체된다.

이진 탐색 트리 문제점

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