자료구조 용어집

자료구조 분야의 개념 27개를 한 장에 모았습니다. 거짓 양성 · 격자 · 계층 구조 표현 · 균형 탐색 트리 등 — 코드베이스에서 뽑아 뜻과 관계를 정리했습니다.

거짓 양성 (false positive)
없는 원소를 있다고 답하는 오류. 블룸 필터는 비트 배열이 찰수록 이 확률이 오른다. 크기와 해시 개수로 목표 확률을 맞춘다
격자 (lattice)
글자 경계마다 노드를 두고 사전에 있는 후보 단어를 간선으로 깐 그래프. 형태소 분석의 탐색 공간이고, 사전에 없는 단어는 간선 자체가 없다
계층 구조 표현
부모-자식 관계를 트리로 담는다. 정렬된 탐색(BST), 최솟값 · 최댓값 꺼내기(힙), 문자열 접두사(트라이), 구간 합 · 최솟값(세그먼트 트리)처럼 목적에 따라 트리 모양을 고른다
균형 탐색 트리 (self-balancing BST, TreeMap, TreeSet)
삽입 · 삭제 때 회전으로 높이를 O(log n) 으로 유지하는 BST. 높이 차를 엄격히 묶는 AVL 과 색 규칙으로 느슨하게 묶는 레드-블랙 트리가 대표다. 디스크용 다분기 균형 트리는 B-트리다
그래프 (graph, vertex, edge)
정점과 간선의 집합. 방향 · 가중치 유무로 나뉘고, 인접 리스트(희소)나 인접 행렬(밀집)로 저장한다
배열 (array)
같은 크기의 원소를 연속 메모리에 둔다. 인덱스 접근은 O(1), 중간 삽입 · 삭제는 뒤 원소를 밀어야 해서 O(n) 이다. 캐시 지역성이 좋다
블룸 필터 (Bloom filter)
비트 배열과 해시 함수 여러 개로 원소가 「확실히 없음」 또는 「아마 있음」을 답한다. 메모리가 아주 작지만 거짓 양성이 있고 삭제가 안 된다. 비싼 조회 앞에서 없는 키를 걸러 낸다
순차 데이터 저장
원소를 한 줄로 담는다. 위치로 바로 접근할지(배열), 중간 삽입 · 삭제가 쌀지(연결 리스트), 넣고 빼는 순서를 제한할지(스택 · 큐 · 덱)를 고른다
스킵 리스트 (skip list, ConcurrentSkipListMap)
정렬된 연결 리스트 위에 확률적으로 고른 노드만 잇는 층을 여러 개 쌓아 평균 O(log n) 에 찾고 넣는다. 회전 없이 균형이 맞아 구현이 단순하고 동시성 제어가 쉽다. Redis sorted set 이 이 구조다
스택 (stack, LIFO)
마지막에 넣은 것을 먼저 꺼낸다(LIFO). 함수 호출 스택 · 되돌리기 · 괄호 짝 맞추기 · 반복형 DFS 에 쓴다
연결 리스트 (linked list, singly linked list, LinkedList)
각 노드가 값과 다음 노드 포인터를 가진다. 위치를 알면 삽입 · 삭제가 O(1) 이지만 k 번째 원소를 찾으려면 O(n) 을 걷는다. 노드가 흩어져 캐시 지역성이 나쁘다
이진 탐색 트리 (binary search tree, BST)
왼쪽 자식 < 부모 < 오른쪽 자식을 지키는 이진 트리. 높이만큼 비교해 찾으므로 균형이면 O(log n), 치우치면 O(n) 이다. 중위 순회하면 정렬 순서가 나온다
이진 트리 (binary tree, complete binary tree, full binary tree)
각 노드가 자식을 최대 둘 가지는 트리. 모든 층이 차고 마지막 층이 왼쪽부터 채워지면 완전 이진 트리라 배열에 빈틈없이 담긴다
적재율 (load factor)
저장된 원소 수를 버킷 수로 나눈 값. 기준(자바 HashMap 은 0.75)을 넘으면 버킷을 늘려 다시 배치한다
큐 (queue, FIFO)
먼저 넣은 것을 먼저 꺼낸다(FIFO). 작업 대기열 · 버퍼 · BFS 에 쓴다
키 조회 구조 설계
키로 값을 빨리 찾는 구조를 고른다. 순서가 필요 없으면 해시, 범위 · 순서 조회가 필요하면 균형 트리나 스킵 리스트, 접두사 검색이면 트라이, 최근 사용 순 제거가 필요하면 LRU 다
트라이 (trie, prefix tree, 접두사 트리)
문자열을 글자 단위로 쪼개 간선에 싣는 트리. 길이 m 인 문자열을 O(m) 에 찾고, 같은 접두사를 공유해 자동완성 · 사전 탐색에 맞다
트리 (tree)
순환 없이 부모-자식으로 이어진 계층 구조. 루트에서 각 노드까지 경로가 하나뿐이다. 그래프의 특수한 경우다
트리 편향 (unbalanced tree, skewed tree)
탐색 트리가 한쪽으로만 깊어져 높이가 n 에 가까워진 상태. O(log n) 이던 연산이 O(n) 으로 떨어진다
해시 충돌 (hash collision, hash flooding)
서로 다른 키가 같은 해시 버킷에 떨어지는 상태. 체이닝이나 개방 주소법으로 처리하고, 몰리면 조회가 선형으로 느려진다. 해시가 예측 가능하면 공격자가 일부러 몰 수 있다
해시 함수 (hash function, MurmurHash, xxHash, FNV)
임의 길이의 입력을 고정 범위의 값으로 바꾸는 함수. 같은 입력은 항상 같은 값을 내고, 자료 구조용은 값이 고르게 퍼지고 빠른 것(MurmurHash · xxHash)이 중요하다. 보안용 암호 해시와는 목적이 다르다
해시맵 (hash map, hash table, 해시 테이블, HashMap, HashSet)
키를 해시 함수로 버킷 위치로 바꿔 평균 O(1) 로 넣고 찾는다. 순서가 없고, 충돌이 몰리면 최악 O(n) 이 된다. 적재율이 넘으면 버킷을 늘려 다시 배치한다
힙 (heap, binary heap, min-heap, max-heap, heapify)
부모가 항상 자식보다 작거나(최소 힙) 큰(최대 힙) 완전 이진 트리. 배열에 담고 루트 조회는 O(1), 넣기 · 꺼내기는 O(log n), 배열 전체를 힙으로 만드는 건 O(n) 이다. 상위 K 개 뽑기에 쓴다
B-트리 (B-Tree, B트리)
노드 하나에 키를 여러 개 담아 높이를 낮게 유지하는 자기 균형 탐색 트리. 디스크 페이지 단위로 읽기에 맞아 관계형 DB 인덱스의 기본 구조가 된다
DAG (Directed Acyclic Graph, 방향 비순환 그래프)
방향 비순환 그래프. 간선에 방향이 있고 순환이 없어 위상 순서가 존재한다
HNSW (Hierarchical Navigable Small World)
계층 그래프로 벡터 근사 최근접을 찾는 자료구조. 위층의 성긴 그래프로 멀리 뛰고 아래층의 촘촘한 그래프로 좁힌다
HNSW 파라미터 (ef_search, num_candidates, ef_construction)
m(노드당 이웃 수) · ef_construction(색인 때 탐색 폭) · ef_search(질의 때 탐색 폭, num_candidates). 올리면 재현율과 메모리·지연이 같이 오른다. 샤드마다 후보를 뽑으므로 샤드 수와도 곱해진다

다른 분류