[Python] 트리 동형 (Tree Isomorphism)

Tree Isomorphism 트리 동형

개념

두 트리는 간선의 방향만 잘 조절해주면 완전히 동일한 트리가 된다.
즉, 두 트리는 Isomorphic 한다.

---

예시를 보자!
두 트리는 2와 3, NULL과 6, 7, 8과 같은 하위 트리가 뒤집힌 동형이다.

두 트리를 동시에 탐색한다.
순회 중인 두 트리의 현재 내부 노드를 각각 n1, n2라고 한다. n1, n2를 기반으로 하는 하위 트리가 동형이 되기 위한 두가지 조건은 다음과 같다.
1. n1과 n2의 데이터는 동일하다.
2. 다음 두 가지 중 하나는 n1, n2의 자식에 해당한다.
a) n1의 왼쪽 자식은 n2의 왼쪽 자식과 동형이고, n1의 오른쪽 자식은 n2의 오른쪽 자식과 동형이다.
b) n1의 왼쪽 자식은 n2의 오른쪽 자식과 동형이고, n1의 오른쪽 자식은 n2의 왼쪽 자식과 동형이다.

# Python program to check if two given trees are isomorphic
 
# A Binary tree node
class Node:
    # Constructor to create the node of binary tree
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
     
# Check if the binary tree is isomorphic or not
def isIsomorphic(n1, n2):
     
    # Both roots are None, trees isomorphic by definition
    if n1 is None and n2 is None:
        return True
 
    # Exactly one of the n1 and n2 is None, trees are not
    # isomorphic
    if n1 is None or n2 is None:
        return False
 
    if n1.data != n2.data :
        return False
    # There are two possible cases for n1 and n2 to be isomorphic
    # Case 1: The subtrees rooted at these nodes have NOT
    # been "Flipped".
    # Both of these subtrees have to be isomorphic, hence the &&
    # Case 2: The subtrees rooted at these nodes have
    # been "Flipped"
    return ((isIsomorphic(n1.left, n2.left)and
            isIsomorphic(n1.right, n2.right)) or
            (isIsomorphic(n1.left, n2.right) and
            isIsomorphic(n1.right, n2.left))
            )
 
 
# Driver program to test above function
n1 = Node(1)
n1.left = Node(2)
n1.right = Node(3)
n1.left.left = Node(4)
n1.left.right = Node(5)
n1.right.left = Node(6)
n1.left.right.left = Node(7)
n1.left.right.right = Node(8)
 
n2 = Node(1)
n2.left = Node(3)
n2.right = Node(2)
n2.right.left = Node(4)
n2.right.right = Node(5)
n2.left.right = Node(6)
n2.right.right.left = Node(8)
n2.right.right.right  = Node(7)
 
print ("Yes" if (isIsomorphic(n1, n2) == True) else "No")
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

• 시간 복잡도
  : 위의 솔루션은 두 트리의 순회를 수행한다. 따라서 시간 복잡도는 O(min(m, n)*2) or O(min(m, n))이다.
• 보조 공간 : 재귀 호출에 사용되는 보조 스택 공간으로 인해 O(log min(n, m))이다.

코드 예시 참고 사이트

우리는 두 트리가 Isomorphic한지 판단하는 방법을 알아야한다.

---

판단 방법

Rooted Tree

rooted tree에서 위상이 같은지 판단하는 것이 unrooted tree보다 편하기 때문에 rooted tree로 먼저 판단해보자!

두 트리 T1, T2가 모두 1개의 정점으로 이루어진 트리라면 당연히 위상이 같다.
두 트리의 루트 노드가 자식을 갖고 있는 경우에는, 각 자식을 루트로 하는 서브트리들이 서로 위상이 같은 경우에만 두 트리가 위상이 같다.

T1의 각 서브트리들을 T2의 어느 서브트리에 매칭시키는지에 따라 위상이 같은지의 여부가 달라지므로, 매칭시키는 방법을 알아보자!

