[알고리즘] 22. 트리 기초

[알고리즘] 22. 트리 기초

지난 글에서는 힙(Heap)에 대해 정리했습니다. 이번 글에서는 자료구조에서 매우 중요한 개념인 트리(Tree)에 대해 알아보겠습니다.

트리는 데이터를 계층적으로 표현하는 자료구조입니다. 파일 시스템, 조직도, 댓글 구조, 카테고리, 이진 탐색 트리, 힙 등 다양한 곳에서 사용됩니다.

트리는 하나의 시작점에서 여러 데이터가 가지처럼 뻗어나가는 계층형 자료구조입니다.

---

1. 트리란?

트리는 노드들이 부모와 자식 관계로 연결된 자료구조입니다. 가장 위에는 하나의 시작 노드가 있고, 그 아래로 여러 노드가 이어집니다.

        A
      /   \
     B     C
    / \     \
   D   E     F

위 구조에서 A는 가장 위에 있는 노드입니다. B와 C는 A의 자식이고, D와 E는 B의 자식입니다.

트리는 이름처럼 나무를 뒤집어 놓은 모양과 비슷합니다. 알고리즘에서는 위에서 아래로 내려가며 데이터를 탐색하거나 처리하는 경우가 많습니다.

트리는 데이터를 위아래 관계로 표현할 때 사용하는 자료구조입니다.

---

2. 트리가 필요한 이유

배열이나 리스트는 데이터를 일렬로 저장합니다. 하지만 실제 문제에서는 데이터가 단순한 일렬 구조가 아닌 경우가 많습니다.

예를 들어 아래와 같은 데이터는 계층 구조를 가집니다.

• 폴더와 파일 구조
• 회사 조직도
• 게시글과 대댓글
• 상품 카테고리
• HTML 문서 구조
• 이진 탐색 트리
• 힙 자료구조

이런 구조는 단순 배열보다 트리로 표현하는 것이 훨씬 자연스럽습니다.

---

3. 트리의 기본 용어

트리를 이해하려면 몇 가지 기본 용어를 알아야 합니다. 처음에는 용어가 많아 보이지만, 구조를 보면 어렵지 않습니다.

용어	의미
노드(Node)	트리를 구성하는 각각의 데이터
간선(Edge)	노드와 노드를 연결하는 선
루트(Root)	트리의 가장 위에 있는 시작 노드
부모(Parent)	어떤 노드의 바로 위에 있는 노드
자식(Child)	어떤 노드의 바로 아래에 있는 노드
형제(Sibling)	같은 부모를 가진 노드
리프(Leaf)	자식이 없는 노드

트리 문제를 풀 때는 이 용어들이 자주 등장합니다. 특히 루트, 부모, 자식, 리프는 반드시 익숙해져야 합니다.

---

4. 루트 노드

루트 노드는 트리의 가장 위에 있는 시작 노드입니다. 트리는 보통 루트에서 시작해서 아래 방향으로 탐색합니다.

        A  ← 루트
      /   \
     B     C
    / \     \
   D   E     F

위 트리에서는 A가 루트 노드입니다. A는 부모가 없는 유일한 노드입니다.

루트 노드는 트리 탐색의 시작점이 되는 노드입니다.

---

5. 부모 노드와 자식 노드

트리에서는 노드들이 부모와 자식 관계로 연결됩니다. 어떤 노드의 바로 위에 있는 노드를 부모 노드라고 하고, 바로 아래에 있는 노드를 자식 노드라고 합니다.

        A
      /   \
     B     C
    / \
   D   E

위 구조에서 관계를 정리하면 다음과 같습니다.

노드	부모	자식
A	없음	B, C
B	A	D, E
C	A	없음
D	B	없음
E	B	없음

부모와 자식 관계를 이해하면 트리 탐색 흐름을 훨씬 쉽게 볼 수 있습니다.

---

6. 리프 노드

