자료구조 33강 - 선형/계층적 자료구조의 탐색, 해쉬

검색 정리

 

형태	자료구조	Search 종류	알고리즘	시간 복잡도
				검색	추가	제거
선형	정렬된 배열	Arbitrary	Linear search	O(n)	O(n)	O(n)
			Binary search	O(log n)
			Interpolation search	O(log n)
		Top	Find max/min	O(1)
	스택	Arrival	Pop	O(1)	O(1)	O(1)
	큐		Push
계층적	이진 탐색 트리	Arbitrary	Search	O(log n) / O(n)	O(log n) / O(n)	O(log n) / O(n)
	히입(우선순위 큐)	Top	Find max/min	O(1)	O(log n)	O(log n)
해쉬	해쉬	Arbitrary	Hashing	O(1)	O(1)	O(1)

 

 

 

 

 

3가지 형태의 검색(search)

 

• 주어진 집합에서 임의의 원소 찾기(find arbitrary)
• 가장 처음으로(마지막으로) 온 원소 찾기(find first/last)
• 최대값 또는 최소값(top)인 원소 찾기(find top)

 

- 탐색(traversal)↔search

 

• 주어진 집합에서 시작하는 원소로부터 도달할 수 있는 모든 원소 찾기
• 트리와 그래프에서 사용

 

 

선형 자료구조

 

• 모든 원소가 인덱스에 대응되는 자료구조
• 리스트, 배열, 연결 리스트
• 구현 방법

1. 배열 vs 연결 리스트
2. 연속적 vs 이산적 
3. 인덱스 vs 포인터

 

- 선형 검색

 

• 자료구조의 모든 원소를 처음부터 방문하면서 찾는 값(key)과 비교
• 인덱스를 이용한 검색 : i=i+1
• 포인터를 이용한 검색 : curr=curr→link
• 정렬되지 않은 배열에도 적용 가능
• 시간 복잡도 : O(n)

 

- 이진 검색

 

• 배열의 중앙값(mid)와 비교하여 좌측 또는 우측의 부분 배열을 선택
• 정렬된 배열에서만 수행할 수 있음

mid = (high+low) / 2 = low + (high-low) / 2

• 시간 복잡도 : O(log n)
• 문제점 : 찾는 값이 low나 high값에 치우친다면 mid보다 치우친 쪽에서 부터 찾는 것이 효율적

 

- 보간 검색(Interpolation search)

 

• 검색을 시작하는 값(mid)를 배열의 값을 고려해서 결정

mid = low + {(key-list[low]) / (list[high]-list[low])} (high-low)

 

 

검색 별 차이점

 

조건	선형 검색	이진 검색	보간 검색
다음에 비교할 위치	i+1	low+1/2(high-low)	low+{(key-list[low])/(list[high]-list[low])}(high-low)
시간 복잡도	O(n)	O(log n)	개선된 O(log n)
정렬된 배열을 요구	No	Yes	Yes
연결 리스트에서 가능	Yes	No	No

 

 

계층적 자료구조

 

• 트리 구조
• 트리구조에 대한 탐색(traversal) : 이진 트리 - 중위, 전위, 후위 / 일반적인 트리 - 넓이, 깊이
• 트리구조를 이용한 검색(search) 

1. find arbitrary : binary search tree
2. find top : heap

 

- 이진 트리

 

ⓞ 트리 탐색 알고리즘 : O(n)

 

• Pre-order traversal
• In-order traversal
• Post-order traversal

 

- 이진 탐색 트리(Binary search tree, BST)

 

• 이진 트리
• 다음의 조건을 만족

1. 각노드에는 서로 다른 하나의 값이 저장
2. 왼쪽 부분 트리에 저장된 값들 < 루트 노드에 저장된 값
3. 오른쪽 부분 트리에 저장된 값들 > 루트 노드에 저장된 값
4. 왼쪽 부분 트리와 오른쪽 부분 트리는 모두 이진 탐색 트리

 

- 이진 탐색 트리 검색의 시간 복잡도 : O(log n)

 

1. 정렬된 리스트보다 좋은 점

 

• 검색의 시간 복잡도는 비슷하지만 추가, 제거의 시간 복잡도는 O(log n)으로 더 효율적

 

2. 정렬된 리스트보다 나쁜 점

 

• 최선의 경우는 모든 연산이 O(log n)이지만 최악의 경우는 O(n)이다

 

- 히입(우선 순위 큐)

 

1. 우선순위가 가장 높은 원소가 가장 앞에 오는 자료 구조
2. 완전 이진 트리
3. 최대 히입(최소 히입)

• 각 노드에 저장된 값이 자식 노드에 저장된 값들보다 더 작지 않음(크지 않음)

 

- 균형 이진 탐색 트리(Balanced Binary Search Tree, BBST)

 

• 최악의 경우 연산의 시간 복잡도가 O(n)이 되는 이진 탐색 트리의 단점을 보완한 구조
• Self-balancing search tree
• Height-balanced search tree
• 항상 height가 최소가 되도록 트리를 유지함

1. AVL tree
2. Red-black tree
3. 2-3 tree
4. B+ tree

 

1. AVL tree

 

• 최악의 경우, O(n)의 시간 복잡도가 발생하는 이진 탐색 트리의 단점 개선을 위해 제안된 트리
• 이진 탐색 트리의 최악의 경우를 피하는 방법
• G. M. Adelson-Velskii & E. M. Landis(1962)가 만듦
• 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 height의 차를 1이하로 유지
• Balance factor = Height of right subtree 
• 추가/제거 연산으로 인해서 balance가 깨질 수 있음
• 항상 balance가 유지되도록 balancing 연산을 수행
• Balancing 연산

