트리(Tree) 간단개념정리

트리의 정의!!

대상 정보를 계층적으로 구조화시키고자 할 때 사용하는 자료구조가 "트리" 이다.

이 그림의 혈통도는 "가계"라는 대상 정보를 단순히 데이터 요소를 나열하여 표현하지 않고, 데이터 요소들간의 "parent-child" 관계를 계층적으로 표현하고 있다. 혈통도는 "I"를 뿌리로 하여 가지가 갈라져 나온 거꾸로 된 나무 모양을 하고 있기 때문에 "트리(tree)" 구조를 가졌다고 한다. 트리에서 단위 데이터 요소들은 하나의 노드로 표현된다.

트리는 다음과 같이 재귀적으로 정의할 수 있다.

• 트리에는 하나의 루트(root) 노드가 있다.
• 루트 를 제외한 나머지 노드들은 서로 중복되지 않는 여러 개의 노드 집합으로 나뉘어진다. 이 때 각각의 노드 집합들은 역시 트리가 된다.

혈통도를 예로 들어 설명하면 "I" 노드는 전체 트리의 루트 노드가 되고, 루트 를 제외한 나머지 노드들은 {father, grand father, grand mother} 집합과 {mother, grand father, grand mother} 의 두 집합으로 나뉘어진다. 이 때 두 개의 집합은 각각 "father" 노드와 "mother" 노드를 루트로 하는 트리가 된다.

트리의 조건!!!

• • 최상위 노드를 근노드(root node)라고 하며, 반드시 1개의 근노드가 있어야 한다.
  • 근노드를 제외한 나머지 노드들은 n개(n≥0)의 부분 집합(subset)인  T₁, T₂, … T_n으로 분리된다. T_i(1≤i≤n)는 각각 하나의 트리가 되며, 이 때 T_i를 근노드의  서브트리(subtree)라고 한다.

  

  순환이 있으므로 트리가 아니다

  
  
  
  
  
  

트리 용어 설명!!

근노드

트리구조에서 레벨(level)이 가장 높은 한 개의 노드로서, 근노드의 부노드(parent node)는 존재하지 않으며, 자노드(parent node)만 가지고 있는 노드이다. Example Tree에서 근노드는 A이다.


서브트리

트리에서 근노드를 제거했을 때 생기는 트리이다. 서브트리와 비슷한 말로는 포리스트(Forest)가 있다. Example Tree에서 A를 제거하면 B를 중심으로 한 트리와 C를 중심으로 한 트리로 구분된다.


간노드

차수(degree)가 0이 아닌 노드를 말하며 단말노드의 반대개념이다. Example Tree에서는 A,B,E가 간노드이다.




경로

어떤 임의의 노드로부터 다른 임의의 노드에 이르기까지 연결된 노드의 집합으로 이동 경로를 말한다. 경로의 길이는 경로(path)를 구성하는 노드의 수보다 하나 적은 수이며, 경로를 구성하는 연결선의 수이기도 하다. Example Tree에서 A노드에서 G노드까지의 경로는 A - B - E - G이며 경로 길이는 3이다.


트리의 차수

트리를 구성하는 모든 노드들이 가지는 차수중에서 가장 큰 차수를 "그트리의 차수"라 한다. Example Tree에서 노드 A의 차수가 가장 큰 차수로써 3이므로 이 트리의 차수는 3이다.