트리 자료구조 - 계층 구조의 표현 - soo:bak

작성일 :

트리란?

트리(Tree)는 계층적 구조를 표현하는 비선형 자료구조입니다.

하나의 루트 노드에서 시작하여 여러 자식 노드로 뻗어나가는 형태입니다.

그래프 관점에서는 사이클이 없는 연결 그래프로 정의할 수 있습니다.


컴퓨터의 파일 시스템을 생각해보면 이해가 쉽습니다.

최상위에 루트 폴더가 있고, 그 아래에 여러 폴더와 파일이 있습니다.

각 폴더는 다시 하위 폴더와 파일을 가질 수 있습니다.


파일 시스템 외에도 회사의 조직도, HTML 문서의 DOM 구조, 가계도 등이 트리 구조입니다.


트리 용어

트리를 다루기 위해 알아야 할 기본 용어들입니다.

1
2
3
4
5

        A          ← 루트(Root): 최상위 노드
       / \
      B   C        ← A의 자식(Child)
     /|   |\
    D E   F G      ← 리프(Leaf): 자식이 없는 노드


노드 관계

용어 설명
루트(Root) 트리의 최상위 노드. 부모가 없음
부모(Parent) 특정 노드의 바로 위 노드
자식(Child) 특정 노드의 바로 아래 노드
형제(Sibling) 같은 부모를 가진 노드들
리프(Leaf) 자식이 없는 노드 (단말 노드)
내부 노드 자식이 있는 노드 (리프가 아닌 노드)
조상(Ancestor) 루트까지 경로에 있는 모든 노드
자손(Descendant) 특정 노드의 서브트리에 있는 모든 노드


구조 용어

용어 설명
간선(Edge) 노드와 노드를 연결하는 선
경로(Path) 한 노드에서 다른 노드까지 거치는 노드들의 순서
깊이(Depth) 루트에서 특정 노드까지의 간선 수 (루트의 깊이는 0)
높이(Height) 특정 노드에서 가장 먼 리프까지의 간선 수
레벨(Level) 같은 깊이에 있는 노드들의 집합
서브트리 특정 노드를 루트로 하는 부분 트리


트리의 속성

트리는 사이클이 없는 연결 그래프로 볼 수 있기 때문에, n 개의 노드를 가진 트리는 항상 n - 1 개의 간선을 가집니다.

또한, 임의의 두 노드 사이에는 유일한 경로가 존재하게 됩니다.


이진 트리 (Binary Tree)

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

왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 구분합니다.


이진 트리는 가장 기본적이면서도 중요한 트리 형태입니다.

이진 탐색 트리, 힙, 세그먼트 트리 등 많은 자료구조가 이진 트리를 기반으로 합니다.


이진 트리의 종류

정 이진 트리 (Full Binary Tree)

모든 노드가 0개 또는 2개의 자식을 가집니다. 자식이 1개인 노드가 없습니다.

1
2
3
4
5

      A
     / \
    B   C
   / \
  D   E


완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 순서대로 채워집니다.

배열로 구현하기에 적합합니다.

1
2
3
4
5

      A
     / \
    B   C
   / \  /
  D  E F


포화 이진 트리 (Perfect Binary Tree)

모든 레벨이 완전히 채워진 이진 트리입니다. 높이가 h인 포화 이진 트리는 2^(h+1) - 1개의 노드를 가집니다.

1
2
3
4
5

      A
     / \
    B   C
   /\   /\
  D  E F  G


이진 트리 순회 (Traversal)

트리의 모든 노드를 특정 순서로 방문하는 방법입니다. 순회 방식에 따라 노드 방문 순서가 달라집니다.


전위 순회 (Preorder)

루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문합니다.

루트를 가장 먼저 방문하기 때문에 전위(前位)라고 합니다.

1
2
3
4
5
6
7
8

void preorder(Node* node) {
  if (node == nullptr)
    return;

  cout << node->val << " ";  // 1. 루트 방문
  preorder(node->left);       // 2. 왼쪽 서브트리
  preorder(node->right);      // 3. 오른쪽 서브트리
}


활용: 트리를 복사하거나, 전위 표기식을 출력할 때 사용합니다.


중위 순회 (Inorder)

왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문합니다.

이진 탐색 트리(BST)에서 중위 순회를 하면 오름차순 정렬 결과를 얻습니다.

1
2
3
4
5
6
7
8

void inorder(Node* node) {
  if (node == nullptr)
    return;

  inorder(node->left);        // 1. 왼쪽 서브트리
  cout << node->val << " ";  // 2. 루트 방문
  inorder(node->right);       // 3. 오른쪽 서브트리
}


활용: 이진 탐색 트리에서 정렬된 순서로 원소를 출력할 때 사용합니다.


후위 순회 (Postorder)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서로 방문합니다.

자식을 모두 처리한 후 부모를 처리합니다.

1
2
3
4
5
6
7
8

void postorder(Node* node) {
  if (node == nullptr)
    return;

  postorder(node->left);      // 1. 왼쪽 서브트리
  postorder(node->right);     // 2. 오른쪽 서브트리
  cout << node->val << " ";  // 3. 루트 방문
}