1. Single left rotate
2. Single right rotate
3. Double left rotate
4. Double right rotate

 

2. Red-black tree

 

• L. J. Guibas and R. Sedgewick(1978)이 제안
• 다음의 다섯 가지 성질을 만족하는 이진 탐색 트리

1. 모든 노드는 red 또는 black
2. Root node는 black
3. 모든 leaf node(NIL node)는 black
4. 한 노드가 red라면, 자식 노드는 모두 black
5. 한 노드에서 모든 자식 노드까지의 경로에는 동일한 수의 black 노드가 존재

 

3. 2-3 tree

 

• J. Hopcroft(1970)이 제안
• 2개 또는 3개의 자식 노드를 갖는 탐색 트리

1. 2-node : 하나의 값이 저장되며 2개의 자식 노드를 가짐
2. 3-node : 2개의 값이 저장되면 3개의 자식 노드를 가짐

 

4. B+ tree

 

• 여러 개의 자식 노드르 갖는 트리(k-ary tree)
• 각 노드는 (k-1) 개의 key 값과 k개의 부분 트리를 가짐

 

 

해쉬

 

ⓞ 이진 탐색 

 

• O(log n)의 탐색 시간
• 자료의 크기에 따라서 검색 시간이 결정됨

ⓞ 자료의 크기에 상관없이 실시간에 탐색이 수행되어야 하는 경우가 있음

ⓞ O(1)의 탐색 시간을 보장하는 자료 구조 및 알고리즘

 

- 정의 : 모든 키의 레코드를 산술 연산에 의해 한 번에 바로 접근할 수 있는 기법

 

• 해쉬 함수(Hash function)
• 해쉬 인덱스(Hash index)
• 해쉬 테이블(Hash table)
• 충돌(collision) & 충돌 해소(collision resolution)

 

- 해쉬 함수

 

① 자릿수 선택(digit selection)

 

• 키의 값 중에서 일부 자릿수만 골라내서 인덱스를 생성하는 함수

ex. 13자리 주민등록번호 중 홀수 자릿수만 선택 → 충돌 발생 가능성

 

② 자릿수 접기(digit folding)

 

• 키의 각각의 자릿수를 더해서 인덱스를 생성하는 함수

ex. h(50421), h(29001) → 충돌 발생 가능성

 

③ 모듈로 연산(modul function)

 

• 키를 해쉬 테이블의 크기로 나눈 나머지를 인덱스로 생성하는 함수
• h(key) = key mod tablesize

ex. h(50421)=50421%10=1, h(29001)=29001%10=1 → 충돌 발생 가능성

 

- 충돌(collision)

 

• 서로 다른 키를 가진 레코드가 해쉬 함수에 의해서 동일한 인덱스로 대응되는 현상
• 예시

1. Hash function : H(k) = k mod m, where m=17
2. For k1= 18 & k2 = 171 → H(k1) = 18 mod 17 = 1, H(k2) = 171 mod 17 =1

 

- 충돌 해소

 

ⓞ 충돌이 발생한 레코드를 다른 주소에 저장하는 기법

ⓞ 열린 어드레싱(open addressing) 

 

• 충돌이 발생한 레코드를 저장할 다른 주소를 찾는 방법
• 레코드의 주소(address)가 변경될 수 있기 때문에 열린(open) 어드레싱이라고 함

 

① 선형 탐사(linear probing)

 

• 충돌이 일어나면 그 다음 빈 곳에 원소를 저장
• 배열의 끝을 만나면 다시 처음으로 되돌아와서 빈자리를 찾음
• 단점 : 클러스터링(clustering) - 레코드가 분산되지 않고 군집되는 현상

※ 태그(tag) : 선형 탐사에서 다음 원소를 가리키는 포인터

※ 태그의 필요성

 

1. 다음 자리 h(key)+1에 이미 다른 원소가 존재할 때 다음 원소의 위치를 가리킴
2. 중간의 원소를 삭제할 때 태그를 수정함

 

② 제곱 탐사(quadratic probing) 

 

• 충돌이 일어날 때 바로 그 뒤에 넣지 않고 조금 간격을 두고 삽입
• 클러스터링을 피할 수 있는가?

1. 연속적인 배열을 피할 수 있음
2. 동일한 키를 가진 레코드는 동일한 자리에 삽입됨
3. 궁극적으로는 클러스터링을 피할 수 없음 → 2차 클러스터링

 

③ 이중 해시(double hash)

 

• 제곱탐사의 단점인 2차 클러스터를 방지
• 두 개의 해쉬 함수 h1, h2를 사용

1. h1은 주어진 키로부터 인덱스를 계산하는 해쉬 함수
2. h2는 충돌 시 탐색할 인덱스의 간격(step size)을 의미

 

ⓞ 닫힌 어드레싱(closed addressing) 

 

• 충돌이 발생한 레코드를 동일한 주소에 저장하는 방법
• 주소가 변경되지 않으므로 닫힌(closed) 어드레싱이라고 함

 

① 버킷(bucket)

 

• 해쉬 테이블의 각 원소들이 다시 여러 개의 원소로 이루어짐
• 2차원 배열
• 충돌되는 레코드를 하나의 인덱스에 둠
• 사용되지 않는 배열 공간이 낭비됨

 

② 별도 체인(separate chain)

 

• 해쉬 테이블의 각 원소들이 연결 리스트를 가리키는 헤드
• 충돌이 일어날 때마다 해당 레코드를 연결 리스트의 첫 위치에 삽입
• 동적 구조(Dynamic Structure)