트리(Tree)

 

🟩 자연의 나무처럼 가지가 분기하여 뻗어 나가는 구조

 

트리를 구성하는 원을 '노드(마디)'

트리 맨 위에 있는 노드는 '루트(뿌리)'

위에 있는지 아래에 있는지에 따라 부모 노드와 자식 노드로 구분, 같은 부모를 가지면 형제 노드

부모와 자식 노드 형태로 묶인 트리의 일부분을 서브 트리

트리의 맨 아래에 있고, 별도의 자식 노드가 없으면 리프(잎) 노드

 

노드의 레벨 : 루트로부터 그 노드까지 이어진 선(경로)의 길

노드의 길이 : 어떤 노드에서 다른 노드로 이동할 때, 거치는 노드의 개수

노드의 경로 : 어떤 노드에서 다른 노드로 이동할 때, 거치는 노드의 순서

노드의 크기 : 자기 자신과 자식 노드를 포함한 노드의 개수

노드의 차수 : 노드별 자식 노드의 개수

트리의 높이 : 트리 노드로부터 리프 노드까지 도달하는 경우 중 가장 긴 '경로'의 '길이' (엣지의 갯수)

트리의 차수 : 노드의 차수 중 가장 높은 숫자의 차수

 

트리의 요소는 '끝'에 추가된다.

 

루트노드 : 진입 차수 = 0

루트를 제외한 모든 노드의 진입 차수 : 1

리프노드 : 진출 차수 = 0