2026.01.24자료구조

🌳 비선형 자료구조의 핵심 - 트리(Tree) 구조 완전 정복

배열, 스택, 큐 같은 자료구조가 데이터를 일렬로 세운 선형 구조였다면 오늘 다룰 트리(Tree)는 조금 다르다.

데이터를 계층적으로 쌓아 올리는 비선형 구조라 처음 접하면 다소 낯설게 느껴질 수 있지만 사실 트리는 우리가 매일 사용하는 파일 시스템, 웹 페이지의 HTML DOM, 데이터베이스 인덱스 등에 이미 깊숙이 자리 잡고 있다.

트리(Tree)란?

트리는 *노드(Node)들이 부모-자식 관계로 연결된 자료구조를 의미한다. 하나의 최상위 노드에서 시작해 아래로 가지가 뻗어나가는 형태를 가진다.

이런 구조 덕분에 트리는 단순히 데이터를 담는 그릇을 넘어 계층을 표현하거나 범위를 나누어 탐색할 때 강점을 가지게 된다.

트리를 이해하기 위해 필요한 용어부터 정리해보자.

*노드(Node) - 트리를 구성하는 하나의 데이터 단위
루트(Root) - 트리의 시작점, 가장 위에 있는 노드
부모/자식(Parent/Child) - 연결된 노드들 사이의 상하 관계
리프 노드(Leaf) - 자식이 없는, 트리의 끝부분에 위치한 노드
간선(Edge) - 노드와 노드를 잇는 선
레벨(Level) - 루트 노드(Level 0)를 시작으로 아래로 내려갈수록 1씩 증가하는 층을 의미
서브 트리(Subtree) - 전체 트리의 일부분을 떼어낸 작은 트리 구조, 모든 트리는 또 다른 서브 트리의 집합이라고 볼 수 있다.

트리의 3가지 핵심 특징

트리가 다른 자료구조와 구별되는 명확한 성질들을 정리해 보자.

1. 사이클(Cycle)이 없는 연결 그래프
트리의 가장 큰 규칙은 어떤 노드에서 출발해도 다시 자기 자신으로 돌아오는 경로가 없다는 점이다. 모든 노드는 단방향 혹은 계층적으로만 연결되어 있어 흐름이 명확하다.

2. 노드와 간선의 관계
트리 내의 노드 개수가 N개라면 노드들을 잇는 간선의 개수는 항상 N - 1개이다. 모든 자식 노드는 반드시 하나의 부모 노드와 연결되어야 하기 때문에 루트 노드를 제외한 나머지 노드 수만큼 간선이 존재하기 때문이다.

3. 단방향 계층 구조
모든 트리는 단 하나의 뿌리(Root)에서 시작하며 부모 노드는 하나지만 자식 노드는 여러 개가 존재할 수 있다. (반대로 자식 입장에서 부모는 오직 하나)

이런 특징들 덕분에 트리는 구조가 명확하고 탐색 경로가 예측 가능해진다. 데이터 사이의 충돌 걱정 없이 특정 데이터를 향해 최단 경로로 내려갈 수 있다.

이진 트리(Binary Tree)

트리 구조 중 실무에서 가장 빈번하게 사용되고 알고리즘 테스트에서도 자주 등장하는 형태가 바로 이진 트리이다.

이진 트리는 모든 노드가 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미한다. 자식 노드는 보통 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 구분한다.

왜 자식 수를 2개로 제한할까?
자식의 수를 제한하면 구조가 단순해져서 배열이나 연결 리스트로 구현하기가 매우 쉬워진다. 또한 '이진 탐색 트리' 처럼 데이터를 특정 규칙에 따라 배치할 수 있어 탐색 속도를 극대화 할 수 있다.

이진 트리는 그 형태에 따라 크게 세 가지로 나뉜다.

정 이진 트리 (Full Binary Tree) - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 구조
완전 이진 트리 (Complete Binary Tree) - 마지막 레벨을 제외하고 모든 노드가 채워져 있으며 노드가 왼쪽부터 순서대로 채워진 구조
포화 이진 트리 (Perfect Binary Tree) - 모든 레벨이 빈 공간 없이 꽉 채워진 완벽한 삼각형 형태

이진 트리 구현 (TypeScript)
실제 코드로 노드를 정의하면 다음과 같이 간단하게 표현할 수 있다.

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
  
  constructor(value: number) {
    this.value = value;
    this.left = null;  // 왼쪽 자식
    this.right = null; // 오른쪽 자식
  }
}

