지난 시간에는 선입선출 형태의 자료구조인 큐를 알아보았습니다.
이번 시간에는 데이터를 계층형으로 저장하는 자료구조인 트리를 알아보겠습니다.

0) 시작에 앞서

트리의 상당 부분은 그래프와 관련이 있으며,
트리를 쓰는 알고리즘은 대부분 그래프를 쓰는 알고리즘과 유사합니다.

하지만 자료구조 교과목은 트리를 그래프보다 먼저 설명하기에, 그 교육과정이 코딩 테스트의 알고리즘 문제와 차이가 많습니다.

그리하여 이번 학습자료는 평소보다 설명이 긴 대신, 과제가 없습니다.

트리는 앞으로 학교에서 배울 자료구조 교과목을 미리 훑어보는 느낌으로 공부해주시면 됩니다.

1) 정의

데이터(노드)들이 나뭇가지처럼 연결된 자료구조입니다.

진짜 나무를 뒤집어 놓은 것과 모양이 비슷해
Tree라는 이름이 붙었습니다.

2) 용어

트리 구조를 사용하기 위해
먼저 알아야 할 단어들이 있습니다.

노드(Node, 정점)

트리를 이루는 데이터들 입니다.

위 트리의 노드는 2, 8, 9, 7, 3, 1, 4, 5, 6입니다.

간선(Edge, 엣지)

노드를 연결하는 선입니다.

위 트리에서 8과 3은 간선으로 연결되어 있습니다.

부모 노드, 자식 노드

상, 하위 계급의 노드를 가진 노드입니다.

위 트리에서
7은 8의 자식노드이고, 8은 7의 부모노드입니다.
1의 자식노드는 없고, 2의 부모노드도 없습니다.

차수

자식노드의 개수입니다.

위 트리에서 7의 차수는 3입니다.

형제 노드

부모 노드가 같은 노드들입니다.

위 트리에서 3의 형제 노드는 7입니다.

루트 노드

부모 노드가 없는 노드입니다.

위 트리에서 루트 노드는 2입니다.

트리에서 루트 노드는 1개만 존재합니다.

리프 노드(단말 노드)

자식 노드가 없는 노드입니다.

위 트리에서 리프 노드는 4, 5, 6, 3, 1입니다.

깊이

루트와 특정 노드 사이에 있는 간선의 수입니다.
루트 노드의 깊이는 0입니다.(1로 정의할 때도 있습니다.)

위 트리에서 1의 깊이는 2입니다.

높이

트리에 존재하는 깊이의 최댓값입니다.

위 트리의 높이는 3입니다.

서브 트리

트리의 특정 노드를 루트 노드로 하는 트리입니다.

위 트리에서 2와 9를 연결하는 간선을 삭제하면, 루트가 2인 서브트리를 만들 수 있습니다.

3) 트리의 성질

모든 트리는 다음 조건을 만족합니다.

• 사이클이 존재하지 않는다.
  (사이클: 특정 노드에서 출발하여 같은 간선을 여러번 만나지 않고 처음 노드로 도착할 수 있는 상황)
• 정점 $V$개와 간선 $E$개가 있을 때, $E=V-1$
• 임의의 두 노드를 잇는 경로는 유일하다.

4) 이진 트리

모든 노드의 차수가 2 이하인 트리를 이진 트리라고 합니다.

이진 트리의 성질은 다음과 같습니다.

• 높이가 $h$인 이진 트리는 최소 $h$, 최대 $2^h-1$개의 노드를 가진다.
  (단, 루트 노드의 깊이가 1일 때)

• 노드의 개수가 $n$인 이진 트리의 높이는 최소 $\lceil log_2(n+1) \rceil$, 최대 $n$이다.

• 모든 노드가 2개의 서브트리를 가지고 있다.
  (단, 서브트리가 공집합일 수 있다.)

• 서브트리간의 순서가 존재한다.(왼쪽, 오른쪽)

5) 이진 트리의 종류

노드간의 배치에 따라 다음과 같이 분류할 수 있습니다.

(1) 사향 트리(편향 트리)

