[Python] 트리(Tree)

트리

• 비선형 구조
• 원소들 간에 1:N 관계를 가지는 자료구조
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조
• 노드 중 최상위 노드를 루트(Root)라 함
• 나머지 노드들은 n개의 분리집합 T1, T2, …. TN으로 분리될 수 있음
• 이들 T1, T2, … TN은 각각 하나의 트리가 되며, 루트의 서브 트리(Sub Tree)라고 함

트리 용어 정리

• 노드(node) : 트리의 원소
  • 트리 T의 노드 : A, B, C, D, E, F, G, H, I, J
• 간선(edge) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
• 루트 노드(root node) : 트리의 시작
  • 트리 T의 루트노드 : A
• 서브 트리(sub tree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들
  • B, C, D는 서로 형제 노드
• 조상 노드(ancestor node) : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
  • K의 조상 노드 : F, B, A
• 자식 노드(child node) : 어떤 노드의 바로 아래에 연결된 노드들
  • B의 자식 노드 : E, F
• 자손 노드(descedant node) : 자식노드를 포함해 계층적으로 현재 레벨보다 하위에 존재하는 모든 노드들
  • B의 자손 노드 : E, F, K
• 차수(degree)
  • 노드의 차수 : 노드에 연결된 자식 노드의 수
    • B의 차수 : 2
    • C의 차수 : 1
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
    • 트리 T의 차수 : 3
  • 단말 노드(leaf node) : 차수가 0인 노드. 자식 노드가 없는 노드
    • 트리 T의 단말노드 : E, K, G, H, I, J
• 높이
  

• 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  • B의 높이 : 1
  • F의 높이 : 2
• 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨
  • 트리 T의 높이 : 3

이진 트리

특성

• 모든 노드들이 2개의 서브 트리를 갖는 형태의 트리
• 각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개이며, 최대 $2^{h+1}-1$개가 됨

종류

• 포화 이진 트리(Full Binary Tree)
  • 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
  • 높이가 h일 때, 노드 개수는 $2^{h+1}-1$개를 가진 이진트리
  • 루트를 1번으로 하여 $2^{h+1}-1$까지 정해진 위치에 대한 노드 번호를 가짐

• 완전 이진 트리(Complete Binary Tree)
  • 높이가 h이고 노드 수가 n개일 때 (단, $h+1 ≤ n ≤ 2{h+1}-1$), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

• 편향 이진 트리(Skewed Binary Tree)
  • 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리

트리의 순회

순회(Traversal)

• 순회란 트리의 각 노드를 중복되지 않게 전부 방문(visit)하는 것을 말함
• 트리는 비 선형 구조이기 때문에 선형구조에서와 같은 선후 연결 관계를 알 수 없음

순회 방법

• 전위 순회(Preorder) : VLR
  • 부모 노드 방문 후, 자식 노드를 좌→우 순서로 방문
• 중위 순회(Inorder) : LVR
  • 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문
• 후위 순회(Postorder) : LRV
  • 자식노드를 좌→우 순서로 방문 후, 부모노드 순으로 방문

신장 트리(Spanning Tree)

정의

• 그래프 내의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 부분 그래프 = 간선의 수가 적음
• n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1개
• 즉, 그래프에서 일부 간선을 선택하여 만든 트리

특징

• DFS, BFS를 통해 그래프에서 이용한 간선을 모아 신장 트리를 만들 수 있음
• 하나의 그래프에는 많은 신장 트리가 존재할 수 있음
• 모든 정점들이 연결되어 있어야 하며, 사이클이 존재해서는 안됨
• N개의 정점을 정확히 N-1개의 간선으로 연결해야 함

Union-Find

Parametric Search

이진 탐색(BS, Binary Search)

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

최소 신장 트리(MST, Minimum Spanning Tree)