[학교_자료구조] 트리(Tree)와 그래프(Graph)

[학교_자료구조] 트리(Tree)와 그래프(Graph)

반응형

트리(Tree)와 그래프(Graph)는 매우 중요한 개념이다.

Graph 범위 안에 Tree가 속해 있다. 그러므로 트리는 그래프이다.

트리란?

트리 : 사이클이 없는 연결 그래프

(A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.)

참고) acyclic : 사이클이 없다 (이진트리 같이 순환되지 않는 것)

- 트리는 비선형 구조로, 각 데이터가 1:1로 연결되어 있지 않고, 1:다 혹은 다:다의 관계를 맺고 있다.

- 트리의 레벨은 level 0으로 시작하기도 하고, level 1로 시작하기도 하지만, 이 글에서는 level 1로 정하겠다.

level 2에서 가질 수 있는 노드 수는 최대 2개이고, level 6에서 가질 수 있는 최대 노드 수는 32이다.

즉, level 1은 2의 0승이고, level 2는 2의 1승이다.

level 1이 시작이라고 했을 때 2의 n-1승이 공식이다.

트리 용어

- 노드(node, 정점)

- 루트(root) : 부모가 없는 노드

- 서브트리(subtree) : 기존 트리에서 하위의 트리 구조. 어떤 노드를 기준점으로 잡았을 때, 아래에 위치한 각각의 트리 구조를 서브트리라고 함. (트리 속의 작은 트리!)

- 간선(edge) : 노드 간의 연결선 (모든 노드의 개수 - 1)

- 차수(degree) : 서브 트리의 개수

- 단말 노드/잎 노드(leaf node) : 차수가 0인 노드 (자식이 없는 노드)

- 비단말 노드(non terminal) : 단말 노드 이외의 노드

- 자식 노드(child node) : 바로 아래에 있는 노드들 (아래 노드 전체를 포함하지 않음. level + 1에 있는 노드들만)

- 부모 노드(parent node) : 바로 위에 있는 노드 (위 노드 전체를 포함하지 않음. level - 1에 있는 노드만)

- 형제 노드(sibling node) : 부모가 같은 자식 노드들

- 조상 노드(ancestor node) : 루트부터 노드에 이르는 경로상의 모든 노드들 (위 노드 전체를 포함)

- 자손 노드(descendent node) : 서브 트리 상의 모든 노드들 (아래 노드 전체를 포함)

- 트리의 차수(degree) : 트리에 속한 노드의 최대 차수

- 수준(level) : 트리의 각 층에 매겨지는 번호, 루트의 레벨은 1, 한 층씩 내려갈수록 1씩 증가

- 높이(height)/깊이(depth) : 트리에 속한 노드의 최대 수준(level)

위에서 유의해야 할 것이, 자식 노드와 부모 노드는 각각 한 층 아래 또는 한 층 위의 노드만 말하는 것이다.

그에 반하여 조상 노드와 자손 노드는 한 층이 아닌 위 노드 전체 혹은 아래 노드 전체를 뜻한다.

참고) 이진트리는 최대 차수가 2개인 트리이다.

반응형

from http://white-world.tistory.com/186 by ccl(A) rewrite - 2021-11-03 11:26:50