리프 노드는 자식이 없는 노드입니다. 트리의 끝에 있는 노드라고 생각하면 됩니다.

        A
      /   \
     B     C
    / \     \
   D   E     F

위 트리에서 D, E, F는 자식이 없습니다. 따라서 D, E, F는 리프 노드입니다.

리프 노드는 더 이상 아래로 내려갈 수 없는 끝 지점입니다. 트리 탐색 문제에서 리프 노드에 도착했을 때 결과를 계산하는 경우도 많습니다.

리프 노드는 자식이 없는 마지막 노드입니다.

---

7. 깊이와 높이

트리에서는 깊이(depth)와 높이(height)라는 개념도 자주 나옵니다.

용어	의미
깊이	루트에서 어떤 노드까지 내려간 거리
높이	어떤 노드에서 가장 아래 리프까지의 거리

예를 들어 아래 트리를 보겠습니다.

깊이 0:        A
             /   \
깊이 1:     B     C
           / \
깊이 2:   D   E

루트 A의 깊이는 0입니다. B와 C의 깊이는 1이고, D와 E의 깊이는 2입니다.

깊이는 루트에서 얼마나 내려왔는지를 나타냅니다.

---

8. 차수

차수는 어떤 노드가 가진 자식의 개수를 의미합니다.

        A
      /   \
     B     C
    / \
   D   E

위 트리에서 각 노드의 차수는 다음과 같습니다.

노드	자식 수	차수
A	B, C	2
B	D, E	2
C	없음	0
D	없음	0
E	없음	0

자식이 없는 리프 노드의 차수는 0입니다.

---

9. 이진 트리

이진 트리는 각 노드가 최대 2개의 자식만 가질 수 있는 트리입니다. 자식은 보통 왼쪽 자식과 오른쪽 자식으로 구분합니다.

        A
      /   \
     B     C
    / \     \
   D   E     F

위 트리는 각 노드가 최대 2개의 자식만 가지고 있으므로 이진 트리입니다.

이진 트리는 알고리즘에서 매우 자주 등장합니다. 대표적으로 이진 탐색 트리, 힙, 세그먼트 트리 등이 이진 트리 구조와 관련이 있습니다.

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다.

---

10. 트리와 그래프의 차이

트리는 그래프의 한 종류로 볼 수 있습니다. 하지만 일반적인 그래프와 비교했을 때 몇 가지 특징이 있습니다.

구분	트리	그래프
구조	계층 구조	자유로운 연결 구조
루트	보통 하나의 루트가 있음	루트가 없을 수 있음
사이클	사이클이 없음	사이클이 있을 수 있음
부모-자식	명확한 부모-자식 관계	부모-자식 관계가 없을 수 있음

트리의 중요한 특징은 사이클이 없다는 점입니다. 한 노드에서 출발해 다시 자기 자신으로 돌아오는 경로가 없습니다.

트리는 사이클이 없는 계층형 그래프라고 이해할 수 있습니다.

---

11. Java로 이진 트리 노드 만들기

이진 트리는 왼쪽 자식과 오른쪽 자식을 가지므로, Java에서는 클래스로 간단히 표현할 수 있습니다.

class TreeNode {
    String value;
    TreeNode left;
    TreeNode right;

    TreeNode(String value) {
        this.value = value;
    }
}

value는 노드의 값이고, left는 왼쪽 자식, right는 오른쪽 자식을 의미합니다.

이 클래스를 이용해 간단한 이진 트리를 만들 수 있습니다.

TreeNode root = new TreeNode("A");

root.left = new TreeNode("B");
root.right = new TreeNode("C");

root.left.left = new TreeNode("D");
root.left.right = new TreeNode("E");

위 코드는 다음 트리를 만듭니다.

        A
      /   \
     B     C
    / \
   D   E

---

12. 트리 순회란?

트리 순회는 트리의 모든 노드를 일정한 순서로 방문하는 것입니다. 배열은 앞에서 뒤로 순회하면 되지만, 트리는 가지가 나뉘어 있기 때문에 방문 순서를 정해야 합니다.

