개념 - 탐색

탐색 : 하나 이상의 필드(field)로 구성되는 레코드(record)의 집합에서 특정 레코드를 찾는 작업

테이블 : 레코드의 집합

탐색 키 : 중복되지 않고 고유한 값을 가지는 필드, 

검색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 것이다.

맵(map), 사전(dictionary)

탐색을 위한 자료구조. 키를 이용해 원하는 자료를 빠르게 찾을 수 있게 하는 자료구조.

키 레코드, 또는 엔트리라 불리는 키-값 쌍을 테이블에 저장한다. 즉 맵은 키를 가진 레코드의 집합이다.

키 레코드 keyed record의 ADT

create(key, value)

getKey();

getValue();

update(value);

맵 Map의 ADT

create() 공백 상태의 맵 생성

search(key) 

insert(entry)

delete(key)

count()

맵을 구현하는 방법들

정렬되지 않은 배열 : O(n)?

정렬된 배열 : O(log n)

이진 탐색 트리 : O(log n) (균형이 맞을 때)

해싱 : O(1) -> 탐색 키의 비교가 아닌, 탐색 키를 수식에 적용시켜 레코드가 저장된 위치를 바로 얻음.

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

순차 탐색 sequential search : 하나씩 검색하는 o(n)

정렬된 배열에서의 탐색

개선된 순차 탐색

배열이 정렬되있다면, 탐색키보다 큰 레코드를 만나면 탐색을 종료시킬 수 있어서 전체를 검색하지 않아도 된다.

그러나 여전히 O(n)

이진 탐색 binary search

비교 한번에 탐색범위가 1/2씩 줄어드는 효율적인 방법. O(logn)

색인 순차 탐색 indexed sequential search

주 자료 리스트에서 일정 간격으로 발췌한 자료를 가진 인덱스 테이블을 사용한다. 

index[i] <= index[i+1] 사이 범위에 키가 있다면 해당 인덱스 구간만 검색하면 된다.

인덱스 테이블의 크기가 m, 주 자료의 크기가 n O(m + n/m)

보간 탐색 interpolation search

데이터의 값의 범위와 찾는 키값의 비를 이용해서 검색할 인덱스를 찾는다. 

균형 이진 탐색 트리

이진 탐색 트리는 균형상태일때만 O(logn)의 시간복잡도를 보장한다. 경사 트리인 경우에는 복잡도가 O(n)으로 늘어난다.

AVL 트리

Adelson-velskii와 landis가 고안한, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리

왼쪽 서브트리의 높이 - 오른족 서브트리의 높이를 균형 인수라고 하는데, 균형 인수가 +-1 이하이면 AVL트리다. 

AVL 트리의 삽입 연산

AVL 트리에서 균형이 깨지는 경우를 다음과 같이 나열한다.

새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 +-2가 된 조상 노드를 A라고 할 때

LL 타입 : N이 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입된다.

LR 타입 : N이 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입된다.

RR 타입 : N이 A의 오른족 서브트리의 오른쪽 서브트리에 삽입된다.

RL 타입 : N이 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입된다.

LL, RR 회전 : 단순 회전single rotation 이 둘은 대칭

LR, RL 회전 : 이중 회전double rotation 이 둘은 대칭