Tree

정의

그래프의 한 종류 / “최소 연결 트리”라고도 함

개념

• 트리는 하나의 루트 노드를 갖는다.

• 루트 노드는 0개 이상의 자식 노드를 갖고 있다.

• 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
• 트리에는 사이클(cycle)이 존재할 수 없다.
• 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
• 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
• 각 노드는 어떤 자료형으로도 표현 가능하다.

특징

• 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)

• DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.

• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.

• 내부(internal) 노드: 단말 노드가 아닌 노드

• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)

• 형제(sibling): 같은 부모를 가지는 노드

• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수

• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합

• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수

• 트리의 차수(degree of tree): 트리의 최대 차수

• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

예시

• 신장 트리 : Spanning Tree

출처