[자료구조] 트리(Tree)란

트리(Tree)

트리(Tree)란 노드들이 뒤집어진 나무처럼 연결된 비선형 계층적 자료구조이다.

트리는 그래프 중 특수한 케이스에 해당하며, 사이클이 없고, 최소의 간선을 사용한 연결 그래프를 말한다.

트리의 특징

• 트리는 부모-자식 관계가 존재하며 레벨이 존재한다.

• 부모 노드 밑의 자식 노드에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조이다.

• 노드가 N개이면 간선은 N-1개고, 레벨 K에 존재하는 노드는 최대 2^K개이다.

• 유방향 그래프이며 사이클이 존재하지 않는다.

트리 구조 기본 용어

• 노드(Node): 트리를 구성하는 기본 요소, 값 또는 하위 노드에 대한 키, 포인터를 가지고 있다.

• 간선(Edge): 노드를 연결하는 선.

• 루트 노드(Root Node): 트리 구조에서 부모가 없는 최상위 노드

• 부모 노드(Parent Node): 자식 노드를 가진 노드

• 형제 노드(Sibling node): 같은 부모를 가지는 노드

• 리프 노드(Leaf node): 자식 노드가 없는 노드

• 깊이(Depth, Level): 루트에서 특정 노드까지의 간선 수

• 높이(Height): 특정 노드에서 최하층 리프 노드까지의 간선 수

• 너비(Weight): 특정 레벨에 있는 노드 수

• 차수(Degree, Order): 노드의 자식 수

• 경로(Path): 특정 노드에서 다른 노드까지 이동하는 데 방문하는 노드들의 순서

• 거리(Distance): 특정 노드에서 다른 노드까지의 최단 경로에 있는 간선의 수

그래프와 트리의 비교

	그래프(Graph)	트리(Tree)
모델	네트워크 모델	계층 모델
방향성	방향, 무방향	방향
사이클	허용	비허용
루트노드	없음	한 개의 루트 존재
부모-자식 관계	부모-자식 관계 없음	부모-자식 관계 있음
간선 수	자유	N-1개

트리의 종류

편향 트리 (Skew Tree)

• 모든 노드들이 자식을 하나만 가진 트리

이진 트리 (Binary Tree)

• 부모 노드의 자식 개수를 최대 2개로 제한하는 트리의 가장 간단한 형태이다.

이진 트리에는 다음과 같은 종류가 있다.

• 정 이진 트리 (Full Binary Tree): 모든 트리의 자식은 0개 혹은 2개이다.

• 포화 이진 트리 (Perfect Binary Tree): 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 갖는다. 모든 포화 이진 트리는 정 이진 트리이다.

• 완전 이진 트리 (Complete Binary Tree): 모든 리프 노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 무조건 있는 이진 트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐 없이 채워 나간 형태이다. 포화 이진 트리는 완전 이진 트리의 부분집합이다.

이진 트리 순회 방법

• 중위 순회 (in-order traversal): 왼쪽 자식, 부모, 오른쪽 자식 순서로 방문하는 순회 방법

• 전위 순회 (pre-order traversal): 부모, 왼쪽 자식, 오른쪽 자식 순서로 방문하는 순회 방법

• 후위 순회 (post-order traversal): 왼쪽 자식, 오른쪽 자식, 부모 순서로 방문하는 순회 방법

• 레벨 순서 순회 (level-order traversal): 너비 우선 순회(Breadth-First traversal)이라고도 하며, 레벨 순서로 노드를 방문하는 순회 방법

중위 순회 : 1 3 4 6 7 8 10 13 14 전위 순회 : 8 3 1 6 4 7 10 14 13 후위 순회 : 1 4 7 6 3 13 14 10 8 레벨 순서 순회 : 8 3 10 1 6 14 4 7 13

중위, 전위, 후위 순회는 스택을 활용한 재귀 함수로 구현이 가능한 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다.

이진 탐색 트리 (Binary Search Tree, BST)

이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되어있다. 자식 노드들도 동일한 방법으로 정렬되어 노드의 왼쪽 자식의 왼쪽 가지에는 왼쪽 자식이 가진 값보다 작은 값만 있고, 왼쪽 자식의 오른쪽 가지에는 왼쪽 자식의 값보다 큰 값들만 있고, 오른쪽 자식의 왼쪽 가지에는… 이런 식으로 정렬이 되어 있는 트리이다.

이러한 특성으로 인해 이진 탐색 트리에서는 어떤 값 n을 찾을 때, 루트 노드와 비교해서 n이 더 작다면 루트 노드보다 큰 값들만 모여 있는 오른쪽 가지는 전혀 탐색할 필요가 없고 마찬가지로 루트 노드의 왼쪽 자식보다 n이 크다면 왼쪽 자식의 왼쪽 가지는 탐색할 필요가 없게 된다.

즉 트리 자체가 이진 탐색을 하기에 적합한 구성이 된다. 또한 값을 찾을 때뿐만 아니라 값을 삽입하거나 삭제할 때도 똑같은 과정을 거치므로, 이상적인 상황에서 탐색/삽입/삭제 모두 시간복잡도가 O(logN)이 된다.

다만 단점이 있는데, 값이 삽입되거나 삭제되는 경우에 따라서 운이 안좋으면 최악의 경우에 O(N)의 시간이 걸리게 된다. 예를 들어, 비어있는 이진 탐색 트리에 1부터 100까지 순서대로 삽입한다면 처음 루트 노드는 1이 되고, 2는 1보다 크니 1의 오른쪽 자식이 되고, 3은 1보다 크니 1의 오른쪽, 2보다 크니 2의 오른쪽… 이런 식으로 트리의 오른쪽 끝으로만 계속 성장하게 된다. 이 상태로 50을 찾는다고 하면 결국 1부터 순서대로 오른쪽으로 쭈욱 내려가는 선형 탐색, O(N)이나 다를게 없게 된다. 이러한 경우를 트리가 편향(skew)되었다고 한다.

신장 트리 (Spanning Tree)

• 신장 트리란 그래프의 최소 연결 부분 그래프이다. 즉, 모든 정점 N개가 연결되어 있어야 하며 간선의 수가 가장 적은 N-1개고, 사이클을 포함하지 않은 부분 그래프이다.

• 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.

• DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.

최소 신장 트리 (Minimum Spanning Tree)

• 신장 트리들 중 사용된 간선들의 가중치 합이 최소인 트리이다. 즉, 모든 정점 N개가 연결되어 있어야 하며 간선의 수가 가장 적은 N-1개고, 사이클을 포함하지 않은 최소 비용의 부분그래프이다.

MST의 구현 방법 (MST 알고리즘)

최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘, 즉 MST Algorithm이라고 한다. 대표적인 MST 알고리즘은 Kruskal Algorithm과 Prim Algorithm이 있다.

1. 크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘은 그리디 메소드를 이용하여 MST를 찾는 알고리즘이다.

자세한 내용은 아래 포스팅으로 이동하자.

[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm)

2. 프림 알고리즘 (Prim Algorithm)

프림 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법이다.

그 외 유명한 트리 자료구조 (추후 포스팅)

• 자가 균형 이진 탐색 트리
• AVL 트리
• 레드-블랙 트리
• 스플레이 트리
• 신장 트리, 최소 비용 신장 트리
• B 트리, B+ 트리
• R 트리
• 기수 트리