[트리] 자료구조 알아보기 : Programming Story

트리란 자료구조의 일종으로 그래프의 특수한 경우라고 볼 수 있다.

트리의 개념

위의 모양과 같은 것을 "트리" 자료구조라고 부른다.

위의 사진을 보면 정점의 개수는 3개, 간선의 개수는 2개이다.

즉 우리는 트리의 성질을 만족시키기 위해서는 정점의 개수가 V개, 간선의 개수가 V-1개여야 한다는 것을 알 수 있다.

하지만 정점의 개수보다 간선의 개수가 하나 더 적다고 해서 무조건 트리 구조가 만들어지는 것은 아니다. 추가로 사이클이 없는 연결된 그래프여야 한다는 조건이 붙는다.

만약 그래프가 연결되지 않는다면 간선과 정점 사이의 관계가 만족이 되더라도 트리 모양이 되지 않을 수 있다.

즉, 정점의 개수가 A개 이고 간선의 개수가 A-1개이며, 모든 점들이 연결되어있다면 트리구조라고 할 수 있다.

트리구조에서 쓰이는 용어

트리 구조에서는 루트를 지정할 수도 있고 지정하지 않을 수도 있는데, 만약 루트를 지정한다면 그것은 부모가 없는 노드를 지칭한다. 즉 위의 그림에서는 A 노드가 루트인 것이다. 그리고 A 노드는 B과 C 노드의 부모라고 할 수 있고 반대로 B와 C노드는 A 노드의 자식이라고 할 수 있다.

또한 B와 C 노드는 자식이 없기 때문에 이러한 노드를 우리는 단말 정점 (Leaf Node / Terminal Node) 라고 하기도 한다. 트리구조에서 깊이는 루트 노드에서부터의 거리를 의미한다. 루트의 깊이를 0으로 하는 경우과 1로 생각하는 경우 모두 존재하는데, 0으로 하는 경우에 위 사진에서 B와 C노드의 깊이는 1이고, 루트의 깊이를 1로 생각하면 B와 C 노드의 깊이는 2라고 할 수 있다.

트리구조에서 "높이"는 위의 깊이 중에서 가장 큰 값을 의미한다.

조금 더 복잡한 트리는 위와 같은 경우라고 할 수 있는데 위의 경우에서 높이를 구해보면 2 또는 3이라고 할 수 있다. 2는 루트의 깊이를 0으로 생각한 경우이고, 3은 루트의 깊이를 1로 생각한 경우이다.

트리의 종류

알고리즘에서 주로 다루고 가장 인기 많은 형태의 트리는 [이진트리]이다. 이진트리 (Binary Tree)란 자식을 최대 2개만 가지고 있는 트리를 뜻한다. 위의 그림의 경우 A 노드의 자식은 B와 C, B노드의 자식은 D와 E, C 노드의 자식은 F와 G이기 때문에 이진 트리의 조건을 만족시킨다.

이진 트리는 "포화 이진 트리"와 "완전 이진 트리"가 있다. 완전 이진 트리는 포화 이진 트리를 포함하는 개념이다.

포화 이진 트리란 위의 그림처럼 단말 정점 (Leaf node)를 제외하고는 모든 노드의 자식 수가 2개로 구성되어 있는 것이다. 말 그대로 포화가 된 것인데, 꽉꽉 차 있어야 하는 구조이기 때문에 자연스럽게 모든 리프 노드의 깊이는 같을 수밖에 없고 만약 높이가 h라면 (루트의 깊이를 1로 봤을때), 트리의 전체 노드의 개수는 2^h-1개가 되어야 한다.

반면, 완전 이진 트리는 포화 이진 트리에서 조건이 조금 더 완화된 형태의 트리를 말한다.

대부분 포화 이진 트리와 유사하나, 마지막 리프 노드 레벨에서는 노드 일부가 없을 수도 있는 형태를 의미한다. 즉, 꼭 없어야 하는 것은 아니기 때문에 포화 이진 트리 또한 완전 이진 트리의 일부이다. 완전 이진 트리는

위의 그림처럼 리프 노드 단계에서 오른쪽에서부터 몇 개가 사라진 형태를 의미한다.

트리의 표현

트리를 표현하는 방법에는 여러가지가 있을 수 있는데 이진트리의 경우에는 클래스/구조체를 통해서 많이 표현한다. 클래스와 구조체를 통해 표현하는 이유는 모든 노드마다 왼쪽 자식노드, 오른쪽 자식노드의 구성요소를 가지고 있기 때문이다.

또는 트릐의 부모를 저장하는 방식이 있을 수 있다. 각 노드마다 노드의 부모를 저장하고 만약 부모가 없는 루트 노드의 경우 0같은 숫자로 예외 처리를 해주는 것이다. 예를 들어,

위와 같은 구조에서는

노드 숫자	1	2	3	4	5	6	7
부모노드	0	1	1	2	2	3	3

라는 테이블로 노드의 부모를 저장해놓는 방식이다.

또 다른 표현 방식으로는 각 노드를 나타내는 배열을 만들수도 있다.

