자료구조 (비선형 자료구조)

지난 글에서 알아본 선형 자료구조에 이어서, 한 원소 뒤에 여러 개의 원소가 존재할 수 있는 비선형 자료구조에 대해 알아보도록 하겠습니다. 비선형 자료구조는 인접한 전, 후 원소 간 다대다 관계가 성립하여, 선형 자료구조에 비해 데이터들의 관계를 표현하기에 적합합니다.

자료구조 (선형 자료구조)

 

트리(Tree)

 트리는 데이터를 노드로 표현하고 연결된 관계를 에지로 표현한 비선형 계층적 자료구조입니다. 계층적 자료구조라는 표현에 적합하게, 컴퓨터의 디렉토리 구조에서 이용되고, 최상위에 위치한 노드를 루트 노드(Root Node)라 하며 나머지 노드를 서브 트리(Sub Tree)라고 합니다.

Tree 구조

 트리에서 Node는 트리 구조의 교점으로, 데이터와 자식 노드를 가진 것을 의미합니다. 또한 Edge는 트리를 구성하기 위한 노드와 노드를 연결하는 선이고, level은 트리의 특정 깊이를 가지는 노드의 집합으로 나타낼 수 있습니다. 다음으로 degree(차수)는 각 노드가 지닌 가지의 수를 말하며, Leaf Node(Terminal Node)는 하위에 다른 노드가 연결되지 않은 노드를 의미합니다.

 트리 구조는 데이터의 저장보다 저장된 데이터를 효과적으로 탐색하기 위해 사용되며, 리스트와 다르게 데이터가 단순 나열되는 것이 아닌 부모(parent), 자식(child)의 계층적인 관계로 표현되고, 이 때 Root Node를 제외한 모든 노드는 단 하나의 부모 노드를 가지게 됩니다.

 

그래프(Graph)

 그래프(Graph)는 노드와 에지로 이루어진 자료구조로, 트리와 다르게 부모/자식 노드의 개념이 존재하지 않습니다. 그래프는 방향 간선(에지)만을 사용하는 유향 그래프(Directed graph)와 무방향 간선(에지)만 사용하는 무향 그래프(Undirected graph)로 분류됩니다. 유향 그래프의 경우 에지를 통해 한쪽 방향으로만 이동이 가능하고, 무향 그래프는 에지를 통해 양방향으로 이동이 가능합니다.

 이러한 특징을 가진 그래프는 모델이나 객체에 대한 관계를 유연한 방식으로 표현하기 위해 사용됩니다.

그래프

 

 

사진 출처(Tree 구조) : https://velog.io/@taeha7b/datastructure-tree

사진 출처(그래프) : https://blog.naver.com/kbs4674/220727852469