[2021/08/30][짤막한 이야기 - 동형 검사]

[2021/08/30][짤막한 이야기 - 동형 검사]
“동형 검사(Isomorphism Test)”란 두 대상의 구조 동일 여부를 검사하는 알고리즘이다.
앞서 동형 검사에는 "순회"가 필요하다고 하였다.
즉 양측 대상의 노드와 노드 속 데이터 값이 동일한지 확인 후 각각 다음 노드로 이동하는 과정이 필요하다.
예를 들어 이진 트리에서의 동형 검사는 다음과 같이 수행되며, 루트(Root) 노드를 시작으로 재귀적으로 들어간다.
1) 두 루트 노드가 둘 다 데이터가 없으면 동형임이 자명하다.
2) 두 루트 노드 중 하나만 데이터가 없으면 이형(Heteromorphism, 형태가 다름)임이 자명하다.
3) 두 루트 노드의 데이터 값이 다르면 이형이다.
4) 두 루트의 좌측 노드를 루트 노드로 가정하여 해당 알고리즘을 다시 수행한다.
5) 두 루트의 우측 노드를 루트 노드로 가정하여 해당 알고리즘을 다시 수행한다.
6) 1) ~ 5)의 알고리즘에서 다음 검사 대상 노드의 좌우가 바뀌어도 동형(좌우 반전 동형)이다.
트리의 동형 검사는 직관적이기 때문에 그래프의 동형 검사에 비하여 효율적으로 수행된다.
모든 노드에서의 True가 모여야 전체 트리 동형에서 True를 출력할 수 있다.
[관련된 짤막한 이야기 - 이진 트리[2021/08/22]]
[관련된 짤막한 이야기 - 동형[2021/08/29]]
#이야기 #루니프 #알고리즘 #자료구조 #동형 #검사 #순회 #재귀

[2021/08/30][Short Story - Isomorphism Test]
“Isomorphism Test” is an algorithm that tests whether two objects have the same structure.
Previously, it was said that isomorphism testing required "Traverse".
In other words, it is necessary to move to the next node after checking whether the data values ​​in the node and the node of both targets are the same.
For example, the isomorphism test in a binary tree is performed as follows, and it recursively enters starting from the root node.
1) If both root nodes have no data, it is trivial that they are isomorphic.
2) If only one of the two root nodes has no data, it is trivial that it is heteromorphic.
3) If the data values ​​of the two root nodes are different, it is heteromorphic.
4) Assuming that the left node of the two routes is the root node, the algorithm is executed again.
5) Assuming that the right node of the two routes is the root node, the algorithm is executed again.
6) In the algorithm of 1) ~ 5), even if the left and right of the next target node are reversed, it is isomorphic (left and right reverse isomorphic).
Since the isomorphism test of a tree is intuitive, it is performed more efficiently than the isomorphism test of a graph.
"True" in all nodes must be gathered to output "True" in the entire tree isomorphism test.
[Related Short Story - Binary Tree[2021/08/22]]
[Related Short Story - Isomorphic[2021/08/29]]
#Story #LootNiP #Algorithm #DataStructure #Isomorphism #Test #Traversal #Recursion