최종수정: 24-09-02
업로드: 26-10-26
트리Tree는 가계도를 닮은 자료 구조다. 부모 노드 밑에 자식 노드들이 붙고, 그 자식 노드들에 또 자식 노드들의 자식 노드들이 붙는 식으로 연결되는 자료 구조다. 다만 트리는 순환적으로 연결되지 않는다. 따라서 위계질서hierarchy가 있는 곳을 자료구조 형태로 표현할 때 유용하다.
회사의 조직도나 책의 목차, RPG 게임의 스킬트리 같은 것이 트리에 해당한다. 컴퓨터 과학에의 응용도 많은 편이다. 운영체제의 파일 시스템, HTML/XML의 DOM이 직접적인 트리 구조를 가진다. DBMS나 검색 엔진에서 트리 구조를 활용하는 경우도 많다.
트리는 뿌리Root, 가지Branch, 잎Leaf이라는 구성 요소로 되어 있다. 각각의 노드에 차이는 없다. 위치에 따라서 맨 위의 노드(부모가 없는 노드)는 뿌리, 맨 아래의 노드(자식이 없는 노드)는 잎, 그리고 뿌리와 잎 사이에 위치한 모든 노드는 가지로 불릴 뿐이다.
지엽적으로는 부모Parent, 형제Sibling, 자식Children으로 노드를 구분할 수도 있다. 가지 혹은 뿌리가 부모 노드가 된다. 부모 노드가 된 노드의 자식들은 서로간에 모두 형제 관계를 갖는다.
트리에는 경로Path와 길이Length라는 개념이 존재한다. 경로는 시작점이 되는 노드에서 목적지가 되는 노드까지 거치는 노드의 순서를 일컫는다. A 노드에서 Z 노드까지 가는 데에 C, F, L, Q를 거쳐야 한다면 경로는 'A, C, F, L, Q, Z'가 된다(자신과 목적지를 포함한다). 이 경로의 길이는 5가 된다(자기 자신을 제외한다).
깊이Depth, 레벨Level, 높이Height라는 개념도 있다. 뿌리 노드에서 목적지 노드까지 도달하는 데 필요한 경로의 길이를 깊이라고 한다. 레벨은 깊이가 같은 노드들의 집합이다. 조직도로 따지자면 (공석이 없고 균일한 조직도를 갖는 조직의 경우) 같은 직급에 해당될 것이다. 높이는 가장 낮은 곳에 있는 잎부터 트리까지의 길이를 뜻한다. 그러므로 높이는 가장 깊은 곳의 깊이와 동일하다.
차수Degree는 기준이 되는 노드가 지닌 자식 노드의 개수를 나타낸다.
트리를 시각화하여 표현할 때는 그림을 그릴 수 있다. 그러나 중첩된 괄호Nested Parenthesis나 중첩된 집합Nested Set, 혹은 들여쓰기Indentation로 표현하는 것도 가능하다. 이는 시각화의 목적에 따라 달라지는 것이고 자료 구조에는 영향을 미치지 않으므로 가볍게 찾아보는 정도로 넘어가자.
노드를 서로 연결하는 데에는 두 가지 방법이 있다. N-링크N-Link 방식은 각각의 노드가 자식 노드의 주소를 전부 가진다. 조직도를 그리는 것과 비슷하여 쓸만하다고 생각할 수도 있으나 노드마다 차수가 다를 수 있는 트리에는 효율적이지 않다(낭비가 심할 것이다).
두 번째 방법은 왼쪽 자식-오른쪽 형제 표현법이다. 말 그대로 노드는 자신의 맨 왼쪽 자식의 주소와 오른쪽 형제의 주소만을 데이터로 갖는다. 어떤 노드의 세 번째 자식을 찾으려면 왼쪽 자식의 주소를 알아내 이동한 후 그 노드의 오른쪽 형제 주소로 이동하는 절차를 두 번 반복하면 된다. 검색은 조금 복잡해진 느낌이지만 트리의 형태에 무관하게 유연한 대처가 가능하다는 것이 왼쪽 자식-오른쪽 형제 표현법의 장점이다.
용어들 설명이 길었지만 ADT는 간단하다. 삽입만 있으면 된다.
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct _TreeNode
{
struct _TreeNode* LeftChild;
struct _TreeNode* RightSibling;
ElemType Data;
} TreeNode;
TreeNode* CreateNode( ElemType data )
{
TreeNode* NewNode = (TreeNode*)malloc( sizeof( TreeNode ) );
NewNode->Data = data;
NewNode->LeftChild = NULL;
NewNode->RightSibling = NULL;
return NewNode;
}
void DestroyNode( TreeNode* N )
{
free( N );
}
void DestroyTree( TreeNode* Root )
{
if ( Root->RightSibling != NULL )
DestroyNode( Root->RightSibling );
if ( Root->LeftChild != NULL )
DestroyNode( Root->LeftChild );
Root->LeftChild = NULL;
Root->RightSibling = NULL;
DestroyNode( Root );
}
void AppendChildNode( TreeNode* Parent, TreeNode* NewNode )
{
if ( Parent->LeftChild == NULL )
Parent->LeftChild = NewNode;
else
{
TreeNode* TmpNode = Parent->LeftChild;
while ( TmpNode->RightSibling != NULL )
TmpNode = TmpNode->RightSibling;
TmpNode->RightSibling = NewNode;
}
}
자식 노드가 많을 때는 AppendChildNode()의 빠른 실행을 위해 자료구조에 LastChild의 포인터 값을 저장하는 것도 좋다.
이진 트리는 특별한 종류의 트리로 하나의 노드가 가질 수 있는 자식 노드가 최대 2개로 제한되는 트리다. 특이한 제한사항을 가지고 있으나 수식 이진 트리Expression Binary Tree, 이진 탐색 트리Binary Search Tree 등 유용한 알고리즘의 기초가 되는 트리이므로 알아둘 필요가 있다.
여기에 속하는 트리 중 포화 이진 트리Perfect Binary Tree는 이름에서도 알 수 있듯이 완벽한 이진 트리로 모든 잎 레벨이 동일하며 모든 레벨이 또한 가득 차있다. 또는 이렇게 말할 수도 있다. 모든 노드는 두 개의 자식 노드를 갖고 잎 노드의 레벨(혹은 깊이)은 동일하다.
전 이진 트리Full Binary Tree는 포화 이진 트리와 이름이 비슷하나, 잎 노드를 제외한 모든 노드가 자식을 둘 씩 갖고 있는 트리를 지칭한다. 다른 말로 정의하면 모든 노드가 0개 혹은 2개의 자식 노드를 갖고 있을 트리에 해당한다.
그 전 단계라고도 할 수 있는 완전 이진 트리Complete Binary Tree는 트리 왼쪽부터 채워져야만 하는 트리로 마지막 레벨을 제외한 모든 레벨이 다 차있는 트리인데, 마지막 레벨의 노드들은 오른쪽만 차있으면 안 된다. 이 트리는 나중에 나올 자료구조 힙Heap과도 연관이 있다.
높이 균형 트리Height Balanced Tree는 뿌리 노드에서 보았을 때 왼쪽 하위 트리의 높이와 오른쪽 하위 트리의 높이가 2 이상 차이가 나지 않는 트리를 말한다. 완전 높이 균형 트리Completely Height Balanced Tree는 양쪽의 높이가 같은 트리를 뜻한다.
기본적인 트리의 특징을 살펴보았을 때와 마찬가지로, 개념어들보다 중요한 것은 따로 있다. 이진 트리에서는 '순회Traversal'라는 것이 중요하다. 트리 안에서 노드를 어떻게 이동하며 탐색할 것인가를 뜻하는 단어다. 순회법에는 총 세 가지, 전위 순회Preorder Traversal, 중위 순회Inorder Traversal, 후위 순회Postorder Traversal가 있다.
전위 순회는 뿌리 노드에서 시작해서 아래로 내려간다. 왼쪽 하위 트리를 먼저 방문하는데, 그 방문이 끝나면 오른쪽 트리를 방문하게 된다. 즉, 뿌리에서 시작해서 맨 왼쪽 잎까지 내려온 뒤에 우선순위를 따라 진행하게 되는데 우선순위는 자신, 왼쪽 노드, 오른쪽 노드 순으로 탐색을 해나가게 된다. 새로운 노드를 방문하면 항상 자신(그러나 새로운 노드에 들어왔다는 것은 부모 노드에서 이미 자신을 탐색했다는 뜻이기도 하다), 왼쪽 노드, 오른쪽 노드를 방문했는지 보고 방문이 안 된 우선순위가 높은 노드로 이동해 같은 작업을 반복한다.
중위 순회는 왼쪽 최하위 노드부터 시작해서 위로 올라간다. 이 경우 우선순위는 왼쪽 노드, 자신, 오른쪽 노드의 순서가 되게 된다. 기준 노드에서 방문되지 않은 곳을 우선순위 순으로 탐색한다. 전위 순회는 매번 우선순위를 체크하는 반면 중위 순회는 기준 노드를 한 번 잡으면 거기서 방문하지 않은 노드를 차례로 방문하고 기준 노드를 이동시킨다.
후위 순회는 왼쪽 노드, 오른쪽 노드, 자신 순의 우선순위를 갖는다. 전위 순회와 마찬가지로 왼쪽 하위 노드 방문을 다 끝낸 뒤에 오른쪽 노드로 옮겨간다. 전위 순회와의 차이점은 모든 노드의 방문이 끝나야 마지막으로 뿌리 노드를 방문하게 된다는 것이다. 후위 순회도 중위 순회처럼 왼쪽 최하위 노드에서 시작하기 때문이다. 전위 순회의 경우 시작부터 뿌리 노드를 방문한다.
이 외에도 층별 순회Level-order Traversal도 있다. 위쪽 노드들부터 왼쪽 노드에서 오른쪽 노드로 차례대로 방문하는 방식이다.
설명이 조금 복잡하지만 재귀를 중심으로 짜여진 구현 코드를 보면 좀 더 명확하다. 이진 트리는 저장된 자료를 출력하거나 출력하여 계산하는 것에 집중되어 있는 자료구조기 때문에 순회 과정이 ADT에서 중요한 부분을 차지하게 된다. 순회를 위주로 코드를 확인해보자.
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct _BTNode
{
struct _BTNode* Left;
struct _BTNode* Right;
ElemType Data;
} BTNode;
BTNode* CreateNode( ElemType data )
{
BTNode* NewNode = (BTNode*)malloc( sizeof( BTNode ) );
NewNode->Data = data;
NewNode->Left = NULL;
NewNode->Right = NULL;
return NewNode;
}
void DestroyTree( BTNode* N )
{
if ( N == NULL ) return;
DestroyTree( N->Left );
DestroyTree( N->Right );
free( N );
}
void PreorderPrintBT( BTNode* N )
{
if ( N == NULL )
return;
printf( "%d ", N->Data );
PreorderPrintBT( N->Left );
PreorderPrintBT( N->Right );
}
void InorderPrintBT( BTNode* N )
{
if ( N == NULL )
return;
InorderPrintBT( N->Left );
printf( "%d ", N->Data );
InorderPrintBT( N->Right );
}
void PostorderPrintBT( BTNode* N )
{
if ( N == NULL )
return;
PostorderPrintBT( N->Left );
PostorderPrintBT( N->Right );
printf( "%d ", N->Data );
}
CreateNode() 함수를 사용해 BTNode->Left나 BTNode->Right에 새로운 노드를 추가하는 방식으로 이진 트리를 구성할 수 있다.
이진 트리는 수식을 계산할 때에도 자주 사용된다.
일반적으로 우리가 사용하는 수식은 중위 표기식이다. 하지만 중위 표기식은 수식 이진 트리를 이용한 컴퓨터 계산에 적합치 않다. 따라서 수식 트리를 구축할 때 중위 표기식을 후위 표기식으로 바꿔준 후, 이를 트리로 만들어 계산한다.
void BuildExpressionTree( char* PostfixExpression, BTNode** N )
{
int length = strlen( PostfixExpression );
char Token = PostfixExpression[length-1];
PostfixExpression[length-1] = '\0';
switch( Token )
{
case '+': case '-': case '*': case '/':
(*N) = CreateNode( Token );
BuildExpressionTree( PostfixExpression, &(*N)->Right );
BuildExpressionTree( PostfixExpression, &(*N)->Left );
break;
default:
(*N) = CreateNode( Token );
break;
}
}
double Evaluate( BTNode* Tree )
{
char Tmp[2];
double Left = 0;
double Right = 0;
double Result = 0;
if ( Tree == NULL ) return 0;
switch( Tree->Data )
{
case '+': case '-': case '*': case '/':
Left = Evaluate( Tree->Left );
Right = Evaluate( Tree->Right );
if ( Tree->Data == '+' ) Result = Left + Right;
else if ( Tree->Data == '-' ) Result = Left - Right;
else if ( Tree->Data == '*' ) Result = Left * Right;
else if ( Tree->Data == '/' ) Result = Left / Right;
break;
default:
memset( Tmp, 0, sizeof( Tmp ) );
Tmp[0] = Tree->Data;
Result = atof( Tmp );
break;
}
return Result;
}
분리 집합Disjoint Set은 '서로소 집합'으로도 불린다. 각 집합이 공통 원소를 지니지 않는 관계인 집합들을 뜻한다. 우리는 분리 집합을 소속이 명확한 데이터들을 다룰 때 사용한다.
분리 집합은 왜 트리일까? 각각의 집합들이 하나의 공통 부모를 갖는 하나의 트리이기 때문이다.
서로소 집합이므로 ADT에 교집합 연산은 필요가 없다. 합집합 연산으로 두 서로소 집합을 합쳐주는 것과 어떤 원소가 속한 집합이 어떤 것인지 찾아내는 연산만 있으면 된다.
#include <stdio.h>
#include <stdlib.h>
typedef struct _DSet
{
struct _DSet* Parent;
void* Data;
} DSet;
DSet* MakeDSetNode( void* data )
{
DSet* NewNode = (DSet*)malloc( sizeof( DSet ) );
NewNode->Data = data;
NewNode->Parent = NULL;
return NewNode;
}
void DestroyDSet( DSet* Set )
{
free( Set );
}
DSet* FindDSet( DSet* Set )
{
while ( Set->Parent != NULL )
Set = Set->Parent;
return Set;
}
void UnionSet( DSet* Set1, DSet* Set2 )
{
Set2 = FindDSet( Set2 );
Set2->Parent = Set1;
}
참고 서적:
박상현, 2022, 한빛미디어, 『이것이 자료구조+알고리즘이다』
참고 사이트:
LeeHyojin Blog: 그래프 VS 트리 / 실생활 예시
나무위키: 트리(자료구조)
hummmmm.log: 이진 트리 (Binary Tree) 개념과 종류
Baeldung: Difference Between Full, Complete, and Perfect Tree
모든 공학의 개념은 이곳에: 트리(Tree)의 개념 및 전위순회, 중위순회, 후위순회, 층별순회
하루한방울: Disjoint Set (분리 집합)
Copyright © 2025-2026. FioM/EwoC. All rights reserved.