Hash table(해시 테이블)
- 해시함수를 사용하여 변환한 값을 index로 삼아 키(key)와 값(value)를 저장하는 자료구조
- 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적
해시 함수(Hash Function)
입력(키, 값)을 받아 고정된 크기의 숫자 값(해쉬값, hash code)으로 변환하는 함수
해시 테이블 충돌 해결법
체이닝(Chaining)
- 같은 인덱스에 연결 리스트로 여러 개 저장
오픈 어드레싱(open addressing)
- 비어있는 주소를 탐색하여 저장
활용
-> 데이터베이스 인덱스 구현
-> 사용자 로그인 인증
Graph(그래프)
- 정점(vertex, Node)과 간선(Edge)로 이루어진 자료구조
- 무방향 그래프(Undirected Graph): 양방향 연결
- 방향 그래프(Directed Graph, Digraph): 단방향 연결
- 가중치 그래프(Weighted Graph): 간선에 비용/거리 있음(지도, 최단경로)
- 사이클 그래프(Cycle Graph): 시작한 정점으로 다시 돌아올 수 있는 경로 존재
- 비순환 그래프(Acyclic Graph): 어디를 가든 출발점으로 다시 돌아올 수 없음
구현 방식
- 인접 행렬(Adjacency Matrix)
- 인접 리스트(Adjacency List)
Tree(트리)
- 사이클 없는 연결 그래프
- 계층적 구조를 표현
- 루트(root)에서 시작해 자식(child)으로 뻗어나감
- 상위 노드를 부모(parent)노드, 하위 노드를 자식(child)노드라고 함
- 루트(root): 트리의 시작점
- 노드(node): 트리의 각 원소
- 간선(edge): 노드 간의 연결선
- 리프(leaf): 자식 없는 노드
- 서브트리(subtree): 트리 안의 트리
이진 트리(Binary Tree)
- 각 노드가 최대 두 개의 자식을 가지는 트리
이진 탐색 트리(BST, Binary Search Tree)
- 왼쪽 서브트리의 모든 노드 값 < 루트값
- 오른쪽 서브트리의 모든 노드 값 > 루트 값
- 왼쪽 자식 < 부모 < 오른쪽 자식
균형 트리 (AVL Tree)
- 모든 노드에서 왼쪽 서브트리 높이-오른쪽 서브트리 높이 <= 1
- 삽입, 삭제 시 불균형이 발생하면 회전을 통해 균형
- 탐색 속도 빠름(O(log n)) -> 삽입, 삭제 시 회전 연산이 자주 발생해서 비용 증가할 수 있음
B트리(B-Tree)
- 균형 다진 탐색 트리
- 이진 탐색 트리(BST)는 자식이 최대 2개 -> 깊이가 커짐 -> 디스크 I/O 증가
- B트리는 한 노드가 여러 개의 키와 자식을 가질 수 있음 -> 트리의 높이 낮아짐
- DB, 파일시스템에서 인덱스로 사용
규칙
-
한 노드가 최대 m개의 자식을 가짐
-
모든 리프 노드는 같은 레벨에 존재(균형 유지)
-
각 노드 안에 여러 키가 오름차순으로 정렬돼 있음
-
탐색 규칙
- 노드 안의 키들을 이진 탐색
- 키보다 작으면 왼쪽, 크면 오른쪽 자식으로 이동
연산
- 삽입, 삭제, 탐색 모두 시간 복잡도는 O(log n)
B+Tree
- 데이터베이스와 파일시스템에서 인덱스 구조로 가장 널리 사용
B트리와 차이점
- 실제 데이터(레코드)는 리프 노드에만 저장
- 내부 노드는 탐색을 돕는 인덱스 키만 저장
- 리프 노드끼리 Linked List로 연결되어 있어 범위 검색 최적화
장점
- 범위 검색 최적화 (시간 복잡도: O(log n + k)(k=범위 내 원소 수)
- 내부 노드 메모리 효율 향상
- 디스크 친화적 구조
Heap(힙)
- 완전 이진 트리(Complete Binary Tree) 기반의 자료구조
- 항상 부모 노드의 값 >= or <= 자식 노드의 값이라는 규칙을 가짐
- 주로 우선순위 큐 구현에 사용
최대 힙(Max Heap)
- 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다
-> 루트 노드의 키 값이 트리의 최댓값
최소 힙(Min Heap)
- 최소 힙: 부모의 키 값이 자식의 키 값보다 작거나 같다
->루트 노드의 키 값이 트리의 최솟값
시간 복잡도
삽입, 삭제: O(log n)
최대/최소값 접근: O(1)
힙 정렬: O(n log n)
힙 정렬(Heap Sort)
- 배열을 힙으로 만든 뒤, 루트(최대/최소값)를 하나씩 꺼내서 정렬
