[ 알고리즘 ] 그래프, 트리

	그래프	트리
방향성	방향, 무방향	방향
사이클	순환, 비순환, 자기순환(self-loop)	비순환
루트노트	루트 없음	한개의 루트 노드
부모- 자식	부모-자식 개념 없음	1:N 의 부모-자식 관계
모델	네트워크 모델	계층 모델
간선 수	자유	N-1개

그래프

 

그래프란 노드 ( Node ) 와 간선 ( Edge ) 를 하나로 모아둔 자료 구조로, 연결되어 있는 객체들간의 관계를 나타내는 자료 구조이다.

그래프는 다음과 같은 특징을 갖는다.

• 그래프는 노드 ( 정점 Vertex 라고도 함), 간선 ( Edge ) 로 이루어져 있으며 간선이 화살표인 경우에는 방향성을 띄게 된다
• 이를 유향 그래프라고 하고, 화살표가 없는 경우는 무향 그래프라고 한다.
• 간선에 특정한 수치를 가질 수 있는데 이를 가중치 ( Weighted value )라고 한다.
• 도시가 노드, 간선이 도로라고 하면 간략화 한 지도가 되고, 간선에 가중치가 있으면 도로의 이용료가 된다.
• 지하철 노선도, 도로망, 컴퓨터 네트워크 등을 표현할 때 사용된다.

트리

트리는 Root 노드의 존재와 부모-자식 관계 를 가지고 있는 그래프의 한 종류이다.

트리는 다음과 같은 특징을 갖는다.

• 트리는 오직 하나의 루트 노드를 갖는다
• 루트 노드는 0개 이상의 자식 노드를 갖는다
• 자식 노드는 오직 하나의 부모 노드만을 갖는다 ( 1:N )
• 노드는 자식과 부모를 연결하는 간선으로 연결되어 있다.
• 트리에는 사이클, 자기 순환이 없다.
• N개의 노드를 갖는 트리는 항상 N-1 개의 간선을 갖는다.

이진 트리 ,완전 이진 트리, 전 이진 트리, 포화 이진 트리

이진 트리 ( Binary Tree )

• 이진 트리는 각 노드가 최대 2개의 자식을 갖는 트리를 의미한다.
• 모든 노드는 자식이 없거나 한개, 두개만의 자식을 갖는다.
• 이진 트리의 탐색 방식에는 전위, 중위, 후위 순회를 통해 탐색한다.

완전 이진 트리 ( Complete Binary Tree )

• 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있는 트리이다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽부터 오른쪽 순서로 채워져야한다.

전 이진 트리 ( Full Binary Tree )

• 전 이진 트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

포화 이진 트리 ( Perfect Binary Tree ) 

• 모든 레벨이 노드로 꽉 차 있는 트리를 의미한다.
• 트리의 노드 개수가 정확히 2^k-1 개 여야한다. k 는 트리의 높이이다.
• 사진은 3층의 높이를 가진 트리니까  2³-1 개, 즉 7개의 노드를 가진 트리이다.