리프를 제외한 모든 노드의 차수가 1인 이진 트리입니다.

(2) 완전 이진 트리

임의의 두 리프노드의 높이의 차이가 1 이하이고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식도 있는 이진 트리입니다.

(3) 포화 이진 트리

임의의 두 리프노드의 높이가 같고, 리프노드를 제외한 모든 노드의 차수가 2인 이진 트리입니다.

6) 이진 트리 구현

이진 트리는 크게 두 가지 방법으로 구현할 수 있습니다.

1. 1차원 배열
2. 연결 리스트(포인터)

2번 방법은 교과과정에 포함되는 내용이지만, 본 부트캠프와 거리가 있기에 생략하겠습니다.

저희가 볼 방법은 1차원 배열입니다.

다음과 같은 이진 트리가 있습니다.

각 노드의 데이터는, 트리를 1차원 배열로 구현하였을 때 값이 저장될 인덱스입니다.

이진 트리는 다음과 같은 규칙으로 1차원 배열에 저장 됩니다.

루트의 인덱스 = $1$

현재 노드의 인덱스가 $n$일 때,
왼쪽 자식 노드의 인덱스 = $2n$
오른쪽 자식 노드의 인덱스 = $2n+1$
부모 노드의 인덱스 = $n/2$

차수가 3 이상이 될 수 있는 트리는
1차원 배열로 구현하는 것이 어렵지만,

이진 트리는 다음과 같은 규칙을 이용하여
1차원 배열로 구현할 수 있습니다.

7) 이진 트리 순회

이진 트리를 순회하는 대표적인 방법은 세 가지가 있습니다.

1. 전위 순회(in-order)
   현재 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

2. 중위 순회(pre-order)
   왼쪽 서브트리 -> 현재 노드 -> 오른쪽 서브트리

3. 후위 순회(post-order)
   왼쪽 서브트리 -> 오른쪽 서브트리 -> 현재 노드

예시로 하나의 이진 트리를 보겠습니다.

이 트리를 순회한 결과는 다음과 같습니다.

• 전위 순회: A B D G H E C F

• 중위 순회: G D H B E A C F

• 후위 순회: G H D E B F C A

코드로 표현하면 다음과 같습니다.

#include <iostream>
using namespace std;

// 위 트리를 저장한 1차원 배열
char tree[16]{ NULL, 'A', 'B', 'C', 'D', 'E', NULL, 'F', 'G', 'H' };
int tree_size = 15;

// n = 현재 노드의 인덱스
void inorder(int n) {

	// 인덱스가 트리의 사이즈를 벗어났거나, 인덱스에 노드가 없는 경우
	if (n > tree_size || tree[n] == NULL)
		return;

	cout << tree[n] << ' '; // 현재 노드 출력
	inorder(n * 2);			// 왼쪽 서브트리 방문
	inorder(n * 2 + 1);		// 오른쪽 서브트리 방문
}


void preorder(int n) {

	if (n > tree_size || tree[n] == NULL)
		return;

	preorder(n * 2);		// 왼쪽 서브트리 방문
	cout << tree[n] << ' '; // 현재 노드 출력
	preorder(n * 2 + 1);	// 오른쪽 서브트리 방문

}

void postorder(int n) {

	if (n > tree_size || tree[n] == NULL)
		return;

	postorder(n * 2);		// 왼쪽 서브트리 방문
	postorder(n * 2 + 1);	// 오른쪽 서브트리 방문
	cout << tree[n] << ' '; // 현재 노드 출력

}

int main() {
	
	cout << "전위 순회: ";
	inorder(1);
	cout << '\n';

	cout << "중위 순회: ";
	preorder(1);
	cout << '\n';

	cout << "후위 순회: ";
	postorder(1);

}

실행 결과는 다음과 같습니다.

전위 순회: A B D G H E C F
중위 순회: G D H B E A C F
후위 순회: G H D E B F C A

이번 시간에는 데이터를 계층형으로 저장하는 트리를 알아보았습니다.
다음 시간에는 데이터를 관계형으로 저장하는 그래프를 알아보겠습니다.