해시 테이블
키와 값의 대응으로 이루어진 표
키를 통해 얻고자 하는 데이터는 버킷에 저장되어 있다.
해시 함수는 키를 인자로 활용해 인덱스를 반환합니다.
해시 충돌
서로 다른 키에 대해 같은 해시 값이 대응되는 상황
해결방법은 체이닝, 개방주소법, 이중 해싱이 있다.
체이닝
충돌이 발생한 데이터를 연결 리스트로 추가하는 방법
계속 추가되면 해시 테이블의 빠른 속도로 조회하는 장점이 사라진다.
개방 주소법
충돌이 발생했을 때, 충돌이 발생한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방법
선형 조사법은 개방 주소법의 한 예시로 충돌이 발생한 인덱스의 다음 인덱스부터 순차적으로 가용할 수 있는 인덱스를 찾는 것이다. 문제는 충돌이 발생하는 인덱스 인근에 여러 데이터 몰려 군집화가 나타날 수 있다. 군집화는 곧 순차탐색이라는 성능 악화로 이어진다.
이중 해싱
2개의 해시 함수를 사용하는 방법으로 f(key) + g(key) 에서 인덱스를 찾는 것이다.
이렇게 해시 함수를 통해 무작위로 인덱스가 생성될 수 있다면 선형 조사법의 군집화 문제를 회피할 수 있다.
트리
정 이진 트리
자식 노드의 개수가 0개 또는 2개인 이진 트리
포화 이진 트리
리프 노드를 제외한 모든 노드들이 자식 노드를 2개씩 가지고 있고, 모든 리프 노드의 레벨이 동일한 이진 트리
완전 이진 트리
마지막 레벨을 제외한 모든 레벨이 2개의 자식 노드를 가지고 있으며,
왼쪽 노드 부터 채워지는 특징을 가짐
이진 탐색 트리와 힙
이진 탐색 트리
특정 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값을 지닌 노드들이 있고,
오른쪽 서브트리에는 해당 노드보다 큰 값을 지닌 노드들이 있는 구조
O(log n)으로 원하는 값을 탐색 가능하다.
힙
와전 이진 트리의 종류 중 하나
최대값과 최소값을 빠르게 찾기 위해 사용된다.
부모 노드 > 자식 노드 최대 힙
부모 노드 < 자식 노드 최소 힙
우선 순위 큐는 최대 힙으로 구현되어 있다.
RB 트리
이진 탐색 트리에서 삽입과 삭제 반복 시 편향된 트리가 될 수 있다.
왼쪽 서브트리와 오른쪽 서브트리의 균형을 맞추는 것이 중요하다.
노드를 레드, 블랙으로 색칠하여 높이와 균형을 맞춘다.
루트 노드는 블랙 노드이다.
리프 노드는 블랙 노드이다.
레드 노드이 자식 노드는 블랙 노드이다.
루트 노드에서 임의의 리프 노드에 이르는 경로의 블랙 노드 수는 같다.
그래프
그래프란 정점이라 불리는 데이터를 간선 혹은 링크로 연결한 형태의 자료구조
DFS, BFS
DFS
그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법
BFS
인접한 모든 정점들을 방문하고, 방문한 정점들과 ㅇ녀결된 모든 정점들을 방문하고, 또 방문한 정점들과 연결된 모든 정점들을 방문하기를 반복하는 탐색 방법
