트리

트리란?

- 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조

- 비순환 구조

 

트리 관련 용어

• 루트 : 트리의 시작부분 즉, 가장 윗 부분을 나타낸다. 하나의 트리에는 하나의 루트가 있다.
• 리프 : 트리의 가장 아랫부분에 위치하는 노드를 리프라고 한다. 이 때, 맨 아래에 있는 노드가 아닌
  자식 노드가 없는 노드를 나타낸다. (terminal node, external node)
• 안쪽 노드 : 루트 및 리프 노드를 제외한 노드를 안쪽 노드라고 한다. (non-terminal node)
• 자식 : 노드 바로 아래에 연결된 노드를 자식 노드라고 한다. 노드는 자식을 여러 개 가질 수 있다.
• 부모 : 노드에서 바로 위쪽에 연결된 노드를 부모 노드라고 한다.
• 형제 : 같은 부모를 가지는 노드를 형제(sibling)라고 한다.
• 조상 : 어떤 노드에서 가지로 연결된 위쪽 노드 모두를 조상(ancestor)라고 한다.
• 자손 : 어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손(descendant)라고 한다.
• 레벨 : 루트로부터 얼마나 떨어져 있는지에 대한 값. 루트의 레벨은 0이다.
• 차수 : 노드가 갖는 자식의 수
• 높이 : 루트로 부터 가장 멀리 떨어진 리프노드까지의 거리(리프노드 레벨의 최댓값)
• 서브 트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
• 널 트리 : 노드, 가지가 없는 트리