[2021/08/26][짤막한 이야기 - K진 트리]

[2021/08/26][짤막한 이야기 - K진 트리]
“K진 트리(K-ary Tree)”란 일반적인 트리를 생각하면 된다.
정확한 정의는 “자식 노드가 최대 K개인 트리”를 의미한다.
“이진 트리(Binary Tree)”는 K진 트리에서 K=2인 경우의 특수한 형태인 것이다.
이진 트리에서 자식 노드가 0개, 1개인 경우도 있는 것처럼, K진 트리에서도 반드시 자식 노드의 수가 K개는 아니라는 점을 유의(최대 K개이다.)하여야 한다.
2개이던 자식 노드를 K개로 늘리는 것 뿐이기 때문에 트리 자료구조의 구현 자체는 크게 달라지지 않는다.
그러나 K진 트리에서의 순회나 분석 방법은 이진 트리에서의 순회나 분석 방법과 전혀 다르기 때문에 시간 복잡도도 크게 늘어나게 된다.
여담이지만 K진 트리에서 K=1인 경우를 “일진(?) 트리(Unary Tree)”라고 부를 수 있을 것이며, 이는 우리가 흔히 알고 있는 단방향 연결리스트와 동일하다.
그림은 각각 이진 트리와 사진 트리의 예시이다.
K진 트리의 명명법은 라틴 숫자 접두사(Uni, Bi, Tri, Quad…)를 따른다.
[관련된 짤막한 이야기 - 이진 트리[2021/08/22]]
#이야기 #루니프 #알고리즘 #자료구조 #K진트리 #시간복잡도

[2021/08/26][Short Story - K-ary Tree]
“K-ary Tree” can be thought of as a general tree.
The correct definition means "the tree with at most K child nodes".
“Binary Tree” is a special form of K=2 in a K-ary Tree.
Just as there are cases where there are 0 and 1 child nodes in a binary tree, it should be noted that the number of child nodes is not necessarily K in a K-ary tree (maximum of K).
Although the number of child nodes from 2 is increased to K, the implementation of the tree data structure does not change much.
However, since the traversal or analysis method in the K-ary tree is completely different from the traversal or analysis method in the binary tree, the time complexity also increases significantly.
As an aside, the case where K = 1 in a K-ary tree can be called “Unary Tree”, which is the same as the one-way linked list we are familiar with.
The figure is an example of a binary tree and a quad tree, respectively.
The nomenclature of the base K tree follows the Latin numeric prefixes (Uni, Bi, Tri, Quad…).
[Related Short Story - Binary Tree[2021/08/22]]
#Story #LootNiP #Algorithm #DataStructure #KaryTree #TimeComplexity