Tree [트리]

트리의 정의

그래프의 부분집합이다.

그래프 중에서 비순환, 연결 그래프이다.

특징은 노드인 루트(root)가 반드시 하나 있음

트리를 구성하는 꼭짓점 v,w간에 v에서 w로 가는 단순 경로가 있음

Sub Tree의 정의

T를 구성하는 Vertex v를 루트로 하는 트리

Node의 정의

그래프 T를 구성하는 꼭짓점

Root의 정의

그래프 T의 시작 노드, 그래프 T의 가장 높은 곳에 위치

Parent Node 정의

어떤 노드의 한단계 상위 노드

Child Node 정의

어떤 노드의 한 단계 하위 노드

Sibling Node 정의

같은 단계에 있으면서 부모가 같은 노드들

Leaf Node 정의

자식 노드가 없는 노드

Internel Node 정의

루트 노드나 잎노드가 아닌 노드

Ancestor Node 정의

루트 노드에서 어던 노드ㅇ에 이르는  경로에 포함된 모든 노드

Descendant Node 정의

어떤 노드에서 잎 노드에 이르는 경로에 포함된 모든 노드

Degree 정의

어떤 노드에 포함된 자식 노드의 개수

Level 정의

루트 노드를 0으로 시작하여, 자식 노드로 내려갈 때마다 하나씩 증가하는 단계

Height/ Depth 정의

트리가 가지는 최대 레벨

Forest 정의

루트 노드를 제가형 얻는 서브 트리의 집합

문제) 주어진 트리를 보고 다음을 구하라 [그림1]

(1) 트리를구성하는모든노드

p, g, f, k, j, x, y, z

(2) 트리의루트노드 

p

(3) 트리의높이

4

(4) 노드의레벨

p 0 level,

g,x 1 level

f,k,j 2 level

j,z   3 level

(5) 트리의잎노드

f, j,z

(6) 트리의중간노드 

g,k,x,y

(7) 트리의숲

Tree g 로 루트로 갖는 서브트리

Tree x 로 루트로 갖는 서브트리

(8) 트리에서차수가가장높은노드 

p, g Degree == 2

(9) 노드x의자손노드

y,z

(10) 노드j의조상노드 

k, g, p

(11) 노드f의형제노드

k, y

(12) 노드g의자식노드 

f, k

(13) 노드x의부모노드

p

[그림1]

Node와 edge에 관한 정리

Node의 갯수를 v, 변의 개수를 e

e = v -1

Tree에 대한 정리

n개의 꼭짓점을 갖는 연결 그래프 T에 대해 다음은 동치

1) T는 트리다.

2) T의 변의 수는 n-1개이다

3) T에서 변 하나를 제거하면 연결 그래프가 아니다

4) T에 속하는 서로 다른 꼭짓점 w,v,에 대해 w에서 v로 가는 유일한 경로가 존재한다.

2진트리

N 항 트리

트리의 최대 차수가 n인 트리

Binary Tree

트리 T를 구성하는 부모 노드가 갖는 자식노드의 수가 최대 2개인 트리

Complete Binary Tree

높이가 h일때 레벨 1부터 h-1까지 모든 노드가 두 개씩 채워져 있고

레벨 h는 왼쪽부터 노드가 채워져 있는 트리

Full Binary Tree   

포화 이진 트리 높이가 h일 때, 레벨 1에서 h까지 모든 노드가 두 개씩 채워진것

Skewed Binary Tree

왼쪽이나 오른쪽 서브 트리만 가지는 트리

이진 트리의 최대 노드 수

레벨 k에서 가질 수 있는 최대 노드 수 :  2^k개 

높이가 m인 트리가 가질 수 있는 최대 노드 수 : 2^(m+1) -1 개

높이가 m인 이진 트리가 가질 수 있는 최소 노드 수 : m+1 개

이진 트리의 표현

배열로 표현 가능하다... --> 난 어렵다..

연결리스트로 표현 --> 훨씬 쉽다.

이진 트리의 순회

순회 규칙

