자료구조-03. 트리

자료의 출처는 '엘리스 AI 트랙 2기 (https://aitrack.elice.io/)' '자료구조' 강의이며, 학습 후 정리한 내용입니다.

⚡️올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사하겠습니다.⚡️

---

트리

01. 비선형구조와 트리

대표적인 자료구조의 예시

선형 구조		비선형 구조
스택 (Stack)	큐 (Queue)	트리 (Tree)	그래프 (Graph)

선형구조: 자료가 순서를 가지고 연속되어 있음

비선형 구조 : 선형 구조에 해당하지 않는 자료구조

그래프

트리는 그래프의 특수한 형태 중 하나이다.

 

정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조

정점(vertex): 자료, 상태 등 뭔가를 담고 있음 (정점은 '노드'라고도 함)

간선(edge): 정점 간의 관계를 나타냄

어떤정점에서간선을통해다른정점으로이동할수있다.
어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 한다.

예를 들어 정점 4에서 정점 6으로 이동하는 경로들 중 하나는 4→5→3→6이 될 수 있다.

유향 그래프

그래프의 간선은 방향이 있을 수도, 없을 수도 있다.

위와 같은 그래프에서 정점 1에서 2로 이동할 수 는있지만, 2에서 1로 이동할 수 는없다.

방향이 있는 간선을 포함한 그래프를 유향 그래프라고 한다.

 

사이클

어떤 정점에서 출발하여 자기 자신으로 돌아오는 경로가 있을 수 있다.

이와 같이 처음 시작한 정점으로 다시 돌아오는 경로를 '사이클' 이라고 한다.

예를 들어 3→6→7→3은 사이클이다.

트리

그래프 중 아래의 특별한 성질을 갖는 그래프를 트리라고 한다.

트리의 여러 성질은 다음과 같다.

• 트리의 간선들은 모두 방향성을 갖는다.
• 어떤 정점을 가리키는 정점의 개수는 최대1개이다.
• 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다.

• 트리는 사이클을 갖지 않는다.

 

트리에서 다른 어떠한 정점도 가리키지 않는 정점을

루트 노드(Root Node) 라고 한다.
정점 1이 루트 노드에 해당한다.
또, 루트 노드로부터의 거리를 깊이라고 한다.

임의의정점𝐴가다른정점𝐵을가리킬때 𝐴를 𝐵의 부모 노드(Parent Node)라고 하고,

𝐵를 𝐴의 자식 노드(Child Node)라고 한다.

예를들어 정점 2는 정점 5의 부모노드이고, 정점3 은 정점 1의 자식노드이다.

가리키는 정점이 없는 정점들을 리프 노드(Leaf Node)라고 한다.

정점 4,5,6,7이 리프노드에 해당

 

트리는 계층적인 구조로 되어 있는 자료구조이다.

운영체제에서 파일을 분류하기 위해 사용하는 디렉터리(폴더)는 트리 구조의 대표적인 예시이다.

이진 트리

각 정점들이 자식 노드를 최대 2개까지만 갖는 트리를 이진 트리라고 한다.

이진 탐색 트리 등 유용하게 활용되는 트리 중에는 대부분 이진 트리를 응용한 것이 많다.

포화 이진 트리

리프노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있으면서

모든 리프노드의 깊이가 동일한 트리를 포화 이진 트리라고한다.

포화이진트리의높이를h라고할때, 정점의 개수는 항상 2! − 1개이다.

 

완전 이진 트리

마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며,

마지막 깊이의 정점들은 가능한 한 왼쪽에 있는 트리를
완전 이진 트리라고 한다.

또는 포화 이진 트리에서 마지막 깊이의 정점이 오른쪽에서부터 일부 제거된 트리라고 볼 수 있다.

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

정 이진 트리

정 이진 트리는 리프노드를 제외한 모든 노드들이

두 개의 자식노드를 갖고 있는 이진트리이다.

즉, 모든 정점은 0개 또는 2개의 자식노드를 갖는다.

02. 트리의 표현 방법

트리의 표현 방법

 class TreeNode :
    def __init__(self) :
        self.left = None
        self.right = None

이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 위와 같은 클래스로 표현할 수 있다.

 

완전 이진 트리의 경우, 배열을 이용하여 간단하게 구현이 가능하다.

아래와 같은 완전 이진 트리가 존재 할 때 각 정점에 순서대로 번호를 붙일 수 있다.

어떤 정점의 번호가 𝑛이면 왼쪽자식은2𝑛,오른쪽자식은2𝑛+1이다.

따라서 배열로 완전 이진 트리를 표현할 수 있게 된다.

0번은 사용하지 않는다.

또, 트리는 그래프의 일종이므로 그래프를 표현할 때 사용하는 인접 행렬, 인접 리스트, 간선 리스트를 사용할 수도 있다.