BST, Heap, Graph를 실무 구조로 읽기
BST는 정렬된 탐색, Heap은 우선순위 접근, Graph는 관계 탐색을 다루는 핵심 자료구조다. 이 세 구조가 DB 인덱싱, 작업 스케줄링, 의존성 관리에서 어떻게 드러나는지와 잘못 선택했을 때의 실패 신호를 함께 정리한다.
Script Companion
오디오와 함께 스크립트 보기
- 01
트리와 그래프를 배울 때 중요한 점은 모양을 외우는 것이 아니라, 어떤 결정을 빠르게 하기 위해 이 구조가 필요한지 보는 것이다. 정렬된 데이터에서 찾기만 빠르면 배열의 이진 탐색으로 충분하지만, 삽입과 삭제까지 계속 빠르게 해야 하면 BST가 필요해진다. 작업마다 긴급도가 다르면 Heap 기반 Priority Queue가 등장하고, 서비스 의존성이나 네트워크 라우팅처럼 관계 자체를 따라가야 하면 Graph 탐색이 필요해진다.
- 02
먼저 Binary Search Tree, 즉 BST는 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값이 놓이는 이진 트리다. 도서관의 십진분류법 책장을 떠올리면, 책을 찾을 때 모든 칸을 훑지 않고 현재 위치에서 왼쪽으로 갈지 오른쪽으로 갈지만 판단하는 구조에 가깝다. 이 속성 덕분에 높이가 h인 트리에서 탐색, 삽입, 삭제는 모두 O(h)가 되고, 균형이 잡혀 있으면 h가 log n이어서 O(log n)으로 동작한다. 하지만 정렬된 데이터를 순서대로 넣어 한쪽으로만 자라면 트리는 사실상 Linked List가 되고, 이때 높이는 n이 되어 O(n)까지 나빠진다.
- 03
BST의 실무 핵심은 균형이다. AVL Tree와 Red-Black Tree는 삽입이나 삭제 뒤에 자동으로 균형을 맞춰 최악 케이스를 O(log n)으로 보장한다. AVL Tree는 좌우 높이 차이를 1 이하로 엄격하게 유지해서 탐색이 약간 빠른 대신 회전이 더 많고, Red-Black Tree는 높이 차이를 더 느슨하게 허용해 삽입과 삭제가 더 실용적이다. 문서의 기준으로는 쓰기 합산이 워크로드의 절반을 넘으면 Red-Black, 탐색이 99%면 AVL이 실용적인 판단선이다. Java TreeMap, C++ std::map, Linux 커널의 CFS와 epoll은 Red-Black Tree를 채택한 사례로 제시된다.
- 04
잘못된 균형 트리를 고르면 에러가 바로 터지기보다 지연 시간이나 처리량으로 드러난다. 탐색이 99% 이상인 정적 사전 자동완성이나 라우팅 테이블에 Red-Black을 그대로 쓰면 AVL보다 트리 높이가 길어질 수 있고, p99 latency가 캐시 미스 한 단계만큼 늘어나는 식으로 나타난다. 반대로 알림 큐나 스케줄러처럼 삽입과 삭제가 끊임없는 워크로드에 AVL을 쓰면 회전이 많아 처리량이 점진적으로 떨어진다. 진단은 평균 노드 깊이를 노출하고, 같은 워크로드 트레이스를 N=10⁵로 재현해 두 구현의 평균 응답 시간을 비교하는 방식으로 접근한다.
- 05
DB 인덱스가 단순 BST가 아니라 B-Tree를 쓰는 이유도 높이와 I/O의 문제다. B-Tree는 한 노드에 여러 키를 저장하는 자가 균형 다진 트리라서 트리 높이를 극단적으로 낮추고, 삽입과 삭제 때도 재균형한다. MySQL과 PostgreSQL의 기본 인덱스가 B-Tree 기반이고, created_at 범위 쿼리나 id 범위 쿼리가 O(log n)에 동작하는 이유가 여기에 있다. JavaScript Map은 해시 테이블 기반이지만, 정렬된 키 순회가 필요하면 Java TreeMap 같은 BST 기반 자료구조가 의미를 가진다. Express와 Fastify 기반 Nest.js 라우트 매핑에서 Radix Tree가 언급되는 것도 문자열 경로를 트리 구조로 다룬다는 점과 연결된다.
- 06
Heap은 우선순위가 있는 선택을 빠르게 하기 위한 구조다. 응급실에서 먼저 온 환자가 아니라 중증도가 높은 환자를 먼저 보는 상황처럼, Priority Queue는 들어온 순서보다 우선순위를 기준으로 꺼낸다. Heap은 완전 이진 트리이고, Max Heap은 부모가 자식보다 크거나 같아 루트가 최댓값이며, Min Heap은 부모가 자식보다 작거나 같아 루트가 최솟값이다. 삽입은 새 요소를 끝에 넣고 위로 올리는 Heapify Up으로 O(log n), 삭제는 루트를 제거한 뒤 마지막 요소를 루트로 올리고 내려보내는 Heapify Down으로 O(log n), 최댓값이나 최솟값 조회는 루트를 읽기만 하므로 O(1)이다.
- 07
Heap의 실패는 우선순위 순서가 조금씩 틀어지는 방식으로 나타난다. pop 이후 peek이 최솟값이 아닌 값을 반환한다면 루트 삭제 뒤 Heapify Down을 빠뜨렸거나, 두 자식 중 더 작은 쪽을 골라야 하는 Min Heap에서 무조건 왼쪽 자식과만 교환했을 가능성이 크다. Top-K 문제에서도 선택이 중요하다. n개 원소에서 가장 큰 k개를 구할 때 전체를 Max Heap에 넣고 k번 꺼내는 방식은 정확하지만, n이 1,000,000이고 k가 10처럼 작으면 Min Heap으로 k개만 유지하는 편이 훨씬 효율적이다. 문서는 이 경우 전체 저장 약 8MB와 k개 유지 약 80바이트라는 차이를 제시한다.
- 08
Graph는 노드와 엣지로 관계를 표현하는 구조다. 지하철 노선도에서 역이 노드이고 선로가 엣지라면, 어느 역까지의 최단 경로를 찾거나 특정 노선의 역들을 순회하는 일이 그래프 탐색이다. 그래프 표현은 크게 인접 행렬과 인접 리스트로 나뉜다. 인접 행렬은 공간이 O(V²)이지만 연결 확인이 O(1)이라 밀집 그래프에 맞고, 인접 리스트는 공간이 O(V + E)라 희소 그래프에 맞으며 이웃 탐색 비용은 degree에 비례한다. 문서의 선택 임계점은 실제 엣지 수를 V²로 나눈 밀도가 약 1/64 이상이면 행렬이 공간 측면에서도 경쟁력을 갖기 시작한다는 것이다.
- 09
그래프 표현을 잘못 고르면 작은 테스트는 통과하고 production 규모에서만 무너질 수 있다. V=10,000인 희소 그래프에 인접 행렬을 boolean 배열로 쓰면 V²가 10⁸이 되고, JavaScript의 boolean이 V8 내부에서 사실상 8바이트를 차지할 수 있어 약 800MB까지 커진다. Node.js 기본 heap limit이 약 2GB라는 점을 고려하면 위험 신호가 된다. 반대로 V=500이고 밀도 0.7인 dense 케이스에서 인접 리스트를 쓰면 한 노드의 이웃 탐색이 평균 350개로 커지고, BFS 1회 비용이 V²에 가까운 곡선으로 부풀 수 있다. 그래프 생성 직후 V, E, density를 찍는 계측이 가장 빠른 진단이다.
- 10
DFS와 BFS는 그래프를 걷는 두 기본 방식이다. DFS는 한 방향으로 최대한 깊이 들어갔다가 막히면 되돌아오므로 스택이나 재귀가 자연스럽고, BFS는 현재 노드의 모든 이웃을 먼저 방문한 뒤 다음 거리의 노드로 넘어가므로 큐가 필요하다. 비가중치 그래프에서 BFS가 최단 경로를 보장하는 이유는 레이어 단위로 탐색하기 때문이다. 시작 노드에서 거리 1인 노드를 모두 방문한 뒤에야 거리 2로 넘어가므로, 어떤 노드에 처음 도달한 시점이 곧 최단 거리다. DFS는 처음 도달한 경로가 최단이라는 보장이 없다.
- 11
트리와 그래프의 경계도 실무에서 중요하다. 트리는 사이클이 없는 그래프이고 부모에서 자식으로 가는 방향이 명확하므로 많은 경우 visited 체크 없이도 탐색할 수 있다. 하지만 일반 그래프에서는 사이클이 가능하므로 visited를 확인하지 않으면 무한 루프가 생긴다. 특히 BFS에서 visited 처리 시점은 큐에 넣는 순간이어야 한다. 꺼낼 때 visited로 표시하면 이미 큐에 들어간 노드가 다시 들어갈 수 있고, 작은 그래프에서는 답이 맞아 단위 테스트가 통과하지만 큰 그래프에서는 큐 크기가 폭주해 OOM이나 TLE로 이어질 수 있다. 정상 BFS의 큐 길이는 V를 넘지 않는 방향으로 관리되어야 한다.
- 12
위상 정렬은 방향 비순환 그래프, 즉 DAG에서 노드를 의존성 순서대로 나열하는 알고리즘이다. A가 B에 의존한다면 B가 A보다 먼저 와야 하며, 이 정렬이 불가능하면 순환 의존성이 있다는 뜻이다. NestJS의 모듈 초기화 순서, npm과 yarn의 패키지 설치 순서, Terraform의 인프라 리소스 생성 순서가 모두 이 원리와 연결된다. 다만 위상 정렬 결과는 항상 하나로 고정되지 않는다. 진입 차수가 0인 노드가 여러 개이면 어느 것을 먼저 꺼내도 유효할 수 있고, JavaScript Object.keys()의 순회 특성과 그래프 구성 방식 때문에 같은 DAG라도 결과가 달라질 수 있다. 그래서 모듈 초기화 부수효과가 있는 테스트에서는 결정적 위상 정렬이 필요하다.
- 13
NestJS, AWS Step Functions, Terraform은 그래프가 직접 드러나는 사례다. NestFactory.create(AppModule)이 실행될 때 NestJS는 모듈과 프로바이더의 의존성 그래프를 구성하고, DFS로 순환 의존성을 감지한다. UserModule이 AuthModule을 import하고 AuthModule이 다시 UserModule을 import하면 Circular dependency detected 오류가 발생할 수 있으며, forwardRef()는 에지 방향을 지연 평가로 바꿔 사이클을 우회하는 기법으로 설명된다. AWS Step Functions의 상태 머신은 상태가 노드이고 전환이 에지인 DAG이며, Terraform은 plan 실행 시 리소스 의존성 그래프를 만들고 의존성이 없는 리소스를 병렬로 생성한다.
- 14
마지막으로 새 기술에서 트리와 그래프를 알아보는 질문은 네 가지로 정리할 수 있다. 요소 사이의 관계가 부모와 자식의 단방향이면 트리이고, 서로 임의로 참조할 수 있으면 그래프로 보는 편이 자연스럽다. 순서가 결과를 바꾸면 위상 정렬이나 우선순위 큐를 의심해야 한다. 사이클이 오류인지 정상 상태인지에 따라 DFS 사이클 감지와 visited 집합의 의미가 달라진다. 조회 빈도가 변경 빈도보다 압도적으로 높으면 정렬 배열이나 인덱스 구조가 유리하고, 변경도 잦으면 Red-Black 같은 자가 균형 트리가 안전하다. 정리하면 BST는 정렬된 탐색, Heap은 우선순위 접근, Graph는 관계 탐색을 효율적으로 처리한다.
같은 레이어
L10에서 이어 듣기
- 오디오 파일
- /podcasts/l10-tree-graph.mp3