트리(Tree)

가지에 의해 연결된 노드로 구성된 추상적인 계층구조.

① 각 가지는 한 노드에서 종속된 다른 노드를 연결하고

② 어떤 노드에도 종속되지 않는 유일한 노드인 루트가 있고

③ 루트를 제외한 모든 노드는 정확히 하나의 노드에 직접 종속된다.

 

트리는 유한한 수의 노드(node)되며, 트리의 시작되는 노드를 루트(root)라 하며 노드와 노드 사이의 연결선을 브랜치(branch)라고 합니다.

 

◈ 트리에서 사용되는 용어

• 근노드(Root Node) : 트리의 뿌리가 되는 노드. 항상 존재한다.

• 단노드(Terminal Node) : 노드의 차수(Degree)가 0인 노드 또는 자식이 없는 노드.

• 간노드(Nonteminal Node) : 노드의 차수(Degree)가 0이 아닌 노드 또는 자식을 갖고 있는 노드.

• 차수(Degree) : 각 노드의 가지(edge) 수 또는 각 노드가 갖고 있는 자식 노드의 수.

• 트리의 차수(Tree Degree) : 트리 전체에서 노드의 차수가 가장 큰 것을 트리의 차수라 한다.

• 레벨(Level) : 근노를 1레벨로 하여 차례로 최종 단노드까지 계층을 표시한다.

• 높이(Height) : 트리의 총 높이.

• 자노드(Child Node) : 각 노드에 연결되어 있는 다음 레벨의 노드.

• 부노드(Parent Noce) : 각 노드의 바로 상위 레벨에 있는 노드.

• 제노드(Sibling Node, Brother Node) : 같은 부노드에 연결되어 있는 노드.

• 조상(Ancestors) : 각 노드의 상위 레벨에 해당하는 모든 노드.

• 자손(Descendants) : 각 노드의 하위 레벨에 있는 모든 노드.

• 숲(Forest) : 트리가 모여서 이루어진 집합.

• 서브 트리(Sub Tree) : 임의의 노드를 제거했을 때 생길 수 있는 트리의 집합.

 

▶ 근노드 : A ▶ 단노드 : C, E, G, H, I ▶ 간노드 : B, D, F ▶ 차 수 :      A의 차수 - 3      B의 차수 - 2      D의 차수 - 1      F의 차수 - 2      C, E, G, H, I의 차수 - 0 ▶ 트리의 차수 : 3(A의 차수가 제일 크기 때문에) ▶ 레 벨 :      A - 1레벨      B,C,D - 2레벨      E, F, G - 3레벨      H, I - 4레벨 ▶ 높 이 : 4 ▶ 자노드 : A의 자노드 - B, C, D ▶ 부노드 : G의 부노드 - D ▶ 제노드 : H, I (부노드 F에 연결되어 있어서) ▶ 조 상 : G의 조상은 D, A이다. ▶ 자 손 : B의 자손은 E, F, H, I 이다. ▶ 서브트리 : A를 제거하면 B, E, F, H, I는 서브트리이다.

 

 

 

출처]

한국정보통신기술협회 : 단체표준 TTAS.KO-11.0019 소프트웨어 프로세스와 품질 - 용어

한국정보통신기술협회 : 트리

 

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 겨울