[알고리즘 스터디 with 케이시] 이진 탐색

이진탐색

책장에서 원하는 책을 찾는다면?

• 하나씩 찾으면 선형탐색

나이를 업다운 해서 맞춘다면?

• 정렬된 숫자가 있으므로, 이진 탐색으로 탐색 가능

특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진트리를 이용하여 구현할 수 있다.
• O(log n) 시간 복잡도인 만큼 상당히 빠르다.

배열을 이용한 구현 방법

여기서 숫자 45를 찾는다면?

1. 배열의 시작점을 left, 중간을 mid, 끝을 right라고 놓습니다.
2. mid(58) 보다 찾으려는 값이 작으므로, right를 미드보다 한 칸 작게 둡니다. right = mid - 1
3. 후에 다시 mid를 계산합니다.
4. 이제 찾으려는 값 45가 미드인 36보다 크기 때문에 left를 mid 보다 한칸 위로 둡니다. left = mid + 1
5. 다시 미드를 계산합니다.
6. left, right 의 값이 같기 때문에 미드의 값도 같이 45로 됩니다.
7. 찾을 값과 미드가 같기 때문에 탐색을 종료합니다.

이진 탐색 트리를 이용한 구현 방법

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

이진 탐색 트리에서 요소 추가

1. 5 추가 - 루트
2. 4 추가 - 왼쪽 서브 트리에 추가
3. 7 추가 - 오른쪽 서브 트리에 추가
4. 8 추가 - 오른쪽 서브 트리에 넣고, 7보다 크기 때문에 7의 오른쪽에 추가
5. 5 추가 - 동일하므로, 오른쪽 왼쪽 둘중에 아무대나 넣어도 되지만, 이번에 왼쪽에 추가, 후 4보다 크므로, 4의 오른쪽에 추가
6. 2를 추가 - 5보다 작으므로 왼쪽 트리에 추가, 4보다 작기 때문에 왼쪽 트리에 추가

이진 탐색 트리에서 요소 삭제

• 리프 정점을 삭제하는 경우
  • 별 다른 처리 없이 부모 정점과의 연결을 끊는다.
• 서브트리를 하나 가지는 경우
  • 7을 삭제한다고 하면, 5의 오른쪽 자식 노드를 8로 한다.
• 해당 노드가 두 개의 서브트리를 가지는 경우
  • 왼쪽 서브트리의 가장 큰 값 혹은 오른쪽 서브트리의 가장 작은 값과 교체하면 된다.
  • 이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체 된다.

이진 탐색 트리의 문제점

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