트리의 종류

트리란 무엇인가?

배열, 리스트, 스택, 큐와 같은 선형구조가 아닌 부모 자식의 관계를 갖는 계층형 그래프

1. Binary Tree(이진 트리)

노드가 하나 이상의 자식을 갖게 되면 트리라고 부르는데 자식 노드가 최대 2개까지만 허용하는 트리를 이진트리라고 부릅니다.

2. Ternary Tree

노드가 2개 이상 붙는 트리도 당연히 존재하게 되는데 3개가 붙으면 ternary tree라고 부릅니다.

3. Binary Search Tree(이진 탐색 트리)

다른 특별한 조건 없이 노드의 자식이 최대 2개씩만 붙으면 이진 트리라고 부르게 되는데, 이진 탐색 트리는 왼쪽 노드와 그 이하의 자식 노드들은 현재의 노드보다 작아야 하며 오른쪽 노드와 그 이하의 자식들은 현재의 노드 보다 큰 조건을 만족하게 된다. 그러므로 모든 값들이 노드들을 기준으로 두 가지 방향으로만 찾으면 되기 때문에 값을 찾는데 편리한 조건을 지니고 있다.

4. Complete Binary Tree(완전 이진 트리)

모든 노드들이 레벨 별로 왼쪽부터 채워져 있을 경우 완전 이진 트리라고 한다. 즉, 마지막 레벨을 제외한 서브 트리의 레벨이 같아야 하며 마지막 레벨이 왼쪽부터 채워져 있으면 완전 이진 트리라고 한다.

5. Full Binary Tree

하나의 자식 노드를 가진 트리가 하나도 존재하지 않을 경우에 Full Binary Tree라고 한다. 노드들의 자식이 하나도 없거나 두 개의 자식으로만 구성될 경우이다.

6. Perfect Binary Tree

양 쪽으로 빈 공간 없이 모든 노드가 두 개의 자식을 가지며 레벨도 같을 경우를 말한다. 레벨의 개수를 n이라고 가정할 때 2^n - 1의 노드 개수를 가지게 된다.