트리 순회(Tree Traversal)

선형 자료구조와 달리 트리는 비선형 구조이기 때문에 모든 노드를 어떤 순서로 방문할 것인가가 매우 중요하다. 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 나뉜다.

1. 깊이 우선 탐색 (DFS, Depth-First Search)
한 방향으로 최대한 깊숙이 내려갔다가 더 이상 갈 곳이 없으면 다시 돌아와 다른 방향으로 탐색하는 방식이다. 주로 재귀(Recursion)를 사용하여 구현한다.

전위 순회(Pre-order): 자신(Root) -> 왼쪽 -> 오른쪽
트리를 복사하거나 전위 표기법 연산 등에 사용된다.
중위 순회(In-order): 왼쪽 -> 자신(Root) -> 오른쪽
이진 탐색 트리(BST)에서 데이터를 오름차순으로 정렬된 상태로 가져올 때 사용된다.
후위 순회(Post-order): 왼쪽 -> 오른쪽 -> 자신(Root)
자식 노드부터 처리해야 하는 트리 삭제나 수식 트리(Expression Tree)의 계산에 활용된다.

2. 너비 우선 탐색 (BFS, Breadth-First Search)
깊게 내려가기보다 인접한 노드(같은 레벨)들을 먼저 방문하는 방식이다. 주로 큐(Queue) 자료구조를 사용하여 구현한다.

레벨 순회(Level-order): 위에서 아래로, 왼쪽에서 오른쪽으로 층별로 탐색
두 노드 사이의 최단 거리를 찾거나 계층 구조를 순차적으로 확인해야 할 때 사용한다.

트리의 시간 복잡도

트리 자료구조를 사용하는 가장 큰 이유는 결국 효율적인 탐색이다. 하지만 모든 트리가 항상 빠른 것은 아니다.

1. 일반적인 트리의 탐색: O(n)
규칙 없이 데이터가 들어간 일반적인 트리에서 특정 값을 찾으려면 최악의 경우 모든 노드를 다 찾아야 한다. 이때의 시간 복잡도는 배열과 다를 바 없는 O(n)이 된다.

2. 이진 탐색 트리(BST)의 탐색: O(log n)
데이터를 삽입할 때부터 부모보다 작으면 왼쪽, 크면 오른쪽과 같은 규칙을 지키면 이야기가 달라진다. 탐색을 한 번 진행할 때마다 확인해야 할 데이터의 양이 절반씩 줄어들기 때문이다. 이것이 우리가 트리 구조를 사용하는 궁극적인 목표이다.

3. 주의할 점: 편향 트리(Skewed Tree)
아무리 이진 탐색 트리라도 데이터가 한쪽 방향으로만 치우쳐서 들어오면 결국 연결 리스트와 다를 바 없는 선형 구조가 된다. 따라서 실제 현업이나 데이터베이스에서는 트리가 한쪽으로 쏠리지 않도록 스스로 균형을 잡는 AVL 트리나 Red-Black 트리, B-Tree 같은 심화 구조를 주로 사용한다.

트리의 활용 예시

트리는 현대 컴퓨팅 시스템의 근간을 이루고 있다.

1. 파일 시스템 (File System)
우리가 매일 사용하는 윈도우의 파일 탐색기나 맥의 Finder가 바로 트리 구조의 대표적인 예이다. C드라이브(Root) 아래에 여러 폴더(Internal Node)가 있고, 그 안에 더 이상 쪼개지지 않는 파일(Leaf Node)들이 존재하는 형태이다.

2. HTML DOM (Document Object Model)
웹 브라우저가 HTML 문서를 해석할 때도 트리 구조를 사용한다. <html> 태그를 루트로 하여 <head>, <body> 등의 자식 노드가 뻗어 나가는 형태이다. 우리가 JavaScript로 요소를 찾고 조작할 수 있는 이유도 DOM이 트리 구조로 설계되어 있기 때문이다.

3. 데이터베이스 인덱스 (B-Tree)
수백만 개의 데이터 중에서 원하는 정보를 순식간에 찾아낼 수 있는 비결은 바로 B-Tree 계층 구조에 있다. 데이터베이스는 트리 구조를 활용해 탐색 범위를 좁혀나가며 성능을 최적화한다.