만약 부모 노드가 X인 경우, 왼쪽 자식 노드는 2*X, 오른쪽 자식 노드는 2*X+1로 나타내면 모든 노드를 겹치지 않게 나타낼 수 있다.

트리의 순회

이제 트리의 개념을 알아봤으니 어떻게 트리의 모든 노드를 방문할 수 있는지 알아보자.

트리를 순회하는 방법은 크게 프리오더(Pre-Order), 인오더(In-Order), 포스트오더(Post-Order) 이렇게 세 가지 방법이 있다.

위와 같은 그림으로 예시를 들어보자

1. Pre-Order (현재 노드 -> 왼쪽 자식 노드 서브트리 pre-order -> 오른쪽 자식 노드 서브트리 pre-order)

현재 노드 방문

왼쪽 자식 노드를 루트로 하는 서브 트리 Pre-Order

오른쪽 자식 노드를 루트로 하는 서브 트리 Pre-Order

따라서 Pre-Order의 경우 1 노드를 먼저 방문한다 --> 이후 왼쪽 자식 노드 (2)를 루트로 하는 서브 트리에서 Pre-Order를 시행한다 (2 방문 -> 왼쪽 자식 노드 4 방문 -> 오른쪽 자식 노드 5 방문) --> 이후 오른쪽 자식 노드 (3)을 루트로 하는 서브 트리에서 Pre-Order를 다시 시행한다 (3 방문 -> 왼쪽 자식 노드 6 방문 -> 오른쪽 자식 노드 7방문)

이런식으로 진행을 하여 최종적으로 순회한 순서는

1 2 4 5 3 6 7 이라고 할 수 있다.

2. In-Order (왼쪽 자식 노드 서브트리 in-order -> 현재 노드 -> 오른쪽 자식 노드 서브트리 in-order)

왼쪽 자식 노드를 루트로 하는 서브 트리 In-Order

현재 노드 방문

오른쪽 자식 노드를 루트로 하는 서브 트리 In-Order

위의 그림으로 똑같이 예시를 들면 In-Order 순서는 다음과 같다.

1의 자식노드 2를 루트로 하는 서브 트리 In-Order (왼쪽 자식 노드 4 방문 --> 현재 노드 2 방문 --> 오른쪽 자식 노드 5 방문) --> 현재 노드 1 방문 --> 오른쪽 자식 노드 3을 루트로 하는 서브 트리 In-Order (왼쪽 자식 노드 6방문 -> 현재 노드 3 방문 -> 오른쪽 자식 노드 7방문 )

이런식으로 하여서 최종 순서는

4 2 5 1 6 3 7 이라고 할 수 있다.

3. Post-Order(왼쪽 자식 노드 서브 트리 post-order -> 오른쪽 자식 노드 서브트리 post-order -> 현재 노드 )

왼쪽 자식 노드를 루트로 하는 서브트리 post-order

오른쪽 자식 노드를 루트로 하는 서브트리 post-order

현재 노드

위의 같은 그림으로 예시를 들어보면 post-order 순서는 다음과 같다.

왼쪽 자식 2를 루트로 하는 서브트리 post-order (왼쪽 자식 노드 4 -> 오른쪽 자식 노드 5 -> 현재 자식노드 2) -> 오른쪽 자식 3을 루트로 하는 서브트리 post-order (왼쪽 자식 노드 6 -> 오른쪽 자식 노드 7 -> 현재 자식 노드 3) -> 현재 노드 1 방문

이런식으로 하여서 최종 순서는

4 5 2 6 7 3 1 이라고 할 수 있다.

위의 세 가지 타입의 트리의 순회 중에서 In-Order 타입의 순회는 이진트리에서만 사용이 가능하다. 인오더는 왼쪽, 오른쪽이 나뉘어 있어야 하기 때문에 이진트리가 아닌 경우 사용할 수 없다.

알고리즘 문제를 풀 때 자주 등장하는 타입은 포스트 오더 (Post-Order)인데 이는 포스트 오더가 자식 노드를 다 방문한 뒤에 부모 노드를 방문하는 형식이기 때문이다. 이는 자식에 대한 값을 바탕으로 부모 노드를 파악하는 문제의 형식에서 많이 사용된다.

여기서 Pre-Order, In-Order, Post-Order의 이름과 방법을 매치시키기 어려울 수 있는데 이렇게 알고 있으면 편하다.

Pre-Order는 현재 노드를 Pre(전) : 미리 방문한다는 것이고, Post-Order는 현재 노드를 Post(후): 나중에 방문한다는 것이다. 따라서 프리 오더는 자식 노드를 방문하기 전에 부모 노드를 먼저 방문하고, post-order는 자식 노드를 다 방문한 후에 부모 노드를 방문하는 것이다. 그리고 In-Order는 전,후가 둘다 아닌 왼쪽 자식 노드를 방문한 다음에 중간에 부모 노드를 방문하고 다시 오른쪽 자식 노드를 방문하는 타입이다. 즉, 이름의 기준을 부모 노드로 잡고 생각하면 편하다.