트리 이론 기본편1 -용어 정리-

1. 트리의 개념

 

비선형 구조

 

원소들 간에 1:n 관계를 가지는 자료구조

 

원소들 간에 계층관계를 가지는 계층형 자료구조

 

상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조

 

###############

 

선형구조와 비선형구조 간단히

 

 

#################################

 

2. 트리의 정의

 

1개 이상의 노드로 이루어진 유한 집합

 

즉, 노드가 1개만 있어도 트리

 

최상위 노드를 root라고 부른다

 

루트 이외의 나머지 노드들은 n개의 부분집합 $T_{1}, T_{2}, T_{3},... , T_{n}$으로 분리 가능하다

 

그림과 같이 $T_{1}, T_{2}, T_{3},... , T_{n}$도 하나의 트리가 되며, 루트의 부 트리(subtree)가 된다

 

그러니까 어떤 tree의 일부를 잘라내도 그것은 트리(tree)

 

 

 

더 이상 밑에 연결된 노드가 없는 E,K,G,H,I,J(파란색으로 칠해진 노드)는 단말 노드, 잎 노드(leaf)라고 부른다

 

 

3. 기본 용어

 

바로 위 그림에서

 

3-1) 노드(node)

 

트리의 각 원소들을 말한다

 

트리 T의 노드들 - A,B,C,D,E,F,G,H,I,J,K

 

 

3-2) 간선(edge)

 

노드를 연결하는 선들

 

부모 노드와 자식 노드를 연결함

 

####################

 

모든 트리는 "노드의 수 = 간선의 수 + 1"이 성립한다

 

그림과 같이 최초에 노드 = 2이면 이들을 연결하는 간선 = 1이고

 

 

여기에 간선이 1 더해지면 노드가 1 더해지므로, 항상 간선의 수 + 1 = 노드의 수

 

 

3-3) 루트 노드(root node)

 

트리의 시작 노드

 

트리 T의 root node는 A

 

T의 서브트리 T1의 root node는 B

 

 

3-4) 부모 노드와 자식 노드

 

위에 있는 노드일수록 특정 노드의 부모 노드

 

아래에 있는 노드일수록 특정 노드의 자식 노드

 

특정 노드에서 바로 밑에 연결된 노드들은 특정 노드의 자식 노드이고 

 

이 자식 노드의 바로 위에 연결된 노드가 부모 노드

 

 

3-5) 형제 노드

 

같은 부모 노드를 가지는 노드들

 

B,C,D는 같은 부모인 A를 가지는 형제노드들

 

 

3-6)조상 노드

 

간선을 따라서 루트까지 갈때, 그 경로의 모든 노드들

 

K의 조상 노드는 A,B,F

 

K의 부모노드는 F

 

------------------------------------------------------------------------------------------

 

노드의 공통 조상??

 

 

K의 조상은 F,B,A이고 E의 조상은 B,A이다

 

E,K의 공통 조상은? B,A

 

 

 

3-7) 서브 트리

 

부모 노드와 연결된 어떤 간선을 끊을때 생기는 임의의 모든 트리들

 

B-F를 끊으면, F-K는 하나의 subtree

 

 

3-8) 자손 노드

 

서브 트리에 있는 하위 레벨의 모든 노드들

 

D의 자손 노드는 H,I,J

 

B의 자손 노드는 E,F,K

 

B의 자식 노드는 E,F

 

 

3-8) 차수(degree)

 

노드의 차수는 노드에 연결된 자식 노드의 수

 

자손이 아니고 자식 노드의 수를 말함

 

 

위 그림에서 B의 차수는 E,F가 자식이므로 2이고 C의 차수는 G가 자식이므로 1이다.

 

A의 차수는 B,C,D가 자식이므로 3이다

 

 

3-9) 트리의 차수

 

트리에 있는 모든 노드들의 차수중에서 가장 큰 값

 

위 트리에서 차수의 최댓값은 A,D의 3이므로 트리의 차수는 3이된다.

 

 

3-10) 단말 노드(leaf 리프 노드)

 

차수가 0인 노드를 말한다.

 

자식이 없는 노드

 

자식이 없으니 자손도 당연히 없음

 

E,K,G,H,I,J가 단말 노드가 된다

 

 

3-11) 높이

 

트리의 루트에서 특정 노드에 이르는 간선의 수

 

노드의 레벨이라고도 부른다

 

 

A는 루트이므로 레벨0, 높이0인 노드

 

## 루트의 레벨을 1부터 시작하는 경우도 있다(상대적임)

 

B,C,D는 A에 이르는 간선의 수가 1개이므로, 레벨1, 높이1인 노드들

 

E,F,G,H,I,J는 A에 이르는 간선의 수가 2개이므로 레벨2, 높이2인 노드들

 

K는 A에 이르는 간선의 수가 3개이므로 레벨3, 높이3인 노드

 

참고로 같은 레벨끼리는 연결되지 않는다

 

그것은 트리가 아니고 그래프라고 부른다

 

 

3-12) 트리의 높이

 

노드의 높이중에서 최댓값

 

위 트리에서 최댓값이 3이므로 트리의 높이는 3이다

 

 

##########

 

문제를 잘 바꿔서 표현해보니 트리

 

거기에 트리 알고리즘을 응용할 수 있어야함