트리·순회·그래프 표현
트리의 형태와 순회 순서, 그래프의 저장 방식 및 BFS·DFS 탐색 원리를 익힌다.
트리의 구조와 기본 용어
트리(Tree)는 하나의 루트에서 시작해 부모와 자식 관계로 데이터를 계층화한 비선형 자료구조다. 그래프 관점에서는 연결되어 있고 사이클이 없는 무방향 그래프다. 따라서 비어 있지 않은 트리에서는 다음 성질이 성립한다.
- 노드가
n개이면 간선은n - 1개다. - 서로 다른 두 노드 사이의 단순 경로는 정확히 하나다.
- 루트를 제외한 모든 노드는 부모를 정확히 하나 가진다.
- 여러 트리가 서로 연결되지 않은 집합은 포리스트(Forest)라고 한다.
| 용어 | 의미 |
|---|---|
| 루트(root) | 부모가 없는 시작 노드 |
| 부모·자식(parent·child) | 간선으로 직접 연결된 위·아래 단계의 노드 |
| 형제(sibling) | 같은 부모를 가진 노드 |
| 조상·후손(ancestor·descendant) | 부모 방향 또는 자식 방향으로 경로를 따라 만나는 노드 |
| 내부 노드(internal node) | 자식이 하나 이상 있는 노드 |
| 잎 노드(leaf node) | 자식이 없는 노드. 단말 노드라고도 한다. |
| 서브트리(subtree) | 한 노드와 그 후손들로 이루어진 트리 |
| 노드의 차수 | 해당 노드가 가진 자식 수 |
| 트리의 차수 | 트리 안에 있는 노드 차수의 최댓값 |
트리의 노드 차수와 그래프의 정점 차수는 기준이 다르다. 루트가 있는 트리에서 노드 차수는 자식 수를 뜻하지만, 일반 그래프에서 정점 차수는 그 정점에 접속한 간선 수를 뜻한다.
노드가 n개인 트리는 간선이 n-1개이며, 간선 k개를 제거하면 k+1개의 트리로 분리된다. 더 일반적으로 n개 노드와 c개 연결 요소를 가진 포리스트의 간선 수는 n-c개다.
깊이·레벨·높이와 노드 수
이 이론에서는 다음 기준을 사용한다.
- 깊이(depth): 루트에서 해당 노드까지 지나가는 간선 수. 루트의 깊이는 0이다.
- 레벨(level):
깊이 + 1. 루트의 레벨은 1이다. - 트리의 높이(height): 트리 안에서 가장 큰 깊이. 노드 하나뿐인 트리의 높이는 0이다.
이진 트리에서 깊이가 d인 위치에 올 수 있는 최대 노드 수는 2^d다. 같은 내용을 레벨로 표현하면 레벨 L의 최대 노드 수는 2^(L - 1)이다.
- 높이가 간선 수
h로 주어질 때 최대 전체 노드 수:2^(h + 1) - 1 - 레벨 수가
H로 주어질 때 최대 전체 노드 수:2^H - 1 - 높이가
h인 이진 트리의 최소 노드 수:h + 1— 한쪽으로만 이어진 경우
예를 들어 루트를 레벨 1로 두고 레벨이 4개인 포화 이진 트리는 각 레벨에 1, 2, 4, 8개의 노드가 있으므로 전체 노드는 15개다. 같은 트리의 높이를 간선 수로 세면 3이다.
교재나 문제에 따라 루트의 높이·레벨 시작값을 다르게 정할 수 있다. 공식을 바로 적용하지 말고 루트를 0으로 세는지 1로 세는지 먼저 확인해야 한다.
이진 트리의 형태
이진 트리(Binary Tree)는 각 노드가 왼쪽 자식과 오른쪽 자식을 각각 최대 하나씩 가지는 트리다. 자식 수가 둘 이하라는 조건뿐 아니라 왼쪽과 오른쪽의 위치가 구분되는 순서 트리라는 점이 중요하다.
| 종류 | 조건 | 판별 기준 |
|---|---|---|
| 이진 트리 | 각 노드의 자식이 최대 2개 | 자식이 0개나 1개인 노드도 허용 |
| 정 이진 트리(full/proper) | 모든 노드의 자식 수가 0개 또는 2개 | 자식이 정확히 1개인 노드가 없음 |
| 포화 이진 트리(perfect) | 모든 내부 노드의 자식이 2개이고 모든 잎이 같은 레벨 | 모든 레벨이 빈자리 없이 채워짐 |
| 완전 이진 트리(complete) | 마지막 레벨을 제외한 모든 레벨이 가득 차고, 마지막 레벨은 왼쪽부터 연속해 채워짐 | 중간 빈칸 뒤에 노드가 나오면 완전 이진 트리가 아님 |
| 편향 이진 트리(skewed) | 내부 노드가 주로 한쪽 자식만 가짐 | 연결 리스트처럼 한 방향으로 길어질 수 있음 |
포화 이진 트리는 정 이진 트리이면서 완전 이진 트리다. 그러나 완전 이진 트리가 항상 포화인 것은 아니며, 정 이진 트리가 항상 완전인 것도 아니다.
정 이진 트리에서 내부 노드 수를 I, 잎 노드 수를 L이라고 하면 L = I + 1이 성립한다. 전체 노드 수는 2I + 1, 또는 2L - 1이다.
영문 full, perfect, complete의 번역은 교재마다 다르게 쓰이는 경우가 있다. 명칭만 암기하기보다 자식 수, 모든 레벨의 충족 여부, 마지막 레벨의 왼쪽 채움 여부를 기준으로 판단한다.
완전 이진 트리의 배열 표현
완전 이진 트리는 중간 빈칸 없이 배열에 저장하기 쉽다. 인덱스 기준을 먼저 확인해야 한다.
| 인덱스 기준 | 부모 | 왼쪽 자식 | 오른쪽 자식 |
|---|---|---|---|
| 1부터 시작 | floor(i / 2) | 2i | 2i + 1 |
| 0부터 시작 | floor((i - 1) / 2) | 2i + 1 | 2i + 2 |
계산한 자식 인덱스가 마지막 원소의 인덱스를 넘으면 해당 자식은 존재하지 않는다. 1부터 시작하는 배열에서 루트는 인덱스 1이며 부모가 없다.
트리 순회
전위는 루트 먼저, 중위는 왼쪽 다음 루트, 후위는 두 서브트리 다음 루트를 방문한다.
순회(Traversal)는 트리의 모든 노드를 정해진 규칙으로 한 번씩 처리하는 과정이다. 전위·중위·후위 순회는 왼쪽 서브트리를 오른쪽 서브트리보다 먼저 방문한다는 점은 같고, 루트를 언제 처리하는지가 다르다. 중위 순회는 왼쪽과 오른쪽이 구분되는 이진 트리에 적용한다.
다음 트리를 A(B(D,E), C(F,G))로 나타내자.
| 순회 | 규칙 | 방문 결과 |
|---|---|---|
| 전위 순회(preorder) | 루트 → 왼쪽 → 오른쪽 | A B D E C F G |
| 중위 순회(inorder) | 왼쪽 → 루트 → 오른쪽 | D B E A F C G |
| 후위 순회(postorder) | 왼쪽 → 오른쪽 → 루트 | D E B F G C A |
| 레벨 순회(level-order) | 깊이가 작은 노드부터, 같은 레벨은 왼쪽부터 | A B C D E F G |
전위·중위·후위는 깊이 우선 방식으로 재귀 호출이나 스택을 이용해 구현할 수 있다. 레벨 순회는 루트에서 가까운 노드부터 처리하는 너비 우선 방식이며 일반적으로 큐를 이용한다.
순회 결과를 역으로 읽는 법
- 전위 순회의 첫 노드는 전체 트리의 루트다.
- 후위 순회의 마지막 노드는 전체 트리의 루트다.
- 중위 순회에서 루트의 왼쪽에 있는 값들은 왼쪽 서브트리, 오른쪽 값들은 오른쪽 서브트리에 속한다.
- 노드 값이 모두 다르면
전위 + 중위또는후위 + 중위결과로 이진 트리를 유일하게 복원할 수 있다. 전위 + 후위만으로는 일반적인 이진 트리를 항상 유일하게 복원할 수 없다.
이진 탐색 트리(Binary Search Tree, BST)를 중위 순회하면 키가 정렬된 순서로 나온다. 일반 이진 트리의 중위 순회 결과까지 항상 정렬되는 것은 아니다.
노드가 n개이면 모든 노드를 한 번씩 방문하므로 각 순회의 시간 복잡도는 O(n)이다. 재귀적인 깊이 우선 순회는 트리 높이에 비례한 호출 스택을 사용하고, 레벨 순회는 방문을 기다리는 노드를 큐에 저장한다.
그래프의 구성과 종류
그래프(Graph)는 정점 집합 V와 정점 사이의 관계를 나타내는 간선 집합 E로 구성하며 G = (V, E)로 나타낸다.
| 종류 | 간선의 의미 | 핵심 판별 |
|---|---|---|
| 무방향 그래프 | 두 정점의 순서가 없는 연결 | A-B와 B-A는 같은 간선 |
| 방향 그래프 | 출발 정점과 도착 정점이 있는 연결 | A→B와 B→A는 서로 다른 간선 |
| 가중 그래프 | 간선에 거리·비용 같은 값이 있음 | 연결 여부와 가중치를 함께 저장 |
| 단순 그래프 | 자기 루프와 평행 간선을 허용하지 않음 | 최대 간선 공식의 기본 전제 |
무방향 그래프에서 정점의 차수(degree)는 그 정점에 접속한 간선 수다. 모든 정점 차수의 합은 2|E|다. 방향 그래프에서는 들어오는 간선 수를 진입 차수(in-degree), 나가는 간선 수를 진출 차수(out-degree)라고 한다.
- 모든 진입 차수의 합:
|E| - 모든 진출 차수의 합:
|E|
단순 그래프의 최대 간선 수
정점이 n개이고 자기 루프와 평행 간선이 없다고 하자.
| 그래프 | 최대 간선 수 | 이유 |
|---|---|---|
| 무방향 단순 그래프 | n(n - 1) / 2 | 서로 다른 두 정점의 조합 수 |
| 방향 단순 그래프 | n(n - 1) | 출발·도착의 순서가 있는 정점 쌍 수 |
정점 6개의 무방향 단순 그래프는 최대 6 × 5 / 2 = 15개의 간선을, 방향 단순 그래프는 최대 6 × 5 = 30개의 간선을 가진다. 자기 루프를 허용하거나 같은 정점 쌍 사이에 여러 간선을 허용하면 이 공식은 그대로 적용되지 않는다.
트리는 정점이 n개이고 간선이 n - 1개인 연결 무방향 그래프다. 단순히 간선 수가 n - 1개라는 사실만으로는 트리라고 확정할 수 없고, 연결되어 있거나 사이클이 없다는 조건을 함께 확인해야 한다.
인접 행렬과 인접 리스트
다음 무방향 그래프를 예로 들자.
- 정점:
A, B, C, D - 간선:
A-B,A-C,B-D
인접 행렬
행 정점과 열 정점 사이에 간선이 있으면 1, 없으면 0을 저장한다.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 0 |
| D | 0 | 1 | 0 | 0 |
무방향 그래프의 인접 행렬은 주대각선을 기준으로 대칭이다. 자기 루프가 없으면 주대각선 값은 0이다. 방향 그래프에서는 A[i][j]를 정점 i에서 j로 가는 간선으로 정의할 때 행의 합은 진출 차수, 열의 합은 진입 차수가 된다.
가중 그래프는 1 대신 간선의 가중치를 저장할 수 있다. 이때 가중치 0인 간선이 가능하다면 0을 무조건 “간선 없음”으로 사용해서는 안 되며 별도의 표시 규칙이 필요하다.
인접 리스트
각 정점마다 직접 연결된 이웃 정점만 저장한다.
A: B, C
B: A, D
C: A
D: B
무방향 그래프에서는 하나의 간선이 양쪽 정점의 리스트에 각각 한 번씩 나타난다. 예를 들어 A-B는 A의 리스트에도, B의 리스트에도 저장된다.
표현 방식 비교
| 기준 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 저장 공간 | O(V²) | O(V + E) |
u-v 간선 존재 확인 | O(1) | 일반적인 리스트에서는 O(deg(u)) |
정점 u의 모든 이웃 확인 | O(V) | O(deg(u)) |
| 적합한 그래프 | 간선이 많은 밀집 그래프 | 간선이 적은 희소 그래프 |
| 무방향 그래프 특징 | 행렬이 대칭 | 각 간선을 양쪽 리스트에 저장 |
인접 행렬은 정점 수만으로 공간이 정해지므로 간선이 적어도 O(V²)를 사용한다. 인접 리스트는 실제 간선 중심으로 저장하므로 희소 그래프에서 공간을 절약하고 이웃 정점을 빠르게 순회할 수 있다.
그래프의 너비 우선 탐색과 깊이 우선 탐색
너비 우선 탐색(BFS)은 큐를 사용하여 먼저 발견한 정점부터 이웃을 탐색한다. 중복 등록을 막으려면 큐에 넣는 시점에 방문 표시하는 구현을 사용할 수 있다. 깊이 우선 탐색(DFS)은 한 이웃을 선택해 끝까지 내려간 뒤 되돌아와 다른 이웃을 탐색하며 재귀 또는 스택으로 구현한다. 하나의 유일한 순서를 묻는 문제에는 시작 정점과 이웃 선택 순서를 함께 제시해야 한다. 무방향 간선은 양 끝의 이웃 목록에 모두 반영한다.
사이클이 있는 그래프에서는 방문 표시를 확인하여 이미 방문한 정점으로 재귀 호출을 반복하지 않는다.