자료 구조 - 탐색

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

탐색

탐색(search)은 하나 이상의 필드(field)로 구성되는 레코드(record)의 집합에서 원하는 레코드를 찾아내는 작업이다.
레코드들의 집합을 테이블(table)이라고 한다.
레코드들은 서로 중복되지 않고 고유한 값을 갖는 키를 가지는데, 이것을 탐색키(search key)라고 한다.
결국 자료를 검색하는 것은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 것이다.

맵이란?

맵(map) 또는 사전(dictionary)은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조를 말한다.
맵은 키를 가진 레코드(keyed record) 또는 엔트리(entry)라고 불리는 키-값 쌍(key, value)을 테이블에 저장한다.

keyed record 의 추상 자료형

데이터: key와 value를 가진 요소 (key, value)의 집합
연산 :
 - create(key, value)
 - getKey()
 - getValue()
 - update(value) : 레코드의 값을 value로 변경한다.

map의 추상 자료형

데이터: 유일한 키를 가진 엔트리(키를 가진 레코드)의 집합
연산 :
 - create(): 공백 상태의 맵을 생성
 - search(key) : 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 반환함
 - insert(entry) : 테이블에 주어진 entry를 삽입함
 - delete(key) : 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 삭제함
 - count() : 테이블의 모든 레코드 수를 반환함

맵을 구현하는 방법

1. 정렬되지 않은 배열을 사용하는 방법
2. 정렬된 배열을 이용하는 방법
3. 이진 탐색 트리를 이용하는 방법
4. 해싱을 이용하는 방법

정렬되지 않은 배열에서의 탐색

순차 탐색

정렬되지 않은 배열을 이용하면 순차 탐색(sequential search)을 사용할 수 있다.
배열의 요소들을 처음부터 마지막까지 하나씩 검사하며 원하는 레코드를 찾는 방법이다.
시간 복잡도는 $O(n)$이다.

정렬된 배열에서의 탐색

순차 탐색

마찬가지로 시간 복잡도는 $O(n)$이다.

이진 탐색

이진 탐색(binary search)은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽에 있는 지 오른쪽에 있는 지 판단하고 다음 단계의 탐색 범위를 반으로 줄이는 방법이다.

색인 순차 탐색

색인 순차 탐색(indexed sequential search) 방법은 index라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다.
인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있으며, 인덱스 테이블에 m개의 항목이 있고, 주 자료 리스트의 데이터 수가 n이면, 각 인덱스 항목은 주 자료 리스트의 각 $n/m$번째 데이터를 가지고 있다.
그 후 인덱스테이블에서 $index[i] <= key < index[i+1]$을 만족하는 항목을 찾는다.
해당 범위의 항목들에서 검색하면 시간을 상당히 줄일 수 있다.
시간 복잡도는 $O(m+n/m)$ 이다.
여기에 이진 탐색을 섞으면 시간 복잡도는 줄어든다.

보간 탐색

보간 탐색(interpolation search)은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다.
보간 탐색 시간 복잡도는 $O(log_2n)$이다.

• 탐색 위치는 다음과 같은 수식으로 구한다.

  $ \frac{(k-list[low])}{list[high]-list[low]}*(high-low) + low $

• 많은 데이터가 비교적 균등하게 분포되어 있을 때 훨씬 효율적이다.

균형 이진 탐색 트리

이진 탐색 트리 vs 이진 탐색

• 이진 탐색에서 자료는 배열에 저장되어 있어 삽입과 삭제가 $O(n)$ 으로 느리다.
• 트리로 구현하면 자료의 삽입과 삭제가 $O(log_2n)$으로 용이하다.
• 따라서 자료의 삽입과 삭제가 빈번하다면 이진 탐색 트리를 이용해야 한다.
• 트리의 경우도 균형 트리여야 $O(log_2n)$가 보장되며, 경사 트리의 경우는 시간복잡도가 $O(n)$이다.
• 그래서 이진 탐색 트리에서는 균형을 유지하는 것이 무엇보다 중요하다

AVL 트리

• Adelson-Velskii와 Landis에 의해 제안된 트리로, 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리 이다.
  • 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이를 균형 인수(balance factor)라고도 한다.
• 탐색 연산은 일반 이진 탐색 트리의 탐색 연산과 동일하다.
• 삽입과 삭제로 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다.
  • 균형이 깨진 가장 가까운 조상 노드(균형 인수가 +-2가 된 조상 노드)를 루트로 하는 서브트리의 노드들을 재배치하여 균형 상태로 만든다.
  • AVL 트리에서는 서브트리를 회전시켜 재배치한다.
• 가능한 회전은 네 가지가 있다. 새로 삽입된 노드를 N, 균형이 깨진 가장 가까운 조상 노드를 A라고 하면,
  1. LL 타입
     • N 이 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입된 경우
     • A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시켜 재배치한다.
  2. LR 타입
     • N 이 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입된 경우
     • A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시켜 재배치한다.
  3. RL 타입
     • N 이 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입된 경우
     • A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시켜 재배치한다.
  4. RR 타입
     • N 이 A의 오른쪽 서브트리의 오른쪽 서브트리에 삽입된 경우
     • A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시켜 재배치한다.
• 한번만 회전시키는 것을 단순 회전(single rotation)이라 하고, 두 번 회전시키는 것을 이중 회전(double rotation)이라고 한다.