CS - 자료구조

< 힙 >

-> 최댓값 혹은 최솟값을 빠르게 찾기 위한 이진트리이다. 최소 힙의 경우에는 부모는 자식보다 작고, 최대 힙의 경우에는 부모는 자식보다 커야 한다. 삽입과 삭제는 로그 N 만큼의 시간복잡도를 갖는다.

< 이진 탐색 트리 >

-> 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리이다. 삽입, 검색, 삭제가 모두 트리의 높이인 log N ~ N(한쪽으로 편향될 수 있기 때문) 만큼의 시간복잡도를 갖는다. 트리가 편향되지 않기 위해선 자가 균형 트리를 사용한다.

< 자가 균형 트리 >

-> 이진 탐색 트리는 시간복잡도가 트리의 높이에 따라 결정되므로 편향될 경우 효율이 떨어진다. 그래서 편향되지 않게 삽입과 삭제를 개선한 이진 탐색 트리를 자가 균형 트리라고 한다.
ex) AVL 트리, Red Black 트리

< 해시 >

-> 해시에 매핑하여 데이터를 저장하는 자료구조이다. key 는 hash function 을 통해서 hash 로 변경된 다음에 value 와 매핑되어서 bucket 에 저장되게 된다. 시간복잡도는 삽입, 삭제, 조회가 모두 O(1) 의 시간복잡도를 갖는다.

< 해시 충돌 회피 방법 >

-> 해시에서 하나의 bucket 에 여러 개의 데이터가 들어갈 때, 충돌을 회피하는 방법이다.

• Open Adressing : 다른 해시값에 저장
• Chaining : 해시 테이블이 원소 하나를 담는 게 아니라, Linked List 를 담음