[c++] 알고리즘 개념공부 :: 자료구조 - 트리

트리

1. 용도

2. 용어 정리

3. 종류

   1. 이진 트리

   2. 일반 트리

   3. 스레드 이진 트리

4. 구현

   1. 배열 표현법

   2. 연결리스트 표현법

5. 트리 활용

   1. 탐색

   2. 집합 표현

   3. 허프만 코드

 

트리

트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다.

 

용도

계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다.

(결정트리)(이진탐색)

 

용어 정리

• 노드 (node) : 트리의 구성요소이다. 그래프로 따지자면 정점(vertex)에 해당한다.
• 루트 (root) : 부모가 없는 노드이다.
• 서브트리 (subtree) : 하나의 노드와 자손들로 이루어진 트리이다.
• 단말 노드 (leaf node) : 자식이 없는 노드이다.
• 레벨 (level) : 트리의 각 층을 나타내는 index이다. 루트노드는 0레벨이며 자손으로 내려갈 수록 1씩 늘어난다.
• 높이 (height) : 트리의 최대 레벨이다. 트리의 속성이 아닌 중간 노드의 height를 구하려면, 해당 노드가 루트노드가 되는 서브트리의 height를 측정하면 된다.
• 차수 (degree) : 노드가 가지고 있는 자식 노드의 갯수이다.
• 포리스트 (forest) : 서브트리들의 집합이다.

 

종류

이진트리

모든 노드의 차수가 2 이하인 트리이다.

 

<성질>

노드의 갯수	간선의 갯수	레벨 i에서 가질 수 있는 최대 노드 수	높이 k인 트리가 가질 수 있는 최대 노드 수	n개의 노드를 가지는 이진 트리의 높이
n	n-1	2^(i-1)	2^k-1	최소 ceil(log2(n+1)) 최대 n

 

노드의 갯수를 n개라고 하면 존재하는 간선의 갯수는 루트노드를 제외한 n-1개이다. (노드마다 간선이 하나씩 위로부터 내려오기 떄문이다.)

 

<종류>

• 포화 이진트리 : 레벨 l까지 노드가 모두 채워져있는 이진 트리
• 완전 이진트리 : 레벨 l-1 까지는 노드가 모두 채워져있고 레벨 l에서는 왼쪽부터 순서대로 노드가 채워져있는 이진트리
• 편향 이진트리 : 높이가 h일 때 h개의 노드를 한 방향으로만 가지는 이진트리

 

일반 트리

이진 트리가 아닌 트리이다.

참고 : 일반 트리를 이진 트리로 변환하는 방법

1. 일반 트리 A의 첫번째 자식 노드 간선만을 남기고 나머지 간선을 제거한다.
2. 형제 노드들을 간선으로 연결한다.
3. 시계방향으로 45도 회전하여 루트 노드를 변경한다.

 

스레드 이진 트리

 

구현

배열과 연결리스트로 구현할 수 있다.

 

배열 표현법

포화 이진 트리라고 가정하고, 노드에 index를 붙여 데이터를 배열에 저장하는 방법이다. 인덱스는 부모 노드의 인덱스를 floor(i/2)라고 할 때, 왼쪽 자식노드는 2*i, 오른쪽 자식노드는 2*i+1이다.

 

연결리스트 표현법

포인터를 사용하여 부모 노드가 자식노드를 가리키게 저장하는 방법이다.

 

트리 활용

 

탐색

탐색(== 순회)은 트리의 노드들을 빠뜨리거나 중복하지 않고 방문하는 것을 뜻한다. 트리의 기본적인 순회 방법에는 다음 3가지가 있다.

선형 자료구조에서의 순회는 한가지 방법만 존재했던 것과 달리 비선형 자료구조에서는 여러 가지 방법으로 순회가 가능하다.

 

 

가장 기본적인 순회 방법으로는 다음과 같은 3가지가 있다.

• 전위 순회 (preorder)

  VLR 순으로 부모노드를 먼저 순회하는 방식이다.

• 중위 순회 (inorder)

  LVR 순으로 부모노드를 중간에 순회하는 방식이다.

• 후위 순회 (postorder)

  LRV 순으로 부모노드를 마지막에 순회하는 방식이다. 수식트리 계산 시 사용된다.

  (수식트리)

 

특이한 순회로는 레벨 순회가 있다.

• 레벨 순회 (levelorder)

  레벨 별로 1->2->3->4->5->6 순으로 순회한다.

 

그래프에서 봤던 탐색 방법인 DFS와 BFS를 트리에서 구현하려면 다음과 같다.

• DFS

  트리에서는 전위탐색 방법과 같다.

• BFS

  트리에서는 레벨우선탐색 방법과 같다.

 

집합 표현

집합 표현에 관련된 Union-Find 문제는 트리를 이용하여 풀 수 있다.

(Union-Find 문제)

 

허프만 코드

(허프만 코드)