[자료구조] 트리(Tree)

트리(Tree) 란?​

• 트리는 노드로 이루어진 자료 구조
  • 트리는 하나의 루트 노드를 갖음
  • 루트 노드는 0개 이상의 자식 노드를 갖고 있음.
  • 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있음.
• 노드와 노드는 서로를 연결하는 간선들로 구성.
  • 트리에는 사이클(cycle)이 존재할 수 없음.
  • 노드들은 특정 순서로 나열될 수도, 아닐 수도 있음.
  • 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있음.
  • 각 노드는 어떤 자료형으로도 표현 가능함.
• 비선형 자료구조로 계층적 관계를 표현함.
• 그래프의 한 종류
  • 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
  • DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류.

 

트리의 특징​

• 그래프의 한 종류로,  '최소 연결 트리' 라고도 불림.
• 계층 모델
• DAG(방향성이 있는 비순환 그래프)의 한 종류
  • loop나 circuit이 없다.
  • 즉, 사이클이 없다
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가짐.
  • 즉, 간선은 항상 (정점의 개수 -1)만큼을 가짐.
• 루트에서 어떤 노드로 가는 경로는 유일.
  • 임의의 두 노드 간의 경로도 유일. 즉, 두 개의 정점 사이에 반드시 1개의 경로만 존재.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가짐
• 트리는 이진트리, 이진 탐색트리, 균형트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 존재.
  .
• 순회는 Pre-order, In-order, Post-order 가 있음.
  
  부모 노드를 언제 방문하는지에 따라 이름이 붙어졌다고 생각하면 쉽다.
  
  • Pre-order(전위 순회) : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
  • In-order(중위 순회) : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
  • Post-order(후위 순회) : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드
    
    
• 예시로, 아래 그림에서 순회 순서는 다음과 같다.
  
  • Pre-order(전위 순회)는 1 -> 2 -> 4 -> 5 -> 3
  • In-order(중위 순회)는 4 -> 2 -> 5 -> 1 -> 3
  • Post-order(후위 순회)는 4 -> 5 -> 2 -> 3 -> 1

 

 

 

Mininum Spanning Tree(최소 신장 트리)​

Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리이다.

• Spanning Tree는 그래프의 최소 연결 부분 그래프라는 특징을 가짐.
  (최소 연결 = 간선의 수가 가장 적음)
• 하나의 그래프에는 다수의 신장 트리가 존재할 수 있음.
• Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야하고 사이클을 포함해서는 안됨.
• MST(최소 신장 트리)는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말함.

 

트리의 용어​

출처 : https://galid1.tistory.com/174

• 노드의 차수- 한 노드가 가진 서브트리의 수
  • A의 차수: 3
  • B의 차수: 2
  • C의 차수: 0
• 리프노드(단말,터미널) - 차수가 0인 노드
  • 리프노드: E, J, K, L, H, I, C
• 자식노드- 노드에 연결된 서브트리의 루트노드들
  • A의 자식노드: B, C, D
• 부모노드- 노드에 연결된 한단계 상위 레벨 노드
  • I의 부모노드: D
• 형제 노드- 부모가 같은 노드
  • G, H, I는 형제노드
• 트리의 차수- 트리노드들의 차수중 최대 차수
  • 트리의 차수:3
• 트리의 깊이(높이)- 트리의 최대 레벨
  • 트리의 깊이: 3

 

트리의 종류​

 

 

이진트리(Binary tree)​

• 이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리.
• 이진트리에는 정이진트리, 완전이진트리, 균형이진트리 등이 존재.

 

트리의 순회(Tree Traverse)​

위에서 설명한 트리의 순회를 좀 더 복잡한 그래프를 가지고 설명하자면,

• 전위 순회(preorder traverse): 루트를 먼저 방문
• 중위 순회(inorder traverse): 왼쪽 하위 트리를 방문 후 루트를 방문
• 후위 순회(postorder traverse): 하위 트리 모두 방문 후 루트를 방문

전위순회: 0->1->3->7->8->4->9->10->2->5->11->6

중위순회: 7->3->8->1->9->4->10->0->11->5->2->6

후위순회: 7->8->3->9->10->4->1->11->5->6->2->0

위와같은 순서로 각 순회를 진행하게 된다.

 

 

이진트리의 시간복잡도​

이진트리의 시간복잡도는 순회만 했을 때 기준으로 O(N).

하지만, 탐색에 대한 기준이 있다면 이를 이진탐색트리(binary search tree)라고 하는데

이럴 경우 트리의 높이만큼의

시간이 소요되므로 탐색의 시간복잡도는 O(h)이다.

 

따라서 균형이 잡힌 이진트리의 경우 O(logN)의 시간복잡도를 가지게된다.

그래프와 트리의 차이​