[Python] Tree (트리)란?

■

 

트리는 하나의 뿌리에서 위로 뻗어나가는 형상처럼 생겨서 '트리(나무)'라는 명칭이 붙었는데, 트리 구조를 표현할 때는 나무의 형상과는 반대 방향으로 표현한다.

 

트리는 자식도 트리고 또 그 자식도 트리고 또 그....

흔히 서브트리(Subtree)로 구성된다고 표현한다.

좀 어렵게 표현하자면 재귀로 정의된(Recursively Defined) 자기 참조(Self-Referential) 자료구조하고 할 수 있다.

 

■■

 

자, 이제 트리의 각 명칭을 살펴보자.

 

우선 트리는 항상 루트(Root)에서 시작된다.

루트는 자식(Child)를 가지며 각 간선(Edge)로 연결되어 있다.

 

차수(Degee)	자식 노드의 개수
크기(Size)	자신을 포함한 모든 자식 노드의 개수
리프(Leaf)	자식 노드가 없는 노드
서브트리(Subtree)	트리는 서브트리로 구성됨

예를 들면 노드 D의 자식 노드는 H, I 두 개 이므로 차수(Degree)는 2,

전체 크기(Size), 루트이자 A 노드의 크기는 자신을 포함한 모든 자식 노드의 개수, 9가 된다.

노드 C의 크기라고 한다면 3이 되겠다.

 

위 사진을 보면 깊이, 높이, 레벨을 한 눈에 알 수 있을 것이다.

 

높이(Height)	현재 위치에서부터 리프까지의 거리
깊이(Depth)	루트에서부터 현재 노드까지의 거리

레벨은 대부분 0에서부터 시작하는 것이 좀 더 일반적이라고 한다. (1에서부터 시작하는 경우도 있다고 한다.)

 

■■■

 

그렇다면 그래프와 트리의 차이점은 무엇일까?

바로 트리는 순환 구조가 아니라는 점이다.

그리고 그래프는 단방향(Uni-Directional),  양방향(Bi-Directional)을 모두 가리킬 수 있지만

앞서 보여준 사진을 보면 트리는 부모 노드에서 자식 노드를 가리키는 단방향 뿐이다.

또한 트리는 하나의 부모 노드를 가져야하며 루트도 하나여야 한다.

 

1. 순환 구조가 아니다 단방향이다

2. 부모 노드는 하나다

3. 루트는 하나다

 

간단하게 정리하자면 위 세 개로 그래프와 트리의 차이점을 잘 알 수 있을 것 이다.

 

■■■■

 

트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree)가 가장 널리 사용된다.

우선, 각 노드가 n개 이하의 자식을 갖고 있으면 n-ary 트리(다항 트리, 다진 트리)라고 한다. 여기서 n=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별이 이진 트리(Binary Tree)라고 구분해서 부른다.

 

이진 트리 유형(Types of Binary Trees)는 정 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)로 3가지 유형을 들 수 있다.

 

정 이진 트리(Full Binary Tree)	완전 이진 트리(Complete Binary Tree)	포화 이진 트리(Perfect Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는다	마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다	모든 노드가 2개의 자식 노드를 갖는다