Tree Structure 노트5 - K-ary Tree, Selection Tree

K-ary 트리와 Selection 트리

 

k-ary tree : degree의 최대 수가 k인 tree를 의미함. 모든 노드가 n개를 초과하는 자식 노드를 가지지 않는 트리. n이 2이면 binary tree가 되고, 3이면 ternary tree가 됨.

특징 : 높이가 h인 k-ary tree는 최대 n의 h제곱-1의 노드를 가질 수 있음. 높이가 3인 binary tree의 노드는 최대 7개.

종류 :

ㆍcomplete n-ary tree : 완전 트리. 마지막 level을 제외한 모든 level이 완전히 채워져 있고, 마지막 level의 모든 노드는 가능한 한 가장 왼쪽에 있는 tree.

ㆍperfect n-ary tree : 포화 트리. leaf node를 제외한 모든 노드의 차수가 0이며, 모든 leaf node가 동일한 level을 갖는다. 어떤 트리가 perfect tree라면, complete tree이며 full tree이다.

ㆍbalanced n-ary tree : 균형 트리. 모든 leaf node의 level 차이가 최대 1인 트리. 균형 트리는 트리의 주 목적인 탐색을 위한 AVL트리, red-black트리 같은 자료구조들의 기반이 됨.

ㆍskewed n-ary tree : 사향 트리. root node를 제외한 노드들이 모두 parent node의 왼쪽에 있거나, 모두 parent node의 오른쪽에 있는 트리.

 

 

Selection tree를 이용하면, 다음으로 가장 작은 record를 찾는데 필요한 비교 횟수를 줄일 수 있음.

Selection tree는 승자 트리(winner tree)와 패자 트리(loser tree)가 있음.

- winner tree : 각 노드가 2개의 자식 노드 중 더 작은 노드를 나타내는 완전 이진 트리(Complete binary tree). -> 루트노드는 트리에서 가장 작은 노트를 나타냄. 작은값을 토너먼트처럼 올림.

- loser tree : winner트리와 특성은 같지만 루트노드 위에 최상위 0번 노드를 가지는 차이가 있음. 패자를 부모노드에 저장하고 승자는 부모의 부모노드로 올라가서 다시 경기를 함. 루트노드에는 마지막 패자를 정하고, 최종 승자는 0번 노드에 넣음.