티스토리 뷰
트리의 정의
- 트리 : 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태
- 가족의 계보(족보), 연산 수칙, 회ㅏ 조직 구조도, 히프(Heap) 등을 표현하기에 적합함
트리 관련 용어
- 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목데 대한 가지(Branch)를 합친 것
＊ 예 ) A, B, C, D, E, F, G, H, I, J, K, L, M
- ★ 근 노드(Root Node) : 트리의 맨 위에 있는 노드
＊ 예 ) A
- ★ 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수
＊ 예 ) A = 3, B = 2, C = 1, D = 3
- ★ 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
＊ 예 ) K, L, F, G, M, I, J
- 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
＊ 예 ) A, B, C, D, E, H
- 조상 노드(Ancestors Node) : 임의의 노드에서 근 노드에 이르느 경로상에 있는 노드들
＊ 예 ) M의 조상 노드는 H, D, A
- 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
＊ 예 ) D의 자식 노드 : H, I, J
- 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들
＊ 예 ) E, F의 부모 노드는 B
- 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들
＊ 예 ) H의 형제 노드는 I, J
- Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L + 1
＊ 예 ) H의 레벨은 3
- 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대의 레벨
＊ 예 ) 위 트리의 깊이는 4
- 숲(Forest) : 여러 개의 트리가 모여 있는 것
＊ 예 ) 위 트리에서는 근 노드 A를 제거하면 B, C, D를 근 노드로 하는 세 개의 트리가 있는 숲이 생긴다
- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수
＊ 예 ) 노드 A나 D가 세 개의 디그리를 가지므로 위 트리의 디그리는 3