해싱과 비슷하게, 어떤 트리를 고유한 데이터(숫자, 문자열, 괄호열, 튜플 등)으로 표현할 수 있다면, T1과 T2의 각 서브트리들을 이쁘게 정렬해서 차례대로 매칭해주면 된다. 또한, 서브 트리들을 표현하는 고유한 데이터들을 잘 조합해주면 전체 트리를 표현하는 데이터를 뽑아낼 수도 있다.
트리는 재귀적이기 때문에 보기 쉽게 이쁘게 구현할 수 있다.

Unrooted Tree

root를 정하지 않으면 재귀적인 성질을 이용해 무언가를 구하는 것을 할 수 없기 때문에 root를 정해야만 한다!

트리의 centroid를 생각해보자

트리의 centroid
: 트리의 무게중심인 정점.
트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다.

이때 모든 서브 트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다.

Q. 센트로이드는 항상 존재하는가?
A. 그렇다.

증명) 센트로이드 탐색 알고리즘

임의의 노드를 고르자
그 노드를 루트로 하는 트리를 생각한다
모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다.
조건을 만족하지 않는 서브트리가 있다면 그 서브트리의 루트에 위 알고리즘을 적용하여 재귀적으로 탐색한다.
센트로이드 분할 개념 참고 사이트

centroid는 트리에 반드시 1개 혹은 2개 존재합니다.
또한, 2개 존재하는 경우에는 두 centroid가 인접합니다. 그러므로 centroid가 2개 존재하는 경우에는 두 centroid 사이에 새로운 정점을 만들어주면, 그 정점이 centroid가 된다.
만약 T1와 T2가 위상이 같다면 트리의 centroid를 root로 잡아서 만든 rooted tree도 위상이 같다.

centroid는 O(N)에 찾을 수 있기 때문에, unrooted tree의 Isomorphism 여부는 O(N) + (rooted tree의 Isomorphic의 여부를 확인하는 시간) 안에 판별할 수 있다.

개념 참고 사이트

---

동형 검사

: 두 대상의 구조 동일 여부를 검사하는 알고리즘이다.
"순회"가 필요하다.
즉, 양측 대상의 노드와 노드 속 데이터 값이 동일한지 확인 후 각각 다음 노드로 이동하는 과정이 필요하다.
예를 들면, 이진 트리에서의 동형 검사는 다음과 같이 수행되며, 루트(Root) 노드를 시작으로 재귀적으로 들어간다.
1. 두 루트 노드가 둘 다 데이터가 없으면 동형임이 자명하다.
2. 두 루트 노드 중 하나만 데이터가 없으면 이형(Heteromorphism, 형태가 다름)임이 자명하다.
3. 두 루트 노드의 데이터 값이 다르면 이형이다.
4. 두 루트의 좌측 노드를 루트 노드로 가정하여 해당 알고리즘을 다시 수행한다.
5. 두 루트의 우측 노드를 루트 노드로 가정하여 해당 알고리즘을 다시 수행한다.
6. 1~5의 알고리즘에서 다음 검사 대상 노드의 좌우가 바뀌어도 동형(좌우 반전 동형)이다.

트리의 동형 검사는 직관적이기 때문에 그래프의 동형 검사에 비하여 효율적으로 수행된다.
모든 노드에서의 True가 모여야 전체 트리 동형에서 True를 출력할 수 있다.

def TreeIsomorphisTest(RootNodeA, RootNodeB):
    if RootNodeA == None and RootNodeB == None :
        return True
    if RootNodeA != None or RootNodeB != None:
        return False
    if RootNodeA.Data != RootNodeB.Data :
        return False
    return ((TreeIsomorphisTest(RootNodeA.LeftChild, RootNodeB.LeftChild) and
             TreeIsomorphisTest(RootNodeA.RightChild, RootNodeB.RightChild)) or
             (TreeIsomorphisTest(RootNodeA.LeftChild, RootNodeB.RightChild) and
              TreeIsomorphisTest(RootNodeA.RightChild, RootNodeB.LeftChild)))

참고 사이트