BST

BST란 ?

이진트리

이진탐색트리(Binary Search Tree; BST)는 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node로만 이루어져 있다. 반대로 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있다.

이진트리(Binary tree)는 모든 node의 child nodes의 개수가 2 이하인 트리를 이진트리 라고 한다.


BST 조건

BST는 저장과 동시에 정렬을 하는 정렬된 tree이다. 따라서 새로운 데이터를 저장할 때 일정한 규칙에 따라 저장한다.

  1. 가운데 node 즉, root node의 값보다 작은 값은 left subtree, 큰 값은 right subtree에 잇다.

  2. subtree를 이어가는 subtree도 1번 조건을 만족한다.

시간복잡도

BST의 검색, 저장, 삭제의 시간복잡도는 모두 O(logn)이다. 위의 그림에서 ‘6’을 찾고 싶을 때 root node에서 6보다 큰지 작은지 비교하고, subtree로 갔을 때 또 6보다 큰지 작은지 비교하면서 검색을 해야하기 때문이다.

worst case

BST의 균형이 깨져서 한쪽으로 node가 치우친 경우가 생긴다. 이런 경우를 worst case라고 한다. Linked list의 형태처럼 보일 수 있다. 이 때는 탐색의 시간복잡도는 O(logn)가 아닌 O(n)이 된다.



Hash table

Hash table 이란?

효율적인 탐색(빠른 탐색)을 위한 자료구조로써, key-value 쌍의 데이터를 입력받는다. hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장한다. 따라서 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다.

고유의 계산식으로 index값을 정해 해당 index에 대입한다고 이해했다.

ex. h(k) = k mod 9

Collision

위와 같은 예시를 통해 해시값을 구하면 서로 다른 key이지만 해시값이 똑같이 나올 수가 있다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있다는 것이다. 이때 collision이 발생했다고 한다. 따라서 hash function을 설계할 때는 collision이 최대한 적게 나도록 설계해야하고, 어쩔 수 없이 collision이 발생했을 때 해결하는 방법을 생각해야한다.

※ 좋은 hash funtion은 ?

  1. 연산속도가 빨라야한다.
  2. 해시값이 최대한 겹치지 않아야 한다.


Hash table의 시간복잡도는 기본적으로 모두 O(1)이지만, collision으로 인해 최악의 경우 O(n)이 될 수 있다. 또한 공간효율성이 떨어진다.

collision 해결방법

open addressing 방식과 separate chaining 방식이 있다.

open addressing

Open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾는다. 이 규칙은 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉜다.

  • Linear Probing(선형조사법) & Quadratic Probing(이차조사법) : 선형조사법은 collision이 발생한 해시값으로 부터 일정한 값(+1, +2, …) 건너 뛰어, 이차조사법은 제곱수(+1, +4, …) 로 건너 뛰어 비어있는 slot에 데이터를 저장한다.


위의 방법은 만약 collision이 여러번 발생하면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링 현상이 발생하는 단점이 있다. 클러스터링 현상이 발생하면, 평균 탐색 시간이 증가하게 된다.


  • Double hashing(이중해싱) : 선형조사법 & 이차조사법을 통해 발생할 수 있는 클러스터링 현상을 방지하도록 2개의 해시함수를 사용하는 방식을 이중해싱 이라고 한다. 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 collsion이 발생할 때 탐사 이동폭을 얻기 위해 사용한다.


Seperate chaining

Seperating chaining 방식은 linked list(혹은 tree)를 이용하여 collision을 해결한다. collision이 발생하면 linked list에 node(slot)을 추가하여 데이터를 저장한다. 같은 인덱스에 여러 데이터를 linked list 형태로 저장하는 것이다. 이 때 위에서 언급했던 worst case의 경우 시간복잡도가 O(n)이 된다는 것이다.

댓글남기기

참고