힙
이진 탐색 트리
→ 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리가 이진 탐색 트리입니다.
이진 탐색트리의 시간 복잡도는 트리의 높이인 LogN~N만큼의 시간 복잡도를 갖습니다. 그래서 트리가 편향되지 않기 위해서 자가 균형 트리를 사용합니다.
자가 균형 트리
→ 이진 탐색트리는 시간 복잡도가 트리의 높이에 따라 결정되므로 편향될 경우 효율이 떨어집니다. 그래서 편향되지 않게 삽입과 삭제를 개선한 이진 탐색 트리를 자가 균형 트리라고 합니다.
자가 균형 트리는 AVL 트리와 Red Black트리가 있습니다.
해시
→ 해시는 해시에 매핑하여 데이터를 저장하는 자료구조 입니다. key는 hash function을 통해 hash로 변경된 다음 value와 매핑되어서 bucket에 저장하게 됩니다. 시간복잡도는 삽입,삭제,조회가 모두 O(1)의 시간 복잡도를 갖습니다.
해시 충돌 회피 방법
→ 충돌회피 기법은 해시에서, 하나의 버킷에 여러개의 데이터가 들어갈 때에 그 충돌을 회피하는 방법으로 Open Adressing 과 Chaining이 있습니다. Open Adressing은 다른 비어있는 버킷의 해시값에 저장하는 방법이구요. Chaining은 HashTable이 원소하나를 담는게 아니라 LinkedList를 담는 방입니다.