자료구조 | 트리(Tree)

오른쪽 이미지 출처: https://ssangq.netlify.app/posts/data-structure-tree

트리(Tree)는 데이터들의 구조가 실제 나무와 비슷하다고 해서 붙여진 이름이다(나무를 거꾸로 뒤집은 모습).

맨 꼭대기 노드인 루트(root)에서 시작하여 가지(branch)와 같은 여러 경로를 통해 맨 아래의 리프(leaf) 노드로 뻗어 나가는 구조를 가지고 있다. 

 

그림 봐도 알겠지만 앞서 배웠던 자료구조들과 다르게 linear 하다고 보기엔 어렵다. 따라서 트리는 비선형 자료구조로 분류된다. 

 

수많은 천재들이 트리를 잘 활용하는 법을 알아내준 덕에 우리는 데이터 관리를 위한 매우 뛰어난 도구를 몇가지 얻게 되었다. 특히 트리 구조는 탐색 기법으로 응용될 때 더 빛을 발하는데, 예를 들어 이진 탐색 트리(Binary Search Tree, BST)나 몬테카를로 트리 탐색(Monte-Carlo tree search) 등이 있다. 

 

 

실생활에서의 트리 구조 예시

트리 구조는 우리에게 이미 익숙한 개념이다. 

• 파일 시스템: 대부분 OS에서 사용하는 디렉토리, 파일은 트리 형태로 구성되어 있다. 우리는 이를 직관적으로 자연스럽게 사용한다. 
• 조직도: 전통적인 회사의 조직도는 상사와 부하 직원의 관계를 표현하는 계층적 구조로 구성되어 있다. 이는 트리 구조이다.
• 알파고: 그 유명한 알파고도 트리에서 파생된 기법인 몬테카를로 트리 검색(Monte-Carlo tree search)을 활용했다. 

 

자료구조에서의 트리 응용 예시

또한 트리는 다른 자료구조들의 근간이 되기 때문에, 다른 자료구조들을 공부함에 있어서도 필수적으로 알아야 하는 개념이다. 트리의 응용 자료구조에는 아래와 같은 예시가 있다. 

응용 분야	설명
힙(Heap) -> 우선순위 큐	- 힙(Heap): 힙 자료구조는 트리의 일종으로, 각 노드의 키 값이 그 노드의 자식들의 키 값보다 크거나(최대 힙) 작은(최소 힙) 특성을 가진 완전 이진 트리이다. - 우선순위 큐: 데이터가 우선순위를 가질 때, 그 우선순위에 따라 접근 또는 제거된다. 힙을 이용하면 이를 효율적으로 구현할 수 있다.
트라이(Trie)	- 트라이(Trie): 트리의 일종. 대개 문자열의 집합을 저장하며, 루트에서부터 어떤 노드까지의 경로상의 문자들로 문자열을 구성.  - 문자열 검색이나 사전 등에서 트라이 사용 시 효율적 검색이 가능하다. O(L)의 시간 내에 문자열 검색이 가능하다 (L은 문자열 길이).

 

---

트리(Tree)

[트리의 정의]

트리를 한 문장으로 요약하면 "트리는 사이클이 없는 연결 그래프이다." 라고 요약할 수 있다. 

트리의 핵심적이고 필수적인 조건은 다음과 같다. 
1. 연결된 그래프이어야 한다. (즉, 임의의 두 노드 간에 경로가 존재해야 함)
2. 사이클을 포함하지 않아야 한다.
3. n개의 노드에 대해 n−1개의 간선이 있어야 한다.

1. 트리의 구조, 용어

트리는 각각의 데이터를 담은 노드로 이루어져 있다.
하나의 트리는 하나의 루트 노드(Root Node)를 가진다. 또한 트리는 수많은 서브트리(subtree)의 집합인 형태이다. 

Introduction to Tree – Data Structure and Algorithm Tutorials (출처: https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/)

 

위 이미지의 내용을 하나하나 이해하고 설명할 수 있으면 트리의 기본 구조는 이해했다고 볼 수 있다!

