트리(Tree)

트리(Tree)

 

트리(Tree)란?

• 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.
• 서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른다.
• 힙(Heap)을 구현하는 방법 중 하나가 트리다.

 

트리의 특징

• 그래프의 한 종류로, 최소 연결 트리라고도 불린다.
• 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형적인 자료구조이다.
• 트리의 구조는 데이터 저장의 의미 보다는 저장된 데이터를 효과적으로 탐색하기 위해서 사용한다.
• 리스트와 다르게 데이터가 단순히 나열되는 구조가 아니다. -> 트리는 부모(Parent)와 자식(Child)의 계층적인 관계료 표현된다.
• 사이클이 없다.
• 한 개의 루트 노드 만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.

 

트리와 관련된 용어

용어	설명	사진 예시
루트 노드(root node)	부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.	A
단말 노드(leaf node)	자식이 없는 노드, '말단 노드' 또는 '잎 노드' 라고도 부른다.	H, I, J, F, G
내부 노드(internal node)	단말 노드가 아닌 노드	A, B, C, D, E
간선(edge)	노드를 연결하는 선, link, branch 라고도 부른다.
형제(sibling)	같은 부모를 가지는 노드	C : F, G
노드의 크기(size)	자신을 포함한 모든 자손 노드의 개수	C : 3
노드의 깊이(depth)	루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수	H : 3
노드의 레벨(level)	트리의 특정 깊이를 가지는 노드의 집합	B, C : 1
노드의 차수(degree)	하위 트리 개수, 간선 수(degree) = 각 노드가 지닌 가지의 수	A : 2
트리의 차수(degree of tree)	트리의 최대 차수	B, C : 2
트리의 높이(height)	루트 노드에서 가장 깊숙히 있는 노드의 깊이	3

SMALL

트리의 기본적인 성질

• 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.
• 루트에서 어떤 노드로 가는 경로, 임의의 두 노드 간의 경로는 유일하다. (단, 같은 노드를 두 번 이상 방문하지 않는다는 조건)

 

트리의 순회

• 트리의 순회란 트리의 각 노드를 체계적인 방법으로 탐색하는 과정을 의미한다.
  
  노드를 탐색하는 순서에 따라 전위순회, 중위 순회, 후위 순회 3가지로 분류된다.

1. 전위(Preorder) 순회

루트 노드 - 왼쪽 서브 트리 - 오른쪽 서브 트리의 순서로 순회하는 방식

깊이 우선 순회라고도 불린다.

2. 중위(Inorder) 순회

왼쪽 서브 트리 - 노드 - 오른쪽 서브 트리의 순서로 순회하는 방식

대칭 순회라고도 불린다.

3. 후위(Postorder) 순회

왼쪽 서브 트리 - 오른쪽 서브트리 - 노드의 순서로 순회하는 방식