트리(Tree)

트리의 정의

• 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태
• 가족의 계보(족보), 연산 수식, 회사 조직 구조도, 히프(Heap) 등을 표현하기에 적합

---

트리 관련 용어

• 노드 : 트리의 기본 요소로 자료 항목과 다른 항목에 대한 가지를 합친 것
• 근 노드 : 트리의 맨 위에 있는 노드
• 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지 수
• 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 도그, 즉 Degree가 0인것
• 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드
• 조상 노드(Ancestors Node) : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드
• 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
• 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들
• 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들
• Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
• 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대의 레벨
• 숲(Forest) : 여러 개 의 트리가 모여 있는 것
• 트리의 드그리 : 노드들의 디그리 중에서 가장 많은 수