용어	설명
노드 (Node)	트리를 구성하는 기본 요소. 데이터와 다른 노드를 가리키는 포인터(자식 노드)로 구성된다.
간선 (Edge 또는 Link)	두 노드를 연결하는 선. 부모 노드와 자식 노드 사이를 연결한다.
경로 (Path)	한 노드로부터 다른 노드로 가는 경로이다.
키 (Key)	노드에 저장된 고유한 값으로, 탐색이나 정렬 등의 연산에서 주로 사용된다.
루트 (Root)	트리의 최상위에 위치한 노드. 부모가 없는 유일한 노드이다.
리프 (Leaf) = 단말 노드 (Terminal Node)	자식 노드가 없는 노드. 트리의 가장 아래쪽에 위치한다. 위 그림으로 치면 G 노드도 리프에 해당한다.
내부노드, 비단말 노드 (Internal Node)	Terminal 노드를 제외한 모든 노드. 루트 노드도 포함한다.
부모(Parent),  자식(Child)	한 노드는 다른 노드에 연결될 수 있으며, 연결된 두 노드 중 상위 노드를 부모, 하위 노드를 자식이라고 한다.
형제 (Siblings)	동일한 부모 노드를 가진 두 노드나 그 이상의 노드들을 형제라고 한다.
최소공통조상 (Least Common Ancestors)	두 노드의 공통적인 조상 중 가장 레벨이 높은 조상 노드
서브트리 (Subtree)	어떤 노드를 루트로 하는 그 밑의 모든 노드들로 구성된 트리.
트리의 높이 (Height of the Tree)	루트 노드에서 가장 멀리 떨어진 리프 노드까지 간선의 수.
레벨 (Level)	루트 노드를 레벨 0(또는 1)로 시작하여, 각 깊이에 따라 레벨이 증가한다. 즉, 부모 노드의 레벨이 n이면, 자식 노드의 레벨은 n+1이다.

 

 

# Node? Vertex? .. Edge? Link?
이 용어들은 자주 혼용되어 사용되는 탓에, 처음 공부하는 입장에서 헷갈리는 면이 있었다. 각 용어가 일반적으로 어떤 문맥에서 선호되는지를 가볍게 알아보고 가면 좋을 것 같다. 
--------------------------------------------------

"Vertex"와 "Edge"는 그래프 이론과 관련된 문맥에서 더 전통적으로 사용되는 용어이다. 반면 "Node"와 "Link"는 일반적으로 네트워킹, 트리 자료구조, 링크드 리스트와 같은 다른 컴퓨터 과학의 분야에서 더 자주 사용된다고 한다. 

Vertex & Edge:
- 그래프 이론: 알고리즘, 최적화 문제, 그래프 관련 문제에서 "Vertex"와 "Edge" 용어가 주로 사용된다. 알고리즘 과목의 수업이나 교재에서 그래프에 관한 문제나 알고리즘을 설명할 때 이 표현들을 사용한다. 

Node & Link:
- 컴퓨터 네트워크: 네트워크 topology나 프로토콜에서 "node"와 "link" 용어가 주로 사용된다.
- 자료 구조: 트리, 연결 리스트와 같은 계층적 구조의 자료 구조에서 "Node"라는 용어가 빈번하게 사용된다.
     - 트리의 경우, 노드는 다음과 같이 구성될 수 있다. [노드 = 데이터 + (하나 이상의) 자식 노드를 가리키는 포인터]
     - 연결 리스트의 경우, 노드는 다음과 같이 구성된다. [노드 = 데이터 + 다음 노드를 가리키는 포인터]
- 분산 시스템: 물리적 또는 가상의 개별 시스템 또는 컴퓨터를 "Node"라고 부를 때가 있다. 
 

 

 

2. 트리의 특성과 성질

1. 계층적 구조: 트리는 계층적 구조를 가지며, 이를 이용하여 계층적 관계를 표현할 수 있다.
2. 사이클을 포함하지 않음: 트리는 Cycle(순환 구조)를 허용하지 않는다. 즉, 어떠한 노드도 자신을 다시 가리키지 않는다.
3. 노드 수가 n개라면, 간선의 수는 n-1개여야 한다. 

트리도 그래프의 일종(Acyclic Graph)이다. 2번과 3번은 어떠한 그래프가 트리인가 여부를 판별할 수 있는 기준이 되기도 한다. 

 

 

2. 트리의 분류

컴퓨터 공학에서 자주 다루는 트리의 대표적인 종류는 다음과 같다: 

트리 종류	설명
이진 트리 (Binary Tree)	각 노드가 최대 두 개의 자식 노드를 가지는 트리.
이진 탐색 트리 (Binary Search Tree)	이진 트리의 일종으로, 모든 노드는 다음 특성을 만족한다: - 왼쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 작고, - 오른쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 크다.
m-ary 트리 (발음: 에-머리 트리)	각 노드가 최대 m개의 자식 노드를 가지는 트리. m = 2일 때, 이진 트리와 동일하다.
B-트리 (B-tree)	m-ary 트리의 일종(균형 검색 트리)로, 데이터베이스와 파일 시스템에 사용된다. 각 노드에는 여러 키가 저장될 수 있으며, 노드의 키 수에 따라 자식 수가 결정된다.
레드-블랙 트리 (Red-Black Tree)	이진 탐색 트리의 일종(균형 검색 트리)으로, 각 노드에 색깔(빨강 또는 검정)을 가지며, 특정 규칙을 만족하여 균형을 유지한다.
AVL 트리	이진 탐색 트리의 일종(균형 검색 트리)으로, 각 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이 되도록 균형을 유지한다.