트리(Tree)

트리(Tree)

트리

- 나무와 유사하게 계층적 구조를 띄고 있는 자료구조

- 주된 목적은 탐색이며, 의사 결정, 파일 시스템, DBMS 등 다양한 곳에서 응용됨

트리의 구조

- 뿌리(Root), 가지(Branch), 잎(Leaf, 단말 - Terminal) 세가지 요소로 이루어져 있다.

- 뿌리(Root) 노드 : A

- 가지(Branch) 노드 : B, C, D, E, F, G

- 잎(Leaf), 단말(Terminal) 노드 : I, J, K, L

- B와 C는 형제 노드, D와 E는 B의 자식 노드, A는 B의 부모 노드

트리의 용어

- 경로(Path) : 한 노드에서부터 다른 노드까지 이르는 길 사이에 놓여있는 노드들의 순서

- 길이(Length) : 경로가 가지는 속성, 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수

- 깊이(Depth) : 루트 노드에서 해당 노드까지의 경로의 길이

- 레벨(Level) : 깊이가 같은 노드의 집합

- 높이(Height) : 루트에서부터 '가장 깊은 곳'에 있는 단말 노드까지의 깊이

- 차수(Degree) : 노드의 차수 - 해당 노드의 자식 노드의 개수

트리의 차수 - 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수

- B to F의 경로 : B, D, F

- B to F의 길이 : 2

- 레벨 2 : C, D, H, J

- 높이 : 4

- B 노드의 차수 : 2

- 트리의 차수 : 3 (A 노드의 차수)