1. 트리 관련 주요 용어
ㅇ 노드/마디/정점 (Node/Vertex)
- 트리를 구성하는 기본 원소
. 例) A,B,C,D,E,F,G,H,I,J,K,L,M,N
ㅇ 가지/관계/분기/링크 (Branch/Edge/Link)
- 노드와 노드 간의 연결선
- (드물게, 뿌리(root)와 잎(leaf) 사이의 모든 노드를 일컫기도 함)
ㅇ 부(하위) 트리의 차수/갯수/간선수 (Degree)
- 각 노드가 지닌 가지의 수 (한 노드에 연결된 자식 노드의 수)
. 例) A의 차수 = 2, B의 차수 = 3, C의 차수 = 2
.. 즉, 부 트리(subtree)의 갯수를 그 노드의 degree 라고 함
* [참고] 모든 노드의 차수가 2 이하인 트리 ☞ 이진 트리 참조
ㅇ 계수 (Order) (드물게,차수라고도 하나 올바른 용어는 아님)
- 자식 노드들 중 최대 개수
. 例) B가 가장 많은 자식 3을 갖으므로 계수 = 3
ㅇ 레벨 (level), 높이 (height), 깊이 (depth)
- 레벨(수준) : 루트로부터 단순 경로의 길이
. 例) A(루트)의 레벨 : 0 ; B,C의 레벨 : 1 ; D,E,F,G,H의 레벨 : 2
- 높이 (깊이) : (최대 레벨 값 + 1)
. 例) 가장 긴 깊이 (높이) : 4
* 한편, 이진 트리에서,
. 레벨 i에서의 최대 노드의 수 : 2i개
. 높이 j를 갖는 이진 트리의 최대 노드 수 : 2j-1개
ㅇ 경로 (path), 길이 (length)
- 경로 (path) : 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
- 경로 길이 (length) : 출발 노드에서 목적 노드까지 거치는 노드의 갯수
ㅇ 루트 노드 (root node, 뿌리), 리프 노드 (leaf node, 잎)
- 부모가 없는 최상위 루트 노드(트리 자료구조의 진입 노드) : root node
. 例) 루트 노드 : A
- 맨 마지막 끝 노드 : leaf node
. 例) 잎 노드 : F,I,J,K,L,M,N
ㅇ 단/끝단/단말 노드 (terminal node), 가지 노드 (branch node), 리프 노드(잎,leaf node)
- 가지를 가지지 않는 즉, degree가 0 인 노드를,
단말 노드(terminal node)라 하며,
. 例) 단말 노드 : F,I,J,K,L,M,N
- degree가 0 이 아닌 노드들을,
간노드(non-terminal node)/가지노드(branch node)라 함
. 例) 가지 노드 : A,B,C,D,E,G,H
ㅇ 자식 (child), 부모 (parent) 노드, 형제 (brother) 노드
- 부모 노드 (parent node) : 例) D,E,F의 부모노드는 B
- 자식 노드 (child node) : 例) B의 자식노드는 D,E,F
- 형제 노드 (brother node,sibling) : 例) D,E,F는 동일한 부모를 갖는 형제노드
- 선조 (ancestor) : 부모 노드와 그의 부모들을 총칭
- 자손 (descendant) : 자식 노드와 그 자식들을 총칭
ㅇ 크기 (size)
- 특정 노드가 자신을 포함한 자손의 수
. 例) 노드 C의 크기 : 6
ㅇ 서브 트리 (subtree)
- B를 루트로 하는 하위 트리를 A의 왼쪽 서브 트리,
C를 루트로 하는 하위 트리를 A의 오른쪽 서브 트리 라고 함