트리 용어

1 목록[ | ]

한국어명	영어명	비고
루트 노드	root	트리의 최상위 노드
자식 노드	child	어떤 노드의 '직접적인' 하위 노드
부모 노드	parent	어떤 노드의 '직접적인' 상위 노드
후손 노드	descendant	어떤 노드의 모든 하위 노드
선조 노드	ancestor	어떤 노드의 모든 상위 노드
말단 노드	leaf	자식 노드가 없는 노드
내부 노드	internal node	자식 노드가 1개 이상 있는 노드
외부 노드	external node	자식 노드가 없는 노드 (leaf와 동일하게 쓰이기도 함)
차수	degree	노드가 가진 자식(또는 연결된 간선)의 개수 (트리 전체의 차수는 모든 노드의 차수 중 최댓값)
엣지	edge	트리에서 노드와 노드를 연결하는 선
경로	path	노드 간 이동 시 거치는 노드들의 열(列), 또는 이를 연결하는 연속된 엣지들의 수열
레벨	level	루트 노드로부터 떨어진 ‘단계 수’ (일반적으로 루트 노드는 레벨 0으로 둠)
노드의 높이	height of node	해당 노드에서 가장 깊은 말단 노드(leaf)까지의 최대 엣지 수(혹은 단계 수)
트리의 높이	height of tree	루트 노드의 높이. 즉, 루트에서 가장 깊은 말단 노드까지의 최대 엣지 수(혹은 단계 수)
깊이	depth	루트 노드에서 특정 노드까지 이동하는 데 거치는 엣지 수(혹은 단계 수)
숲	forest	둘 이상의 서로 독립된(연결되지 않은) 트리들의 집합

※ 레벨(level), 깊이(depth), 높이(height)는 간선 수를 기준으로 할 수도 있고, 노드 수(루트를 1로 보는 방식 등)를 기준으로 할 수도 있으므로, 사용하는 맥락에 따라 정의를 약간씩 달리 적용할 수 있다.
※ 차수(degree) 또한 일반적으로 “노드가 가진 자식의 개수”를 의미하지만, 그래프 이론에서는 “해당 노드에 연결된 간선의 수”를 의미하기도 하므로 상황에 따라 다르게 해석될 수 있다.