트리 (1) - 트리의 특성

트리는 그래프 시리즈만큼 내용상 순차적으로 잘 연결되게 연재하지는 않을 것 같다. 트리가 정의상 그래프의 부분집합이기도 하고, 겹치는 아이디어가 꽤 있기 때문이다. 세그먼트 트리 등의 경우 이미 잘 설명하고 있는 다양한 출처가 존재하는 것도 한몫한다. 그럼에도 불구하고 트리는 자료 구조의 측면에서 활용되고 설명할 거리가 많아 그래프와는 분리하였다. 여기서는 어느 정도의 그래프 이론 지식이 있음을 전제하고 설명한다.

 

 

트리의 정의와 특성

사이클이 없는 연결 그래프를 트리(Tree)라고 한다. 이 단순한 정의로부터 다양한 특성들이 도출된다.

 

• 정점이 $N$개인 트리의 간선 수는 $N-1$개이다.
• 모든 간선은 단절선(bridge)이 된다. 즉 간선을 없애면 그래프가 분리된다.
• 반대로 (중복 및 self-loop가 아닌) 간선을 1개 이상 추가하면 반드시 사이클이 생긴다.
• 한 정점에서 다른 정점으로 가는 길은 유일하다.
• 트리에서 아무 정점이나 잡아 루트로 만드는 것이 가능하다. (중력이 작용하듯이 루트 정점을 잡고 들어올리는 것을 상상해 보자)

 

트리에서 루트(root) 노드를 설정하면, 그에 따라 각 노드의 부모-자식 관계, 리프(leaf) 노드, 깊이(depth) 등이 결정된다. 여러모로 그래프보다 정형적이고 다루기 훨씬 간편하기 때문에, 많은 보편화된 자료 구조들은 트리 구조에 기반한다. 

 

 

이진 트리

모든 노드들이 둘 이하의 자식을 가지면, 이진 트리(binary tree)라고 한다. 두 자식을 보통 left/right child로 명명하며 각각 존재할 수도, 존재하지 않을 수도 있다. 이진 트리가 따로 중요하게 다뤄지는 이유는, 트리의 자손 수를 2로 한정시켜 놓아 그래프의 배열화가 가능하기 때문이다. 다음과 같이 배열의 인덱스를 관리하여 배열을 이진 트리로 사용하는 것이 가능하다.

 

• 배열의 크기는 $4N$ 정도면 넉넉하며, 루트 노드의 인덱스는 1로 한다.
• 특정 노드의 왼쪽 자식에 접근하고 싶은 경우, $A[2idx]$를 방문한다.
• 특정 노드의 오른쪽 자식에 접근하고 싶은 경우, $A[2idx+1]$을 방문한다.
• 반대로 부모에 접근하고 싶다면 $A[idx//2]$로 가능하다.

 

이는 우선순위 큐(힙)나, 세그먼트 트리의 기초가 되는 개념이므로 잘 알아놓으면 좋다. 추가로 이진 트리의 경우 왼쪽 서브트리, 루트, 오른쪽 서브트리 중 우선순위를 정하여 순회하는 이진 트리 순회라는 개념도 있다.

 

 

일반적인 트리의 구현 방법

이진 트리가 아닌 경우에는, 결국에는 그래프와 비슷하게 인접 리스트로 구현하게 된다. 다만 그래프 이론에서 배우는 몇 가지 행동들을 구현할 때 다소 수월한 포인트들이 있다.

 

• 루트 노드가 있다면, parent 배열을 만들어서 각 노드의 부모를 지정해 준다.
• 이는 한 번의 dfs/bfs로 가능한데, 인접한 정점이 부모가 아닌 경우 탐색하면 된다. 이때 visitied를 따로 관리할 필요가 없다. 사이클이 없기 때문이다.
• 마찬가지로 트리 dp 등의 상황에서도 visited를 관리할 필요 없이, 리프 노드들을 모은 다음 합치면서 올라가거나, 루트 노드에서부터 차례로 내려가면 된다.
• 각 노드와 트리를 class화 시켜 구현하는 것도 가능하지만, 끔찍하게 느리기 때문에 잘 사용하지 않는다.

 

아래는 대표적인 트리 dfs의 코드이다. 루트 노드를 1번으로 하여 각 노드들의 부모를 구한다.

N = int(input())
adj = defaultdict(set)
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].add(b)
    adj[b].add(c)

parent = [0]*(N+1)
stack = [1]
while stack:
    u = stack.pop()
    for v in adj[u]:
        if v == parent[u]: continue
        parent[v] = u
        stack.append(v)