[자료구조] 이진 탐색 트리, 해시 검색 방법 정리

이진탐색트리

왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리. 

출처 : https://code-lab1.tistory.com/10

이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다.

이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 

트리 구조에 따라서 logN ~ N까지의 시간복잡도를 가질 수 있다. (편향된 이진 탐색트리인 경우, N(높이)만큼의 시간복잡도를 가짐.) 

해당 경우를 방지하기 위해 자가 균형트리가 존재. 

 

자가 균형트리 

트리가 한쪽으로 편향되지 않도록 삽입, 삭제를 개선한 이진 탐색트리. 

AVL 트리와 Red black 트리가 존재. 

해시

해시에 매핑하여 데이터를 저장하는 방법. 

'데이터를 저장하는 위치 = 인덱스'를 간단한 연산으로 구하는 것. 

원소의 검색뿐만 아니라, 추가&삭제도 효율적으로 수행할 수 있습니다. 

장단점.

• 해시 충돌이 발생(개방 주소법, 체이닝 과 같은 기법으로 해결해 줘야 한다.)
• 순서/관계가 있는 배열에는 어울리지 않는다.
• 공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다. 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다. (메모리 낭비)

해시는 배열의 단점을 커버한다

배열에서는 (추가, 삭제로 인한)요소 이동에 필요한 복잡도(time-complexity)가 O(n)이다(꽤 무거움). 배열 요소를 추가, 삭제할 때마다 하나씩 앞으로(뒤로) 쭉 밀어서 자리를 만드는 과정이 필요하다. 

해시에서는 (추가, 삭제로 인해)요소가 이동하더라도 다른 배열 요소들을 앞뒤로 옮기지 않아도 된다.

해시 값의 충돌 collision 

• 체인법
• 오픈주소법

체인법 

• 해시값이 같은 데이터를 체인 모양의 연결리스트로 연결하는 방법. 

오픈주소법 (선형 탐색법) 

• 충돌이 발생했을 때, 재 해시를 수행하여 빈 버킷을 찾는 방법. 
• 즉, 다시 해시값을 찾아서 다른 버킷에 저장하는 방법을 의미.