트리
- 데이터 사이의 계층 관계를 나타내는 자료구조
- 구성 요소 : 노드와 가지
- 루트 : 트리의 가장 윗부분에 위치. 하나의 트리에는 하나의 루트가 있음
- 리프 : 더 이상 뻗어나갈 수 없는 마지막에 위치한 노드. 끝 노드, 바깥 노드라고도 함
- 안쪽 노드 : 루트를 포함하여 리프를 제외한 모든 노드
- 자식 : 어떤 노드로부터 가지로 연결된 아래쪽 노드. 여러 개를 가질 수 있음
- 부모 : 어떤 노드에서 가지로 연결된 위쪽 노드. 노드는 1개의 부모를 가짐
- 형제 : 같은 부모를 가지는 노드
- 조상 : 어떤 노드에서 가지로 연결된 모든 위쪽 노드
- 자손 : 어떤 노드에서 가지로 연결된 모든 아래쪽 노드
- 레벨 : 루트로부터 얼마나 떨어져 있는지에 대한 값. 루트의 레벨은 0이고 루트로부터 가지가 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어남
- 차수 : 노드가 갖는 자식의 수. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 함
- 높이 : 루트로부터 가장 멀리 떨어진 리프까지의 거리. 리프 레벨의 최댓값
- 서브 트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
- 널 트리 : 노드와 가지가 없는 트리
- 순서 트리 : 형제 노드의 순서를 따지는 트리
- 무순서 트리 : 형제 노드의 순서를 따지지 않는 트리