2023-12-08DiscreteStructure-L08

• toc {:toc}

트리의 기본 개념

• 트리 : 하나 이상의 노드로 구성된 유한 집합
• 트리 응용 분야
  • 최적화 문제 해결
  • 알고리즘
  • 분자구조식 설계, 화학결합 표시
• 루트 : 그래프의 시작 노드. 가장 높은 곳에 위치한다.
• 차수 : 해당 노드의 시점에서 서브 트리의 개수
• 잎 노드 : 차수가 0 인 노드, 맨 아래에 위치
• 자식 노드 : 어떤 노드의 서브 트리의 루트 노드
• 부모 노드
• 형제 노드 : 동일한 부모를 갖는 노드
• 중간 노드 : 루트도 아니고 잎 노드도 아닌 노드
• 조상 : 해당 노트부터 루트까지의 경로에 있는 모든 노드
• 자손 : 해당 노드부터 잎 노드에 이르는 모든 노드
• 레벨
• 트리의 높이 : 트리에서 노드가 가질 수 있는 최대 레벨 (트리의 깊이)
• 숲 : 서로 연결되지 않는 트리들의 집합 : 루트를 제거하면 숲을 얻을 수 있다.
• 그래프 G = (V, E) 에서 V 의 원소의 개수 = n, E 의 원소의 개수 = m 일 때 다음은 동치이다.
  • G 는 트리이다.
  • G 는 연결되어 있고 m = n-1 이다. 연결선 = 노드 - 1
  • G 는 연결되어 있고 어느 한 연결선만을 제거하면 G 는 연결되지 않는다.
  • G 는 사이클을 가지지 않는다.
  • G 는 어느 한 연결선만 첨가해도 사이클을 형성한다.
• n- 트리 : 모든 중간 노드들이 최대 n 개의 자식 노드를 가질 때
  • 이진 트리 : n 이 2 인 경우

방향 트리

• 방향이 있고 순서화된 트리
  • 루트 노드가 하나가 있다. 루트에서는 모든 노드로 갈 수 있는 경로가 있다.
• 루트를 제외한 모든 노드들은 오직 하나씩만의 선행자를 가진다.
• 각 노드의 후속자들은 왼쪽으로부터 순서화되어 있다.

이진 트리

• 사향 이진 트리 : 왼쪽, 오른쪽으로 편향된 트리의 구조
• 완전 이진 트리 : 높이가 k 일 때 레벨 1 부터 k-1 까지는 모두 차있고 k 에서는 왼쪽 노드부터 차 있는 이진 트리
• 포화 이진 트리 : 잎 노드가 아닌 것들은 모두 2 개씩의 자식 노드를 가지고 트리의 높이가 일정한 경우
• 이진 트리가 레벨 i 에서 가질 수 있는 최대한의 노드 수 = 개
• 높이가 k 인 이진 트리가 가질 수 있는 최대한의 노드 수 =
• 이진 트리에서 잎 노드의 개수 = n, 차수가 2 인 노드의 개수를 m 이라 할 때 n=m+1 이 항상 성립한다.

이진 트리의 탐방

• 중순위 탐방 (inorder, LDR)

  1. 트리의 왼쪽 서브 트리를 탐방한다.
  2. 노드를 방문하고 데이터를 출력한다.
  3. 트리의 오른쪽 서브 트리를 탐방한다.

• 전순위 탐방 (preorder, DLR)

  1. 노드를 탐방하고 데이터를 출력한다.
  2. 트리의 왼쪽 서브 트리를 탐방한다.
  3. 트리의 오른쪽 서브 트리를 탐방한다.

• 후순위 탐방 (postorder, LRD)

  1. 트리의 왼쪽 서브 트리를 탐방한다.
  2. 트리의 오른쪽 서브 트리를 탐방한다.
  3. 노드를 탐방하고 데이터를 출력한다.

생성 트리와 최소 비용 생성 트리

• 생성 트리 : 그래프 G 에서 모든 노드를 포함하는 트리

• 생성 트리의 비용 : 트리 연결선의 값을 모두 합한 값

• 최소 비용 생성 트리 (Minimum Spanning Tree : MST) : 최소 비용을 갖는 생성 트리

• 프림의 알고리즘

  • 주어진 가중 그래프 G = (V, E) 에서 V = {1, 2, …, n} 이라고 하자.
  1. 노드의 집합 U 를 1 로 시작한다.
  2. , 일 때 U, V-U 를 연결하는 가장 짧은 연결선을 찾아 v 를 U 에 포함시킨다. 이때, 사이클을 형성하지 않는 연결선을 찾는다.
  3. 2 번의 과정을 U=V 때까지 반복한다.

• 크루스칼 알고리즘

  • 주어진 가중 그래프 G = (V, E) 에서 V = {1, 2, …, n} 이라고 하고 T 를 연결선의 집합이라 하자.
  1. T 를 공집합으로 놓는다.
  2. 연결선의 집합 E 를 비용이 적은 순서로 정렬하다.
  3. 가장 최소값을 가진 연결선을 차례로 찾아가 사이클을 이루지 않으면 연결선을 T 에 포함시킨다.
  4. 3 번의 과정을 T 의 원소의 개수 = V 의 원소의 개수 - 1