항상 루트에서 시작한다. 즉 트리의 레벨 0에서 시작

서브 트리에 대한 순회의 순서는 항상 왼쪽에서 오른쪽으로 이루어진다.

데이터를 읽기 전에 왼쪽, 혹은 오른쪽 노드가 있는지 확인하는 작업을 한다.

Preorder Traversal

루트노드-왼쪽노드-오른쪽 노드 순으로 방문하는 순회 방식

노드1에방문:데이터A를읽고(P) 

왼쪽노드가있는지확인 

노드2에방문: 데이터B를읽고(L) 

왼쪽노드가있는지확인

왼쪽노드가없으므로오른쪽노드가있는지확인

오른쪽노드도없으므로, 다시노드1에방문: 오른쪽노드가있는지확인 

노드3에방문: 데이터C를읽고(R) 왼쪽노드가있는지확인

왼쪽노드가없으므로오른쪽노드가있는지확인

오른쪽노드도없으므로다시노드1에방문:순회종료

Inorder Traversal 

왼쪽노드 - 루트 노드 - 오른쪽 노드 순으로 방문하는 순회 방식

노드1에방문:왼쪽노드가있는지확인 

노드2에방문:왼쪽노드가있는지확인 

왼쪽노드가없으므로, 노드2의데이터B를읽는다(L). 

노드2의오른쪽노드가있는지확인: 오른쪽노드도없다. 

다시노드1에방문: 데이터A를읽는다(P). 

노드1의오른쪽노드가있는지확인

노드3에방문:왼쪽노드가있는지확인 

왼쪽노드가없으므로, 노드3의데이터C를읽는다(R)

 노드3의오른쪽노드가있는지확인: 오른쪽노드도없다

. 다시노드1에방문: 순회종

Inorder Traversal

왼쪽노드 - 오른쪽 노드 - 루트 노드 순으로 방문하는 순회 방식

노드1에방문:왼쪽노드가있는지확인 

노드2에방문:왼쪽노드가있는지확인 

왼쪽노드가없으므로, 노드2의오른쪽노드가있는지확인 

오른쪽노드도없으므로, 노드2의데이터B를읽는다(L). 

다시노드1에방문:노드1의오른쪽노드가있는지확인 

노드3에방문:왼쪽노드가있는지확인 

왼쪽노드가없으므로, 노드3의오른쪽노드가있는지확인 

오른쪽노드도없으므로, 노드3의데이터C를읽는다(R)

. 다시노드1에방문:데이터A를읽고(P) 순회종료

이진 탐색 트리(Binary Search Tree)

노드가 가지는 데이터의 크기에 따라 노드의 위취를 탐색할 수 있는 트리

트리에서 탐색되는 모든 원소는 서로 다른 유일키를 갖는다.

왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.

오른쪽 서브 트리에 있는 원소들의 키들은 그 루트의 키보다 크다.

트리의 활용

Spanning Tree

그래프 G의 꼭짓점을 모드 노드로 포함하는 트리 T

Minimal Spanning Tree   

그래흐 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T

비용을 최소로 하는 알고리즘

Prim Algorithm

가중치가 가장 작은 변을 선택 [한번에 하나의 노드만 연결]

연결된 꼭짓점들과 연결된 모든 변들 중 가중치가 가장 작은 변을 선택

가중치가 같은 변은 임의로 선택

선택된 변에 의해 순환이 형성되는 경우는 선택하지 않음

n개의 꼭짓점에 대하여 n-1개의 변이 연결되면 종료

Kruskal Algorithm

가중치가 가장 작은 변을 차례로 선택하여 노드들을 연결 [한번에 여러개 노드 연결]

가장치가 같은 변은 임의로 선택

선택된 변에 의해 회로가 형성되는 경우는 선택하지 않음

n개의 꼭짓점에 대하여 n-1개의 변이 연결되면 종료

Huffman Algorithm

발생빈도가 높은 문자에 적은 비트를 할당하고 발생 빈도가 낮은 문자에는 많은 비트를 할당하기 위한 알고리즘