자료구조 - 비선형구조 : 트리, 그래프

1. 트리(Tree)

우리는 트리를 기억할 때 영어 그대로  나무를 생각해보자.

그 중에서도 나뭇가지를 생각하면 더 쉬울것 같다.

이것은 놀랍게도 나무다.

나뭇가지를 사람이 잘랐다. 자른 나뭇가지는 대충 이렇게 생겼다. 나뭇가지를 자료구조로 바꾸면 맨 오른쪽이 된다.

위에서 처럼 나뭇가지와 같이 생긴게 트리 구조다.

 

트리는 위에서부터 아래로 계층형 구조로 생겼다.

트리의 종류

• 이진트리 :  데이터를 검색하거나, 자료를 정렬하는 알고리즘에서 사용된다.
• 최소 비용 신장 트리 : 데이터 간의 관계를 유지하면서 최소의 비용이 드는 관계를 유지하는 방법.

 

트리는 위에서 말한대로 계층형 구조를 가지게 되는데,  A가 1 레벨, B, C, D 가 2레벨, E부터 J까지가 3레벨이라고 한다.

물론 아래 계층이 더 생기면 4, 5, ... 순으로 늘어간다.

 

 

트리에서 사용하는 용어

다시 저 자료구조로 바꾼 것을 살펴보면서 보자

용어	설명	위치 및 값
노드 - Node	A, B등을 감싸는 원	A, B, C 등 각 항목들
간선 - Edge, 링크 - Link	노드와 연결되는 선	A와 B 사이의 선 등
루트(Root) 노드	뿌리가 되는 노드	A
단말(Terminal)노드	자식이 없는 노드	E, F, G, H, I, J
간노드(Nonterminal)	자식이 있는 노드	A, B, C, D
노드의 차수(Degree)	자식 노드의 개수	B는 3
트리의 차수(Degree)	노드의 차수가 가장 큰 값	루트 노드인 A의 차수 = 3
노드 레벨(Level)	특정 깊이를 가지는 노트 집합	A = 1,     B,C,D = 2,     E~J = 3
노드의 크기(Size)	자신을 포함한 자식 노드의 수	A의 노드크기 = 10(하위 모든 노드의 수) B의 노드 크기 = 4(B,E,F,G)
노드의 깊이(Depth)	루트에서 거쳐 간 간선의 수	H = 2 ( A → C,  C → H)
노드의 높이(Height)	루트에서 가장 깊은 노드	3
부(Parent)노드	부모 노드	G는 B, H는 C
자(Children)노드	자식 노드	B는 E,F,G  C는 H
(형)제(Sibling)노드	형제노드 (부모가 같은 자식 노드들)	F는 E,G
숲(Forest)	루트를 제외한 나머지 부분	A 제외하고 다

 

2. 그래프

구조

데이터와 데이터 사이의 관계를 표현하는 비선형 구조이다.

데이터 검색, 데이터의 복잡도, 전자회로 분석 등 다양한 응용분야에 적용된다.

 

좌 : 무방향성 그래프 ,  우 : 방향성 그래프

무방향성 그래프 : 간선을 표현하는 두 정점의 쌍에 순서가 없는 그래프. 

방향 그래프 : 모든 간선을 순서가 있는 두 정점을 쌍으로 표현하는 즉, 간선의 방향을 가진 그래프.

 

그래프는 관계를 나타내는 노드(Node)와 간선(Edge)으로 구성된 모음이다.

일반적으로 G = (V, E)    [G = 그래프, V = 정점, E = 간선] 로 표현한다.

• 노드는 트리에서와 마찬가지로 정점(원)이다. 
  • A, B, C, D, E
• 간선은 정점(원)을 잇는 연결이다.

 

간선은 E로 표기한다.

• 무방향성 그래프에서는 간선을 {{A,B},{B,C}, {C,E}} 등으로 표현한다.
• 방향성 그래프에서는 간선을 화살표 방향대로 표현한다. {<A, C>, <B,A>,<B,C>, <C,D> ...등}

그래프의 특징

• 그래프는 네트워크 모델이다.
• 트리처럼 루트노드, 부모-자식 관계가 없다.
• 2개 이상의 경로가 가능하다
• 자기 자신을 향하는 간선은 없다.
• 중복된 간선을 허용하지 않는다.