트리

트리는 비선형적(nonlinear) 자료구조 중에서 계층적(hierarchical) 자료구조로 부모-자식 관계의 노드들로 구성된다.

• 상위 노드는 부모(parent)노드로 불리고 하위 노드는 자식(child)노드로 불린다.

트리의 응용 분야

트리는 여러 분야에서 응용될 수 있는 자료구조이다.
대표적으로 트리는 계층적인 조직 표현에 쓰이며 회사 조직도와 같은 곳에서 사용된다.
또한 트리는 컴퓨터에서 디렉터리 구조로서 사용된다. 그리고 인공지능에서 결정 트리(decision tree)로서 응용된다.

• 인공지능에서 결정 트리의 예시로 사람이 야외로 골프 치러 갈 것인지를 결정하기 위한 트리로 사용된다.

트리 용어

• 트리에서 노드(node)는 트리를 구성하는 요소이다.
• 루트(root)는 부모가 없는 최상위 노드를 말한다.
• 서브 트리(subtree)는 전체 트리 중 일부 트리를 의미한다.
• 단말 노드(terminal node)는 자식이 없는 노드로서 리프(leaf) 노드라고도 불린다.
• 단말 노드를 제외한 자식이 있는 노드를 비단말 노드(nonterminal node)라고 한다.

• 자식들의 부모를 부모 노드라고 하고 부모의 자식들을 자식 노드라고 한다.
• 같은 부모에서 나온 자식 노드들을 서로 형제(sibling) 노드라고 한다.
• 자식의 자식 노드 입장에서 루트 노드는 조상(ancestor) 노드로 불린다.
• 반대로 루트 노드 입장에서 자식의 자식 노드는 후손(descendent) 노드로 불린다.
• 트리의 레벨(level)은 트리의 각 층 번호를 의미한다.
• 트리의 높이(height)는 트리의 최대 레벨을 의미한다.
• 트리의 차수(degree)는 노드가 가지고 있는 자식 노드의 개수를 의미한다.
  

트리 용어 활용

• A는 루트 노드이다.
• B는 D와 E의 부모 노드이다.
• C는 B의 형제 노드이다.
• D와 E는 B의 자식 노드이다.
• B의 차수는 2이다.
• 트리의 높이는 4이다.

트리의 종류

• 일반 트리
  • 각 노드의 자식 수에 제한이 없는 트리
    
• 이진 트리
  • 각 노드의 자식이 최대 2개인 트리
  • 각 노드는 데이터 필드와 왼쪽/오른쪽 서브 트리의 위치를 저장하는 2개의 링크 필드로 구성 가능하다.