[12주차] 트리의 개념

4월 6일 자 학습 내용 정리입니다.

 

 

✅ 비선형 구조

앞서 포스팅에서 스택과 큐를 배우며 선형 구조와 비선형 구조에 대해 언급했었다.

선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미하며 비선형 구조는 자료를 일렬로 나열하기 힘들고 자료의 순서가 불규칙해 연결 관계가 복잡한 구조를 의미한다.

바로 이 비선형 구조의 대표적인 예가 트리(Tree)와 그래프(Graph)이다.

 

 

✅ 그래프

트리는 사실 그래프의 특수한 형태 중 하나이다.
따라서 트리를 이해하기 위해서는 그래프의 정의부터 알 필요가 있다.

그래프(Graph)는 정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조이다.

 

정점(vertex)은 자료, 상태 등 값을 담고있는 것을 의미하며 노드라고 부르기도 한다.

간선(edge)은 정점 간의 관계를 나타낸다.
어떤 정점에서 간선을 통해 다른 정점으로 이동할 수도 있다.
어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 한다.
이때 어떤 정점에서 출발해 자기 자신으로 돌아오는 경로가 존재할 수 있는데 이를 사이클이라고 한다.

그래프의 간선은 방향이 존재할 수도 있고 없을 수도 있다.
간선의 방향이 존재하는 그래프는 유향 그래프라고 한다.

 

 

✅ 트리

그래프 중 특별한 성질을 갖는 그래프를 트리(Tree)라고 한다.
특별한 성질은 아래와 같다.

 

• 트리의 간선은 모두 방향성을 갖는다.
• 어떤 정점을 가리키는 정점의 개수는 최대 1개이다. => 1개 있거나 없거나 둘 중 하나의 경우의 속한다.
• 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개이다.
• 사이클을 갖지 않는다.

 

 

트리에서 다른 어떠한 정점도 가리키지 않는 정점을 루트노드(root node)라고 한다.
그리고 루트 노드로부터의 거리를 깊이(depth)라고 하며 루트 노드로부터 깊이가 제일 깊은 노드들을 리프 노드(leaf node)라고 한다.

 

 

임의의 정점 A가 다른 정점 B를 가리킬 때 A를 B의 부모 노드(parent node)라고 하고 B를 A의 자식 노드(child node)라고 한다.
즉, 연결되어 있는 두 정점 사이에는 부모-자식 관계가 성립한다.
이는 곧 트리가 계층적인 구조로 되어있다는 것을 의미한다.

 

 

✅ 트리의 종류

✔️ 이진 트리

 

이진트리(Binary Tree)는 각 정점들이 자식 노드를 최대 2개까지만 갖는 트리를 의미한다.

 

✔️ 포화 이진 트리

 

포화 이진 트리(Perfect Binary Tree)는 리프 노드(leaf node)를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있으면서 모든 리프 노드의 깊이가 동일한 트리를 의미한다.

포화 이진 트리의 높이를 h라고 할 때 정점의 개수는 항상 \(2^{h}-1\) 개이다.

 

✔️ 완전 이진 트리

 

 

완전 이진 트리(Complete Binary Tree)는 마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며 leaf node들은 왼쪽부터 채워져있는 트리를 의미한다.

 

포화 이진 트리도 완전 이진 트리에 속하며 완전 이진 트리는 포화 이진 트리에서 leaf node가 오른쪽에서부터 일부가 제거된 트리라고 볼 수 있다.

(제거되지 않아도 완전 이진 트리 조건에 충족한다.)

 

완전 이진 트리의 높이가 h 일때 정점의 개수는 \(2^{h-1}\)개 이상 \(2^{h}-1\) 개 이하이다.

 

✔️ 정 이진 트리

 

 

정 이진 트리(Full Binary Tree)는 리프 노드를 제외한 모든 노드들이 2 개의 자식 노드를 갖고 있는 이진 트리이다.
즉, 모든 정점은 0개 또는 2개의 자식 노드를 가진다.