이산수학 8. 트리

트리

하나 이상의 노드로 구성된 유한 집합으로서

1. 특별히 지정된 노드인 루트(root)가 있고

2. 나머지 노드들은 다시 각각 트리이면서 연결되지 않는 애들로 구성 (서브트리)

 

트리의 응용 분야

- 최적화 문제의 해결

- 알고리즘 (데이터 구조, 정렬)

- 분자구조식 설계와 화학결합의 표시, 유전학

- 언어들 간의 번역, 언어학

- 자료의 탐색, 정렬 데이터베이스 구성

- 사회과학 (조직 분류에 있어서의 구조 등)

 

 

루트(root): 주어진 그래프의 시작 노드

차수(degree): 노드의 서브트리의 개수 A의 차수는 3 (B, C, D)

잎 노드(leaf node): 차수가 0인 노드

자식 노드(children node): 어떤 노드의 서브 트리의 루트 노드들

부모 노드(parent node): 자식 노드의 반대 개념

형제 노드(sibling): 동일한 부모를 가지는 노드

중간 노드(internal node): 루트, 잎 노드가 아닌 그 외 노드

조상(ancestor): 노드 위의 경로 따라 모든 노드들

자손(descendant): 노드로부터 잎 노드에 이르는 모든 노드

레벨(level): 루트를 0으로 두고 자손 노드는 +1하는 것

트리의 높이, 깊이(height, depth): 트리에서 노드가 가질 수 있는 최대 레벨

숲(forest): 서로 연결되지 않는 트리들의 집합으로 루트를 제거하면 얻을 수 있음

* n개의 노드를 가진 트리는 n-1개의 연결선을 가짐

 

n트리란 모든 중간 노드들이 최대 n개의 자식 노드를 가질 수 있을 때

 

8.2 방향 트리

선행자가 없는 루트 노드가 있음

루트 노드를 제외한 모든 노드들은 오직 하나씩만의 선행자가 있음

각 노드의 후속자들은 왼쪽으로부터 순서화 되어 있음

 

8.3 이진 트리

skewed binary tree: 왼쪽 또는 오른쪽으로 편향된 트리의 구조

complete binary tree: 이진트리로 모두 차 있지만 k번째 레벨에서는 왼쪽에서 순서대로 채워진 것

full binary tree: 잎 노드 제외 모든 노드가 채워져있는 것

 

이진트리의 잎 노드의 개수 + 1 = 잎 노드 제외 전체 노드의 개수

 

8.4 이진 트리의 표현

배열, 연결리스트

 

8.5 이진 트리의 탐방

탐방: 각 노드를 한 번씩만 방문하는 것

전위 순회 (RLP)

중위 순회 (LPR)

후위 순회 (LRP)

 

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

생성 트리: spaaning tree, 어떤 그래프 G에서 모든 노드들을 포함하는 트리

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

최소 비용 생성 트리(Minimum Spanning Tree: MST): 최소한의 비용을 가지는 생성 트리

프림 알고리즘: 시작 정점을 고르고 인접한 정점 중에서 가중치가 가장 짧은 정점을 고른다. 그 다음 고른 정점들 중에서 인접한 가중치가 가장 짧은 정점을 골라서 모든 정점을 고를 때까지 반복한다.

크루스칼 알고리즘: 연결선들을 가중치가 적은 순서대로 나열한 후 연결선을 제거한 그래프에서 연결선의 비용이 적은 순서로 사이클이 생기지 않도록 연결해 나가면 된다.

 

8.7 트리의 활용

문법의 파싱

결정트리

게임트리