정보처리산업기사 - 데이터베이스 이해 - 트리(Tree)

※ 공부 내용의 복습 개념으로 정리된 글입니다. - 출처 시나공 

 

트리의 개요

트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태입니다.

• 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 합니다.
• 트리는 가족의 계보(족보), 조직도 등을 표현하기에 적합합니다.
• 트리 관련 용어

• 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
  예) A, B, C, D, E, F, G, H, I, J, K, L, M
• 근 노드(Root Node) : 트리의 맨 위에 있는 노드
  예) A
• 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수
  예) A = 3, B = 2, C = 1, D = 3
• 단말 노드(Terminal Node) = 앞 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드
  예) K, L, F, G, M, I, J
• 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
  예) D의 자식 노드 : H, I, J
• 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들
  예) E, F의 부모 노드 : B
• 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들
  예) H의 형제 노드 : I, J
• 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수
  예) 노드 A나 D가 3개의 디그리를 가지므로 앞 트리의 디그리는 3입니다.

 

 

728x90

 

트리의 운행법

트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 합니다.

• 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖습니다.
• 이진 트리의 운행법은 다음 세 가지가 있습니다.

• Preorder 운행 : Root → Left → Right 순으로 운행합니다. A, B, C
• Inorder 운행 : Left → Root → Right 순으로 운행합니다. B, A, C
• Postorder 운행 : Left → Right → Root 순으로 운행합니다. B, C, A

예제

다음 트리를 Inorder, Preorder, Postorder 방법으로 운행했을 때 각 노드를 방문한 순서는?

Preorder 운행법의 방문 순서

Inorder 운행법의 방문 순서

① Inorder는 Left → Root → Right이므로 1A3이 됩니다.

② 1은 2BE이므로 2BEA3이 됩니다.

③ 2는 HDI이므로 HDIBEA3이 됩니다.

④ 3은 FCG이므로 HDIBEAFCG가 됩니다.

• 방문 순서 : HDIBEAFCG

Postorder

① Postorder는 Left → Right → Root이므로 13A가 됩니다.

② 1은 2EB이므로 2EB3A가 됩니다.

③ 2는 HID이므로 HIDEB3A가 됩니다.

④ 3은 FGC이므로 HIDEBFGCA가 됩니다.

• 방문 순서 : HIDEBFGCA

 

※ 이진 트리 운행법

이진 트리 운행법의 이름은 Root의 위치가 어디 있느냐에 따라 정해진 것입니다. 즉 Root가 앞(Pre)에 있으면 Preorder, 안(In)에 있으면 Inorder, 뒤(Post)에 있으면 Postorder입니다. 

 

 

수식의 표기법

산술식을 계산하기 위해 기억공간에 기억시키는 방법으로, 이진 트리를 많이 사용합니다.

이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중 위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 됩니다.

• 전위 표기법(PreFix) : 연산자 → Left → Right, +AB
• 중위 표기법(InFix) : Left → 연산자 → Right, A+B
• 후위 표기법(PostFix) : Left → Right → 연산자, AB+

Infix 펴기를 Postfix나 prefix로 바꾸기

• Postfix나 Prefix는 스택을 이용하여 처리하므로 Infix는 Postfix나 Prefix로 바꾸어 처리합니다.

예제 1 : 다음과 같이 Infix로 표기된 수식을 Prefix와 Postfix로 변환하시오.

 

Postfix나 Prefix로 표기된 수식을 Infix로 바꾸기

 

예제 2 : 다음과 같이 Postfix로 표기된 수식을 Infix로 변환하시오.

 

예제 3 : 다음과 같이 Prefix로 표기된 수식을 Infix로 변환하시오.