트리의 구조와 개념 (용어)

 

간선 (edge)

- 노드와 노드를 연결하는 선 

 

내부 노드 (internal Node)

- 자녀 노드를 가지는 노드 (2 5 9 6 11)

 

외부 노드 (external Node, 단말노드 , leaf node)

- 자녀 노드가 없는 노드 (3 7 8 1 4 )

 

노드의 높이

- 노드에서 리프노트까지의 가장 긴 경로의 간선수 (5의 높이 = 2)

 

트리의 높이 

- 루트 노드의 높이 (height = 3)

 

노드의 깊이

- 루트 노드에서 해당 노드까지 경로의 간선수 (11의 깊이 : 2)

 

노드의 차수 (degree)

- 노드의 자녀 노드 수 (11의 차수는 3 ,  3의 차수는 0)

 

트리의 차수

- 트리에 있는 노드들 중 가장 큰 차수를 가지는 노드의 차수 (11 이 제일 많으므로 3)

 

두 노드 사이의 거리 (distance)

- 두 노드의 최단 경로의 간선 수 (9 -> 8 : 2 ,    3 -> 8 : 6)

 

 

노드의 레벨 

- 노드와 루트 노드 사이의 경로에서 간선의 수

(5, 9) -> 레벨1    (6,7,11) -> 레벨2   (3,8,1,4)  -> 레벨3

 

width

- 임의의 레벨에서 노드수 (level 2의 width는 3)

 

노드의 크기

-자신을 포함한 자손 노드의 수 (9의크기: 5   ,  5의 크기 : 4)

 

트리의 주요 특징

1. 루트 노드는 하나만 존재한다.

 

위와 같은 노드는 루프 노드가 2개 이기때문에 트리가 아니다.

 

2. 사이클이 존재하지 않는다. 

한방향으로만 흐르는 구조를 가진다.

 

3. 자녀노드는 하나의 부모 노드만 존재한다.

 

4. 데이터를 순차적으로 저장하지 않는 비선형(nonlinear)구조이다. 

 

5. 트리에 서브트리가 있는 재귀적 구조이며 계층적인 구조를 띈다.

 

이진 트리

각 노드의 자녀 노드 수가 최대 두 개인트리이다.

 

 

 

- full binary tree (정 이진 트리)

모든 노드는 자녀 노드가 없거나 두개인 트리이다.

 

- complete binary tree (완전 이진 트리)

마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 존재하고 

리프노드의 레벨은 왼쪽부터 빠짐없이 노드가 채워져 있는 트리이다.

 

만약 0번이 없거나 4번이 없이 3번의 자녀노드가 존재한다면 완전 이진 트리가 아니다.

 

- perfect binary tree (포화 이진 트리)

모든 레벨에서 노드가 빠짐없이 채워져 있는 트리이다.

 

- balanced binary tree (균형 이진 트리)

모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 트리이다.

 

5의 노드인 경우 : 7의 높이 0 왼쪽은 없으니 -1 --> ok

9의 노드인 경우 : 왼쪽서브트리 높이 1,  오른쪽은 0 --> ok

1의 노드인 경우 : 왼쪽서브트리 높이 0,  오른쪽은 -1 --> ok

모든 노드가 밸런스하다

 

만약 7번 노드가 없다면 루트 노드를 기준으로

왼쪽 서브트리는 높이 0 ,  오른쪽 서브트리는 높이 2이기 때문에 균형 이진 트리가 아니다.

 

 

내용 출처 :

https://www.youtube.com/watch?v=ohrwGtqeW-I