[자료구조] Tree (1): 트리란 무엇인가?

프로그래밍을 학습하다 보면, 데이터를 구조화하여 저장하고 효율적으로 탐색·수정·삭제할 수 있는 다양한 방식들을 접하게 된다. 그중에서도 Tree(트리)는 복잡한 데이터 간의 관계를 계층적으로 표현하며, 빠른 탐색과 정렬, 분류 작업에 강력한 성능을 발휘하는 중요한 자료구조이다.

 

이 글은 건국대학교 2025-1학기 자료구조 수업에서 배운 내용을 바탕으로, Tree에 대한 핵심 개념을 정리한 복습 노트이다. 단순한 이론 암기를 넘어서, 코드나 시각 자료를 함께 활용하여 실제 구현과 동작 흐름까지 체감할 수 있도록 구성하였다. 트리의 기본 구조부터 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), 균형 이진 탐색 트리(Balanced BST), 그리고 AVL 트리까지 다양한 변형과 그 특징을 수업에서 다룬 순서대로 정리할 예정이다.

 

자료구조는 한 번 제대로 이해하고 넘어가면 이후의 알고리즘 문제 풀이나 코딩 테스트 및 인터뷰에서 강력한 무기가 된다. 이번 복습을 통해 트리의 기초부터 고급 응용까지 꿰뚫어보는 계기가 되기를 바란다.

---

1. 트리(Tree)란 무엇인가?

트리의 기본 개념

트리(Tree)는 계층적(hierarchical)인 구조를 가진 비선형(Non-linear) 데이터 구조이다. 이는 선형 구조인 배열(array), 연결 리스트(linked list)와는 구별되는 중요한 특징이다.

(정의: 트리는 노드들의 집합으로 이루어진 구조이며, 각 노드는 자식 노드들을 가질 수 있다. 이러한 관계를 통해 트리는 계층적인 데이터를 표현할 수 있다.)

트리의 구조

 

트리는 왜 Linked List와 유사하다고 하는가?

강의 슬라이드에서는 트리를 "Linked List와 유사한 데이터 구조"라고 설명하고 있다. 이는 트리도 포인터를 이용해 노드를 연결하기 때문이다. 하지만 중요한 차이점이 있다.

비교 항목	Linked List	Tree
구조	선형 구조 (linear)	비선형 구조 (non-linear)
다음 노드	하나만 가리킴	여러 개를 가리킬 수 있음
연결 방식	순차적으로 연결	계층적으로 연결

 

즉, linked list는 하나의 노드가 오직 하나의 다음 노드만 가리키는 반면, 트리는 하나의 노드가 여러 자식 노드를 가리킬 수 있는 구조이다.

 

트리는 비선형 구조이다

비선형(Non-linear) 구조란, 데이터가 단순히 일렬로 나열되는 것이 아니라 여러 방향으로 뻗어나갈 수 있는 구조를 말한다. 트리는 이러한 특성을 바탕으로 복잡한 관계를 표현할 수 있다.

 

예를 들어, 기업의 조직도, 파일 시스템, 족보, HTML DOM 트리 등이 트리 구조의 예시이다.

 

강의 슬라이드에서 강조한 주요 특징은 다음과 같다:

• 각 노드가 하나가 아닌 여러 개의 다음 노드를 가리킬 수 있다.
• 트리는 계층적 속성(hierarchical property)을 가지며, 구조적으로는 사이클이 없는 방향 그래프(DAG)의 일종이다.

 

트리의 구성 요소

트리를 이해하기 위해 반드시 숙지해야 할 핵심 용어는 다음과 같다.

용어	설명
Node	트리의 기본 단위로, 하나의 데이터를 포함한다.
Root	트리의 시작점이 되는 최상위 노드이다.
Parent	다른 노드를 가리키는 노드이다.
Child	부모 노드에 의해 가리켜지는 노드이다.
Leaf	자식 노드가 없는, 즉 더 이상 분기하지 않는 노드이다.
Sibling	동일한 부모를 가진 노드들이다.
Subtree	어떤 노드를 루트로 하는 하위 트리이다.
Edge	노드 간의 연결선을 의미한다.
Depth	루트 노드에서 특정 노드까지의 거리(간선 수)이다.
Height	특정 노드에서 가장 깊은 리프 노드까지의 거리이다.

 

이러한 용어들은 이후 트리의 종류, 탐색, 연산 등에 있어 반복적으로 사용되므로 반드시 정확하게 이해하고 넘어가야 한다.

 

트리의 활용 사례

트리는 현실 세계의 다양한 계층 구조를 표현하는 데 매우 적합하며, 다음과 같은 분야에서 널리 활용된다.

• 파일 시스템: 폴더와 파일 간의 포함 관계를 표현
• 웹 문서(DOM): HTML 요소들이 트리 구조로 표현됨
• 데이터베이스 인덱스: B-Tree, B+Tree 등
• AI 및 게임: 상태 공간 탐색 트리 (예: 미니맥스)
• 컴파일러: 구문 분석 트리(Parse Tree)
• 운영체제: 프로세스 간의 부모-자식 관계 표현

 

정리

• 트리는 하나의 노드가 여러 자식 노드를 가질 수 있는 비선형 데이터 구조이다.
• 트리는 계층적 관계를 표현하는 데에 효과적이며, 다양한 분야에서 폭넓게 활용된다.
• linked list와는 구조적으로 유사하지만, 트리는 하나 이상의 자식 노드를 가질 수 있다는 점에서 더 복잡하고 표현력이 크다.
• 트리를 구성하는 다양한 용어는 후속 학습에서 계속 사용되므로 확실히 익혀두는 것이 중요하다.

---

 

트리는 비선형 자료구조 중에서도 특히 다양한 응용 분야에서 두루 사용되는 중요한 개념이다. 계층적인 구조를 바탕으로 복잡한 데이터 간의 관계를 효과적으로 표현할 수 있고, 탐색이나 삽입, 삭제와 같은 연산도 효율적으로 수행할 수 있다. 이 글에서는 트리의 기본 개념부터 비선형 구조로서의 특징, 트리와 연결 리스트의 차이점, 그리고 구성 요소와 활용 사례까지 전반적인 기초 내용을 정리하였다.

 

트리는 자료구조의 중추적인 개념 중 하나로, 이후 학습하게 될 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), AVL 트리 등의 기반이 된다. 따라서 이번 내용을 정확히 이해해두는 것이 앞으로의 학습에 있어 매우 중요한 출발점이 된다.

 

다음 게시글에서는 트리에서 자주 사용되는 용어들, 예를 들어 루트, 노드, 간선, 서브트리, 레벨(Level) 등의 개념을 보다 구체적으로 정리하고, 실제 트리 구조에서 이러한 용어들이 어떻게 사용되는지를 살펴볼 예정이다. 본격적인 트리의 구현과 탐색을 이해하기 위해 꼭 알아두어야 할 핵심 개념들이니, 이어지는 글도 함께 읽어보기를 권한다.