트리 구조

트리구조

계층적인 구조를 표현

- 조직도

- 디렉토리와 서브 디렉토리 구조

- 가계도

 

트리는 노드들과 노드들을 연결하는 링크들로 구성된다.

 

용어

루트 노드 - 부모가 없는 노드, 트리는 하나의 루트 노드만을 가짐.

 

단말 노드 - 자식이 없는 노드.

 

내부 노드 - 단말 노드가 아닌 노드

 

링크 - 노드를 연결하는 선

 

형제 - 같은 부모를 가지는 노드

 

 

노드의 크기 - 자신을 포함한 모든 자식 노드의 개수

- C의 크기 : 6

 

노드의 깊이 - 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

- D의 깊이 : 2

- L의 깊이 : 3

 

노드의 레벨 - 트리의 특정 깊이를 가지는 노드이 집합

- A의 레벨 1

- B , C의 레벨 : 2

- D, E, F, G, H, 의 레벨 : 3

- I, J, K, L, M, N 의 레벨 : 4

 

노드의 차수 - 하위 트리 개수 / 간선 수 (degree) = 각

노드가 지닌 가지의 수

- A의 차수 = 2

- B의 차수 = 3

- C의 차수 = 2

 

트리의 차수 - 트리의 최대 차수

- B가 최대 차수를 가짐 => 3

 

트리의 높이 - 루트 노드에서 가장 깊숙히 있는 노드의 깊이

- 3

 

트리의 기본 성질

- 노드가 N개인 개인 트리는 항상 N - 1개의 링크를 가진다.

- 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다.

또한 임의의 두 노드 간의 경로도 유일. (같은 노드를 두번 이상 방문하지 않는다는 조건)

 

 

 

이진 트리

1) 개념

 

이진 트리에서 각 노드는 최대 2개의 자식을 가진다.

각각의 자식 노드는 자신이 부모의 왼쪽 자신인지 오른쪽 자식인지가 지정된다.

-자식이 한명인 경우에도 적용

 

2)종류

 

포화 이진 트리 - 모든 레벨에서 노드들이 모두 채워져 있는 트리

 

완전 이진 트리 - 마지막 레벨을 제외하고 노드가 모두 채워져 있는 트리

 

 

 

3)이진 트리 특징

 

높이가 h인 포화 이진 트리(full binary tree)는 2h−12h−1개의 노드를 가진다.

 

노드가 N개인 포화(full) 혹은 완전(complete) 이진 트리의 높이는 O(logN)O(logN)이다.

 

노드가 N개인 이진트리의 높이는 최악의 경우 O(N)O(N)이 될 수 있다.

 

 

참고

https://jiwondh.github.io/2017/10/15/tree/