[자료구조] 트리 용어란?

✨트리(Tree) 란?  

 

부모-자식 개념을 가지는 비순환적 경로로 연결되어있는 자료구조입니다.

 

by yunamom

 

✨트리 관련 주요 용어  

 

by yunamom

구분	설명	예시
Node	트리를 구성하는 기본 원소	예) A,B,C,D,E,F,G,H,I,J
Root node (뿌리 노드)	(뿌리)부모가 없는 최상위 루트 노드 트리는 하나의 루트 노드만을 가진다.	예) A
Leaf node (잎 노드)	자식이 없는 노드 (맨 마지막 끝 노드)	예) H, I, J, F, G
Internal (내부 노드)	Leaf node 가 아닌 노드
Edge/Branch/Link (관계,가지,분기)	노드를 연결하는 선 , 뿌리(root)와 잎(leaf)사이의 모든 노드	예) A, B, C, D, E
Degree (노드의 차수)	하위 트리개수 / 각 노드가 지닌 가지의 수 (연결된자식 노드의 수)	예) A의 Degree = 2
Order (계수/차수)	자식 노드들 중 최대 개수
Depth (노드의 깊이)	루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수	예) D 의 경로 깊이 2
Level (노드의 레벨)	특정 깊이를 가지는 노드의 집합 (같은 깊이)	예) A의 레벨 : 레벨0
Height (높이)	루트 노드에서 가장 깊숙히 있는 노드의 깊이	예) 가장 긴 깊이 : 4
Size (크기)	특정 노드가 자신을 포함한 자손의 수	예) 노드 B의 크기 : 6
Parent node (부모)	선조( ancestor ) : 부모 노드와 그의 부모들	예) D, E의 부모노드는 B
Child node (자식)	자손( descendant ) : 자식 노드와 그 자식들	예) B의 자식노드는 D, E
Sibling node (형제)	같은 부모를 가지는 노드	예) D, E는 같은 부모를 갖는 형제노드
Subtree (서브트리)	A를 기준으로 B를 루트로 하면 왼쪽 서브트리, C를 루트로 하면 오른쪽 서브트리라고 한다.