이진 트리에서 자주 나오는 순회 방식은 다음과 같습니다.

순회 방식	방문 순서
전위 순회	현재 노드 → 왼쪽 → 오른쪽
중위 순회	왼쪽 → 현재 노드 → 오른쪽
후위 순회	왼쪽 → 오른쪽 → 현재 노드

이번 글에서는 가장 기본이 되는 전위 순회만 간단히 보겠습니다.

---

13. 전위 순회 예제

전위 순회는 현재 노드를 먼저 방문하고, 그다음 왼쪽 자식과 오른쪽 자식을 방문합니다.

        A
      /   \
     B     C
    / \
   D   E

전위 순회 결과는 다음과 같습니다.

A → B → D → E → C

Java 코드로 작성하면 다음과 같습니다.

public static void preorder(TreeNode node) {
    if (node == null) {
        return;
    }

    System.out.println(node.value);

    preorder(node.left);
    preorder(node.right);
}

현재 노드를 출력한 뒤 왼쪽 자식, 오른쪽 자식을 재귀적으로 방문합니다.

트리 순회는 재귀와 함께 자주 사용됩니다.

---

14. 트리의 간선 수

트리에서 노드가 N개라면 간선의 수는 항상 N - 1개입니다.

예를 들어 노드가 5개인 트리를 보겠습니다.

        A
      /   \
     B     C
    / \
   D   E

노드는 A, B, C, D, E로 총 5개입니다. 간선은 A-B, A-C, B-D, B-E로 총 4개입니다.

노드 수: 5
간선 수: 4
간선 수 = 노드 수 - 1

이 규칙은 트리 문제에서 자주 활용됩니다.

트리는 N개의 노드를 가지면 항상 N - 1개의 간선을 가집니다.

---

15. 트리에서 자주 하는 실수

트리 문제를 풀 때는 아래 실수를 조심해야 합니다.

• 루트 노드를 제대로 정하지 않는 경우
• 부모와 자식 관계를 반대로 이해하는 경우
• 리프 노드 조건을 잘못 판단하는 경우
• 깊이와 높이 개념을 헷갈리는 경우
• 트리에 사이클이 있다고 생각하는 경우
• 재귀 순회에서 종료 조건을 빠뜨리는 경우
• null 노드 처리를 하지 않는 경우

특히 재귀로 트리를 순회할 때는 node가 null인지 확인하는 종료 조건이 중요합니다.

if (node == null) {
    return;
}

트리 재귀 탐색에서는 종료 조건을 먼저 작성하는 습관이 좋습니다.

---

16. 정리

이번 글에서는 트리 기초에 대해 정리했습니다.

• 트리는 데이터를 계층적으로 표현하는 자료구조이다.
• 트리는 노드와 간선으로 구성된다.
• 가장 위의 노드를 루트 노드라고 한다.
• 부모, 자식, 형제, 리프 노드 관계를 이해해야 한다.
• 깊이는 루트에서 특정 노드까지의 거리이다.
• 이진 트리는 각 노드가 최대 2개의 자식을 가지는 트리이다.
• 트리는 사이클이 없는 계층형 구조이다.
• 노드가 N개인 트리는 간선이 N - 1개이다.
• 트리 순회는 재귀와 함께 자주 사용된다.

트리는 이후에 배울 그래프, DFS, BFS, 이진 탐색 트리, 힙 같은 개념과도 연결됩니다. 처음에는 용어가 많아 보이지만, 부모와 자식 관계를 기준으로 차근차근 보면 충분히 이해할 수 있습니다.

트리의 핵심은 하나의 루트에서 시작해 부모와 자식 관계로 데이터가 뻗어나가는 구조를 이해하는 것입니다.

---

다음 글 예고

다음 글에서는 그래프 기초에 대해 알아보겠습니다.

정점과 간선, 방향 그래프와 무방향 그래프, 인접 행렬과 인접 리스트의 기본 개념을 예제로 정리해보겠습니다.