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

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

 

선형구조가 주로 자료에서 input-output하는 것에 초첨이 맞춰져있다면 

비선형 자료구조 자료 뒤에 여러 자료가 존재하는 형태를 보인다. 

비선형 자료구조 : 트리

트리의 개념 

노드들이 나뭇가지처럼 연결된 계층적인 자료구조를 가리키며 주로 조직 구조도, 연산 수식을 표현하는데 적합하다.

• 노드 : 자료 항목을 가지는 트리를 구성하는 기본 요소 
• 루트 노드 : 트리의 가장 맨 상단에 있는 노드
• 차수(Degree) : 각 노드에서 뻗어나온 가지 수 
• 리프 노드 : 자식이 하나도 없는, 차수가 0인 노드. 보통 마지막 노드가 이에 해당한다. 
• 트리 뎁스 : 트리의 최대 깊이 
• 트리 데그리 : 노드 차수 중 최대 차수 

이진 트리 (Binary Tree)

자식이 둘 이하인 노드로만 구성된 트리 (= 차수가 2 이하)

Full Binary Tree와 Complete Binary Tree로 구분할 수 있다. 

 

• 깊이 i인 노드의 최대 노드 수 = 2^i -1 ex) 위의 전 이진 트리의 최대 노드 수는 7임.   

이진 트리의 순회

트리를 구성하는 노드들을 모두 방문하는 방법

• 전위 순회 (Pre-order) : Root -> Left -> Right
• 중위 순회 (In-order) : Left -> Root -> Right
• 후위 순회 (Post-order) : Left ->Right -> Root

이진 수식 트리

산술식을 계산하기 위해 이진트리에 기억시키는 방법

• 전위 순회 (Pre-Fix) : Root -> Left -> Right
• 중위 순회 (In-Fix) : Left -> Root -> Right
• 후위 순회 (Post-Fix) : Left ->Right -> Root

단, 컴퓨터에서는 중위 표기법 사용 시 어떤 수식을 먼저 연산해야 할 지 확인해야하며

스택으로 연산이 가능한 Post-Fix나 Pre-Fix 방식을 활용해야한다.

 

ex) In-Fix 표기를 Pre-Fix로 변환 

 

A/B * (C + D) + E

 

1) 연산 우선 순위에 따라 괄호로 묶기 : (((A/B) * (C + D)) + E)

2) 연산자를 괄호 앞으로 이동 : + ( *(/(A B) + (C D) ) E)

3) 괄호 제거  : +*/AB+CDE

 

ex) In-Fix 표기를 Post-Fix로 변환 

1) 연산 우선 순위에 따라 괄호로 묶기 : (((A/B) * (C + D)) + E)

2) 연산자를 괄호의 뒤로 : (((A B) / (C D) + ) * E) +

3) 괄호 제거  : AB+CD+*E+

비선형 자료구조 : 그래프 

그래프의 개념 

Vertex 혹은 Node와 이들을 연결하는 간선(Edge)의 집합으로 이루어진 자료구조로,

통신망, 교통 시스템, SNS 분석 등에 활용된다. 

 

무방향 그래프, 방향 그래프 두 개가 있으며 간선을 통해 양방향 이동이 가능하느냐 아니냐의 차이가 존재한다.

단순히 생각해보자면 SNS의 팔로워-팔로잉도 이에 해당한다는걸 알 수 있다.

 

무방향-방향 그래프 안에서도 비용이나 사용료를 의미하는 가중치가 부여되는 그래프들도 존재한다.

 

 

그래프의 구현 방법

• 인접 리스트 (Adjacency List) : 인접한 정점을 인접 리스트에 저장하는 방법 
• 인접 행렬 (Adjacecy Matrix) : 2차원 배열을 이용하여 노드 간 연결 관계를 나타내는 방법

인접한 정점이 없는 5와 8은 저장이 안 된 것을 확인할 수 있다.

 

구현은 쉽지만 비교적 비용이 많이 든다

그래프 알고리즘 종류 

 

• 그래프 탐색 알고리즘 : 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

        특정 정점(노드)를 찾는 알고리즘

 

• 최단 경로 알고리즘  : 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드 와샬(Floyd Warshall)

        두 정점 간의 최소 가중치 합을 찾는 알고리즘 

 

• 최소 신장 트리 알고리즘  : 크루스칼(Kruskal), 프림(Prim)

        모든 정점을 최소하느이 간선으로 연결하는 그래프를 찾는 알고리즘 

 

그래프와 트리의 관계

 

 

 

 

참고자료

https://youtu.be/v9vUioce2IM?si=xdioVM5xA4I26wb_