[2021/08/27][짤막한 이야기 - 좌측자식 우측형제]

[2021/08/27][짤막한 이야기 - 좌측자식 우측형제]
시작부터 제목이 조금 우스꽝스럽다.
“좌측자식 우측형제(Left-Child Right-Sibling)”란 K진 트리를 이진 트리로 변환하는 알고리즘이다.
LCRS 이진 트리라고도 한다.
K진 트리에서의 분석 방법과 이진 트리에서의 분석 방법이 약간 다르기 때문에 이진 트리로 선처리 후 분석을 진행하는 것이 더 나을 수 있다.
알고리즘 이름에서 알 수 있듯이, 자식 노드는 모두 부모 노드의 좌측에만 존재하기 때문에 얼핏 보면 “편향 트리(Skewed Tree)”와 유사하게 보일 수 있다.
이진 트리로 변환된 K진 트리는 이진 트리의 특성을 가지고 있긴 하지만, 약간의 편향성 때문에 이진 트리와는 조금 다른 특징도 가진다.
예를 들어, 부모 노드(4번)가 자식 노드(8번)로 가기 위하여 K진 트리에서는 소요 시간이 1이지만, LCRS 이진 트리에서는 시간이 더 소요된다.
변환 알고리즘은 그림을 보면 쉽게 이해가 갈 것이다.
모든 형제 노드끼리 간선으로 연결(파란선, 6,7,8,9번 노드도 연결됨)한다.
그 다음 가장 좌측의 자식 노드로 향하는 간선만 남겨두고 나머지 간선은 모두 제거(회색선)한다.
마지막으로 이를 약 45도 회전하면 이진 트리로의 변환이 완료된다.
[관련된 짤막한 이야기 - 이진 트리[2021/08/22]]
[관련된 짤막한 이야기 - K진 트리[2021/08/26]]
#이야기 #루니프 #알고리즘 #자료구조 #좌측자식우측형제 #K진트리 #시간복잡도

[2021/08/27][Short Story - Left-Child Right-Sibling]
The title is a bit ridiculous from the start.
“Left-Child Right-Sibling” is an algorithm that converts a K-ary tree into a binary tree.
Also called LCRS binary tree.
Since the analysis method in the K-ary tree and the analysis method in the binary tree are slightly different, it may be better to perform the analysis after preprocessing into the binary tree.
As the algorithm name suggests, at first glance, it may look similar to a “Skewed Tree” because all child nodes exist only to the left of the parent node.
A K-ary tree converted to a binary tree has the characteristics of a binary tree, but it also has slightly different characteristics from a binary tree due to some bias.
For example, it takes 1 time for a parent node (No. 4) to go to a child node (No. 8) in a K-ary tree, but takes more time in an LCRS binary tree.
The conversion algorithm can be easily understood by looking at the picture.
All sibling nodes are connected by an edge (blue line, nodes 6, 7, 8, and 9 are also connected).
Then, only the edges toward the leftmost child node are left, and all other edges are removed (grayed lines).
Finally, rotate it about 45 degrees to complete the conversion to a binary tree.
[Related Short Story - Binary Tree[2021/08/22]]
[Related Short Story - K-ary Tree[2021/08/26]]
#Story #LootNiP #Algorithm #DataStructure #LeftChildRightSibling #KaryTree #TimeComplexity