n-ary Tree와 Complete, Perfect, Balanced, Skewed Tree

n-ary tree는 degree의 최대 수가 n인 tree를 의미한다. '모든 노드가 n개를 초과하는 자식 노드를 가지지 않는 트리'라고도 정의한다. k-way tree, k-ary tree, m-ary tree라고도 불린다. n이 2이면 binary tree가 되고, 3이면 ternary tree가 되는 식이다.

n-ary tree의 특징

높이가 h인 n-ary tree는 최대 n의 h제곱-1만큼의 노드를 가질 수 있다. 예를 들어, 높이가 3인 binary tree는 최대 7개의 노드를 가질 수 있다.

n-ary tree의 종류

complete n-ary tree

완전 트리라고 부른다. 마지막 level을 제외한 모든 level이 완전히 채워져 있으며, 마지막 level의 모든 노드는 가능한 한 가장 왼쪽에 있는 tree다.

perfect n-ary tree

포화 트리라고 부른다. leaf node를 제외한 모든 노드의 차수가 n이며, 모든 leaf node가 동일한 level을 갖는다. 어떤 트리가 perfect tree라면, complete tree이며 full tree다.(모든 노드의 차수가 n이므로)

balanced n-ary tree

균형 트리라고 부른다. 모든 leaf node의 level 차이가 최대 1인 트리를 말한다. 균형 트리는 트리의 주 목적인 '탐색'을 위한 AVL tree, red-black tree 와 같은 자료구조들의 기반이 된다.

skewed n-ary tree

사향 트리라고 부른다. root node를 제외한 노드들이 모두 parent node의 왼쪽에 있거나, 모두 parent node의 오른쪽에 있는 트리다.