노드와 에지로 연결된 그래프의 특수한 형태
순환 구조x, 1개의 루트 노드가 존재한다.
루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
트리의 부분 트리 역시 트리의 모든 특징을 따른다.
트리의 구성 요소
구성 요소
설명
노드
데이터의 index와 value를 표현하는 요소
에지
노드와 노드의 연결 관계를 나타내는 선
루트 노드
트리에서 가장 상위에 존재하는 노드
부모 노드
두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드
두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드
트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
서브 트리
전체 트리에 속한 작은 트리