Full, Perfect, Complete ? 이진트리의 형태

이진트리에는 여러 종류가 있다

트리 중에서도 가장 많이 사용하는 것이 이진트리이지만, 이진 트리들에도 명칭이 존재한다

 

Binary Tree의 종류에는

1️⃣Full Binary Tree 2️⃣Perfect Binary Tree 3️⃣Complete Binary Tree

가 있다

 

세 가지 트리를 한글로 번역하면... 

 

 

 

그렇다

트리들의 이름만으로는 분간이 안 간다

 

그럼 세 가지 트리는 어떤 특징을 가지고 있고, 어떻게 다를까?

 

1️⃣ Full Binary Tree 

 

 

full binary tree는 모든 node의 child가 2개 or 0개인 트리를 말한다.

즉, leaf node가 아닌 node는 child를 두 개 가져야만 한다는 뜻이다 😄

그림의 오른쪽 트리에서, '2'와 '4'는 child를 하나씩 가졌기 때문에 full binary tree가 아니다.

 

 

2️⃣ Perfect Binary Tree

 

 

perfect binary tree는 full binary tree + 모든 leaf node의 depth가 같은 트리를 말한다.

위의 그림을 보며 가득 찬 이진트리라고 생각하면 이해가 쉽다

perfect binary tree는 가장 깊은 depth의 node들은 child가 없고, 다른 모든 node들은 두 개의 child를 가진다.

 

3️⃣ Complete Binary Tree

 

 

complete binary tree의 depth가 d라고 할 때, depth가 d-1까지는 perfect binary tree이면서, depth가 d인 node(제일 아래 층 node들)은 왼쪽부터 오른쪽의 order대로 node가 채워져 있는 트리를 말한다.

즉, 중간의 순서를 건너뛰고 다음 node를 채울 순 없다.

왼쪽의 그림은 위와 같은 정의를 만족하지만, 오른쪽 그림은 5, 1 다음에 4의 left child node가 채워지지 않고 right child node가 생겼기 때문에 complete binary tree가 아니다.