BST & Hash Table

BST(Binary Search Tree)

이진탐색트리는 정렬된 트리이다.

어느 노드를 선택하든 해당 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있는 이진 트리 , 저장과 동시에 정렬한다.

검색, 저장, 삭제의 시간복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 트리가 됐을 때 O(n)이다.

worst case는 한쪽으로 치우친 트리인데, Linked List와 다를게 없다.

자가 균형 BST는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지한다. 대표적으로 AVL트리와 Red-black tree가 있다.

Hash table

효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key - value쌍 구조를 가진다.

hash function h 에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 저장

저장, 삭제, 검색의 시간 복잡도는 모두 O(1)이다.

🥇Collision 발생

서로 다른 key의 해시값이 똑같을 때 발생

즉, 중복되는 key는 없지만 해시값은 중복 될 수 있는데 이때 Collision이 발생한다.

최대한 hash function을 잘 설계해야하고, 어쩔 수 없이 collision이 발생하는 경우 separate chaining 이나 open addressing등의 방법을 사용하여 해결한다.

[해결 방법]

1. Open addressing

   미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾는다. 빈 슬롯을 찾는 방법에 따라 Linear Probing, Quadratic Probing, Double Hashing으로 나뉜다.

   메모리를 적게 사용한다.

   • Linear Probing & Quadratic Probing

     충돌이 발생한 해시값으로 부터 일정한 값만큼 건너뛰어 비어있는 slot에 저장

     -> 탐사이동폭이 같기 때문에 특정 영역에 데이터가 집중적으로 몰리는 클러스터링 문제가 발생할 수 있다.

     

   • Double Hashing

     클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식

     하나는 최초의 해시값을 얻을 때 사용, 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용

     이동폭이 다르게 발생

2. Separete chaining

   Linked list를 활용하여 노트(slot)을 추가하여 데이터를 저장

   

​ [Worst Case]

​ n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되게 된다.

​ 이때, 특정 key를 찾기 위해서는 길이 n의 linked list를 검색하는 O(n)의 사간복잡도를 갖게 된다.