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의 오른쪽에 있는 트리다.
'컴퓨터 기초 > 자료구조' 카테고리의 다른 글
Binary Search Tree (1) | 2019.02.04 |
---|---|
Binary Tree의 순회 (0) | 2019.02.01 |
Tree의 표현(representation) (0) | 2019.01.21 |
Tree (0) | 2019.01.18 |
Stack과 Queue (0) | 2019.01.16 |