[자료구조] 트리

1. 개념 

• 트리 : 계층적인 구조를 나타내는 자료구조
• 원소 간에 1 : 다 관계를 가지는 비선형 자료구조
• 원소 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조(부모 - 자식 관계의 노드로 이루어짐)
• 응용 분야
   - 계층적인 조직표현, 파일 시스템, 인공지능에서의 결정 트리

 

2. 용어

• 노드(node) : 트리의 구성요소
• 루트(root) : 부모가 없는 노드 (A)
• 서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 (B, C, D)
• 단말노드(terminal node) : 자식이 없는 노드 (E, F, G, H, I, J)
• 비단말노드 : 적어도 하나의 자식을 가지는 노드 (A, B, C, D)
• 레벨(level) : 트리의 각층의 번호
• 높이(height) : 트리의 최대 레벨 (3)
• 차수(degree) : 노드가 가지고 있는 자식 노드의 개수
• 포리스트(forest) : 서브 트리의 집합
   - 트리 A에서 노드 A를 제거하면 A의 자식 노드 B, C, D에 대한 서브 트리가 생기고, 이들의 집합은 포리스트가 된다.

 

트리구조
A						root 노드, level 1
↙			↓	↘
B			C	D		level 2
↙	↓	↘	↓	↙	↘
E	F	G	H	I	J	단말 노드, level 3

 

 

3. 이진 트리(Binary Tree)

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리
• 서브 트리는 공집합일 수 있다.
• 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재
• 모든 노드의 차수가 2 이하가 되어 구현하기가 편리
• 이진 트리에는 서브 트리 간의 순서가 존재

 

1) 순환적 구성

• 노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브 트리도 이진 트리
• 노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리

 

A (root)
↙		↘
B (왼쪽 서브 트리)		C (오른쪽 서브 트리)
↙	↘	↙	↘
D	E	F	G

 

2) 특성

• n개의 노드를 가진 이진 트리는 항상 (n - 1) 개의 간선을 가진다.
• 루트를 제외한 (n - 1) 개의 노드가 부모 노드와 연결되는 한 개의 간선을 가진다.
• 높이가 h인 이진 트리의 경우 최소 h개의 노드를 가지며 최대 2^h - 1개의 노드를 가진다.
   - 높이가 3일 경우 최소는 3개의 노드, 최대는 2^3 - 1 = 7개의 노드를 가진다.
   - 최대 7개의 노드를 가지고 있으므로 최대 높이는 7, 최소 높이는 3이 된다.
• n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 log_2(n + 1)
• 높이가 h인 이진 트리의 최소 노드 수는 h, 최대 노드 수는 2^h - 1
• 부등식 n ≤ 2^h -1 성립
   - 양변에 로그를 취하여 h 값을 구하면 log^2(n + 1) ≤ h h는 정수이므로 h ≥ log^2(n + 1)

 

3) 종류

(1) 포화 이진 트리(Full binary tree)

• 포화 이진 트리 = 정이진 트리
• 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인(2^h - 1) 개의 노드를 가진 이진 트리
• 루트를 1번으로 하여 2^h - 1까지 정해진 위치에 대한 노드 번호를 가진다. 

 

(2) 완전 이진 트리(Complete binary tree)

• 높이가 h이고 노드 수가 n개 일 때 (단, h ≤ n < 2^h - 1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈자리가 없는 이진 트리

 

(3) 사향 이진 트리(Skewed binary tree)

• 편향 이진 트리라고도 부름
• 왼쪽이나 오른쪽으로만 치우쳐진 트리