[알고리즘 강의] 파트17. 트리(Trees)

트리 (Tree)

정점 (node) 과 간선 (edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료 구조

용어 정리

- 루트 (root) 노드: A

- 리프 (leaf) 노드: G, H, J, E, K

- 내부 (internal) 노드 - B,D,C,F

- 부모 (parent) 노드

ex. 노드 D는 노드 G,H,J의 부모

- 자식 (child) 노드

ex. 노드 E는 노드 C의 자식

- 노드 G,H,J는 서로 형제간 (sibling)

- 조상 (ancestor): 부모의 부모(의 부모의...)

- 후손(descendant): 자식의 자식(의 자식의...)

 

노드의 수준 (Level)

Root node가 level 0 이며 아래로 내려갈수록 노드의 level 증가

ex. 위의 트리에서는 위부터 아래 순서대로 level이 0,1,2,3

 

트리의 높이 (Height)

트리의 높이(height) = 최대 수준 (level) +1

* 깊이(depth) 라고도 함

ex. 위의 트리의 height 는 4

 

부분 트리 (서브트리 - Subtree)

 

노드의 차수 (Degree)

= 자식 (서브트리) 의 수

ex. A는 degree가 2

ex. B는 1, C는 2

ex. D는 3, F는 1

ex. G,H,J,E,K 는 0 -> leaf nodes

 

이진 트리 (Binary Tree)

- 모든 노드의 차수가 2 이하인 트리

- 재귀적으로 정의할 수 있음:

  빈 트리 (empty tree) 이거나

  루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리

  (단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리)

 

포화 이진 트리 (Full Binary Tree)

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

(높이가 k 이고 노드의 개수가 2^k - 1 인 이진 트리)

 

완전 이진 트리 (Complete Binary Tree)

높이 k 인 완전 이진 트리:

레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리

레벨 k-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리