알고리즘 6강 (탐색)

학습개요

1. 이번 강의를 포함해서 앞으로 두 번의 강의를 통해서, 주어진 저장 매체에서 원하는 데이터를 찾는 탐색 알고리즘에 대해서 살펴본다. 우선 이번 시간에는 순차 탐색과 이진 탐색과 같은 기본적인 탐색 방법을 비롯하여 이진 탐색 트리와 2-3-4 트리에 대해서 학습한다.

 학습목표

1. 순차 탐색의 개념, 성능, 특징을 이해하고 설명할 수 있다.
2. 이진 탐색의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
3. 이진 탐색 트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
4. 2-3-4 트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.

 주요용어

1. 순차 탐색(sequential search)
   - 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
2. 이진 탐색(binary search)
   - 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법
3. 이진 탐색 트리(binary search tree)
   - 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다는 조건을 만족시키는 이진 트리
4. 후속자(계승자) 노드(successor node)
   - 트리에서 어떤 노드의 바로 다음 키값을 갖는 노드
5. 2-3-4 트리
   - 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리
   - k-노드는 (k-1)개의 키와 k개의 자식으로 구성
6. 노드 분할(node split)
   - 2-3-4 트리에서 노드 분할이란 4-노드 하나를 2-노드 셋으로 분할한 후 가운데 2-노드를 부모 노드로 이동시키는 연산

정리하기

1. 1. 순차 탐색
     ⦁ 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
     ⦁ 성능 → O(n)
     ⦁ 모든 리스트 형태의 입력에 적용 가능 → 특히 비정렬 데이터 탐색에 적합
     ⦁ 데이터가 큰 경우에는 부적합
2. 2. 이진 탐색
     ⦁ 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법 → 분할정복 방법 적용
     ⦁ 성능 → 탐색 O(logn), 초기화 O(nlogn), 삽입/삭제 O(n)
     ⦁ 정렬된 리스트에 대해서만 적용 가능
     ⦁ 삽입/삭제 연산이 빈번한 응용에는 부적합 → 삽입/삭제 후 입력 리스트의 정렬 상태를 유지하기 위해서는 O(n)의 데이터 이동이 필요
3. 3. 이진 탐색 트리
     ⦁ 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다는 조건을 만족시키는 이진 트리
     ⦁ 탐색 연산 → 루트 노드로부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 진행
     ⦁ 삽입 연산 → 우선 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치의 자식 노드로서 새 노드를 추가
     ⦁ 삭제 연산 → 삭제되는 노드의 자식 노드의 개수에 따라 3가지 경우로 나누어 처리
     ① 자식 노드가 없는 경우 → 남는 노드가 없으므로 별도의 처리가 불필요
     ② 자식 노드가 하나인 경우 → 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올림
     ③ 자식 노드가 두 개인 경우 → 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고, 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리
     ⦁ 성능 → 평균 O(logn), 최악 O(n)
     ⦁ 삽입/삭제 시 기존 노드의 이동이 거의 발생하지 않음
     ⦁ 원소의 삽입/삭제가 진행됨에 따라 최악의 성능을 갖는 경사 트리 형태가 될 수 있음
4. 4. 2-3-4 트리
     ⦁ 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리
     - k-노드는 (k-1)개의 키와 k개의 자식을 가짐
     ⦁ 4-노드의 분할 → 삽입을 위한 탐색 과정에서 4-노드를 만나면 하나의 4-노드를 3개의 2-노드로 분할하고, 가운데 2-노드에 해당하는 키를 부모 노드로 이동시킴
     ⦁ 성능 → 탐색/삽입/삭제 O(logn)
     ⦁ 2-3-4 트리를 그대로 구현하면 노드의 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 많음