- 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)
- 트리의 왼쪽 서브 트리를 탐방한다.
- 노드를 방문하고 데이터를 출력한다.
- 트리의 오른쪽 서브 트리를 탐방한다.
-
전순위 탐방(preorder, DLR)
- 노드를 탐방하고 데이터를 출력한다.
- 트리의 왼쪽 서브 트리를 탐방한다.
- 트리의 오른쪽 서브 트리를 탐방한다.
-
후순위 탐방(postorder, LRD)
- 트리의 왼쪽 서브 트리를 탐방한다.
- 트리의 오른쪽 서브 트리를 탐방한다.
- 노드를 탐방하고 데이터를 출력한다.
생성 트리와 최소 비용 생성 트리
-
생성 트리 : 그래프 G에서 모든 노드를 포함하는 트리
-
생성 트리의 비용 : 트리 연결선의 값을 모두 합한 값
-
최소 비용 생성 트리(Minimum Spanning Tree : MST) : 최소 비용을 갖는 생성 트리
-
프림의 알고리즘
- 주어진 가중 그래프 G = (V, E)에서 V = {1, 2, …, n} 이라고 하자.
- 노드의 집합 U를 1로 시작한다.
, 일 때 U, V-U를 연결하는 가장 짧은 연결선을 찾아 v를 U에 포함시킨다. 이때, 사이클을 형성하지 않는 연결선을 찾는다. - 2번의 과정을 U=V 때까지 반복한다.
-
크루스칼 알고리즘
- 주어진 가중 그래프 G = (V, E)에서 V = {1, 2, …, n} 이라고 하고 T를 연결선의 집합이라 하자.
- T를 공집합으로 놓는다.
- 연결선의 집합 E를 비용이 적은 순서로 정렬하다.
- 가장 최소값을 가진 연결선을 차례로 찾아가 사이클을 이루지 않으면 연결선을 T에 포함시킨다.
- 3번의 과정을 T의 원소의 개수 = V의 원소의 개수 - 1