활용: 트리를 삭제하거나, 서브트리의 결과를 먼저 계산해야 할 때 사용합니다.


레벨 순회 (Level Order)

레벨별로 왼쪽에서 오른쪽으로 방문합니다.

BFS(너비 우선 탐색) 를 사용합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void levelOrder(Node* root) {
  if (root == nullptr)
    return;

  queue<Node*> q;
  q.push(root);

  while (!q.empty()) {
    Node* node = q.front();
    q.pop();

    cout << node->val << " ";

    if (node->left)
      q.push(node->left);
    if (node->right)
      q.push(node->right);
  }
}


순회 예시

1
2
3
4
5

      1
     / \
    2   3
   / \
  4   5
순회 방식 방문 순서 설명
전위 1 → 2 → 4 → 5 → 3 루트 먼저
중위 4 → 2 → 5 → 1 → 3 왼쪽, 루트, 오른쪽
후위 4 → 5 → 2 → 3 → 1 루트 마지막
레벨 1 → 2 → 3 → 4 → 5 위에서 아래로


트리 구현

포인터 기반 구현

동적으로 노드를 생성하여 연결합니다. 일반적인 이진 트리 구현에 사용됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct Node {
  int val;
  Node* left;
  Node* right;

  Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 트리 생성 예시
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);


배열 기반 구현

완전 이진 트리는 배열로 효율적으로 표현할 수 있습니다.

힙과 세그먼트 트리에서 주로 사용됩니다.


1-based indexing을 사용할 때 인덱스 규칙은 다음과 같습니다.

루트는 인덱스 1이고, 노드 i의 왼쪽 자식은 2×i, 오른쪽 자식은 2×i+1, 부모는 i/2입니다.

1
2
3
4
5
6
7

int tree[100];  // 인덱스 1부터 사용

tree[1] = 1;    // 루트
tree[2] = 2;    // 루트의 왼쪽 자식
tree[3] = 3;    // 루트의 오른쪽 자식
tree[4] = 4;    // 노드 2의 왼쪽 자식
tree[5] = 5;    // 노드 2의 오른쪽 자식


인접 리스트 구현

자식의 수가 정해지지 않은 일반 트리에 적합합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

vi children[100];  // children[i]: 노드 i의 자식들

void addChild(int parent, int child) {
  children[parent].push_back(child);
}

// 트리 순회
void dfs(int node) {
  cout << node << " ";
  for (int child : children[node])
    dfs(child);
}


트리의 활용

이진 탐색 트리 (BST)

왼쪽 서브트리 < 루트 < 오른쪽 서브트리 조건을 만족하는 트리입니다.

탐색, 삽입, 삭제가 평균 O(log n) 에 가능합니다. 다만, 한쪽으로 치우친 트리가 되면 O(n)까지 느려질 수 있어서, 균형 잡힌 트리(AVL, Red-Black Tree 등)가 사용됩니다.


힙 (Heap)

부모가 자식보다 항상 크거나(최대 힙) 작은(최소 힙) 완전 이진 트리입니다.

우선순위 큐 구현에 사용되며, 삽입과 삭제가 \(O(\log n)\)에 가능합니다.

참고 : 힙 정렬 - soo:bak


트라이 (Trie)

문자열 집합을 저장하는 트리입니다.

문자열 검색이 \(O(\text{문자열 길이})\)에 가능하며, 자동완성이나 사전 구현 등에 활용됩니다.


세그먼트 트리

구간 쿼리를 처리하는 트리입니다.

구간 합, 구간 최솟값/최댓값 등을 \(O(\log n)\)에 구할 수 있습니다.

참고 : 세그먼트 트리 - soo:bak


트리 문제 풀이 팁

재귀로 생각하기

트리 문제는 대부분 재귀로 풀 수 있습니다.

현재 노드에서 해야 할 일을 정의하고, 자식 노드에 대해 같은 함수를 호출합니다.

1
2
3
4
5
6
7
8
9
10

// 트리의 높이 구하기
int getHeight(Node* node) {
  if (node == nullptr)
    return -1;  // 빈 트리의 높이는 -1

  int leftHeight = getHeight(node->left);
  int rightHeight = getHeight(node->right);

  return max(leftHeight, rightHeight) + 1;
}


부모 정보 저장하기

루트에서 시작하는 문제가 아니라면, 부모 노드 정보를 저장해두면 편리합니다.

1
2
3
4
5
6
7
8
9

int parent[100];

void dfs(int node, int par) {
  parent[node] = par;
  for (int child : children[node]) {
    if (child != par)
      dfs(child, node);
  }
}


마무리

트리는 계층적 데이터를 표현하는 자료구조입니다.


순회 방식 순서 활용
전위 루트 → 왼쪽 → 오른쪽 트리 복사, 전위 표기식
중위 왼쪽 → 루트 → 오른쪽 BST 정렬 출력
후위 왼쪽 → 오른쪽 → 루트 트리 삭제, 서브트리 계산
레벨 위에서 아래로 BFS 기반 탐색


트리 문제는 재귀적 사고가 중요합니다.

현재 노드에서 무엇을 하고, 자식에게 무엇을 위임할지 생각하면 대부분의 문제를 풀 수 있습니다.


관련 문제

이 블로그의 다른 글