트리와 그래프의 차이

이번 시간에는 트리와 그래프의 차이를 살펴보겠습니다. 트리와 그래프 모두 각 노드가 불규칙적으로 연결되어 있는 구조이지만 차이가 있습니다.

 

 

 

트리 (Tree) - "엄격한 상하 관계"

- 간선에 방향이 정해져 있고 부모-자식 관계가 존재합니다. 따라서 해당 노드보다 상위에 있다면 '부모 노드(parent node)' 라고 하고 하위에 있다면 '자식 노드(child node)' 라고 합니다. 위에 b를 기준으로 a는 부모 노드 이고 d는 자식 노드 입니다.

- 만약 직속 상위 노드가 같고 레벨이 같다면 '형제 노드(sibling node)' 라고 합니다. 위에 e를 기준으로 f는 직속 상위 노드(c)가 동일하고 레벨이 같으므로 형제 노드 입니다.

- 트리에서 가장 위에 있는 노드 하나를 '루트 노드(뿌리 노드, root node)' 라고 합니다. 위의 트리에서는 a가 루트 노드 입니다.

- 가장 밑에 있는 노드(자식이 없는 노드)를 '잎 노드(leaf node)' 라고 합니다. 잎 노드를 제외한 노드를 전부 '내부 노드(internal node)' 라고 합니다. 위의 트리에서는 d, e, f가 잎 노드 입니다. 이 외 a, b, c는 모두 내부 노드 입니다.

- 노드끼리 원형을 이룰 수 없습니다.

- 높이는 레벨의 최대값과 같습니다. 따라서 '높이 = max(레벨s)' 가 성립합니다.

 

 

 

그래프 (Graph) - "평등 관계"

- 간선에 방향이 정해져 있지 않고 부모-자식 관계도 존재하지 않습니다.

- 노드끼리 원형을 이룰 수 있습니다. 위에 (a)-(c)-(f), (a)-(c)-(d)-(b) 등은 원형으로 연결되어 있습니다.