[자료구조]비선형구조의 종류와 설명

비선형구조란?

선형구조는 자료를 저장하고 꺼내는 것이 중점이라면 비선형구조는 자료의 표현에 중점을 맞추고 있습니다.

하나의 자료 뒤에 여러개의 자료가 존재하는 형태

자료들 간의 앞뒤 관계가 '1:다' 또는 '다:다'의 관계

 

 

비선형구조의 종류

1. 트리

1개 이상의 노드로 구성된 집합으로 나무 모양과 비슷하여 트리라고 합니다.

우리가 쓰고 있는 폴더구조가 트리라고 생각해주시면 됩니다.

일반 트리와 이진트리의 차이는 이진트리는 2개이상의 노드가 존재하지 않는 구조라고 생각해주시면 됩니다.

 

특징

   · 방향성이 있음

   · 각 노드는 어떤 자료형으로도 표현이 가능

   · 사이클이 존재할 수 없다(하나의 연결 그래프)

   · 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있음

 

1.1 이진트리

각 노드가 최대 두개의 자식을 갖는 트리

 

2. 그래프

노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료구조

추상적인 개념의 연결 관계를 표현하기 위해서 많이 사용합니다.

도시를 연결하는 도로망이나 웹 사이트간에 링크 관계...에 사용하고 있습니다.

 

특징

   · 네트워크 모델

   · 2개 이상의 경로가 가능

   · 부모 - 자식 관계라는 개념이 없음

   · 그래프는 크게 방향 그래프와 무방향 그래프가 있음

 

2.1 무방향 그래프 VS 방향 그래프
무방향 그래프(Undirected Graph)
 · 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
 · 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
 · (A, B)는 (B, A) 동일 Ex) 양방향 통행 도로

방향 그래프(Directed Graph)
 · 간선에 방향성이 존재하는 그래프
 · A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
 · <A, B>는 <B, A>는 다름 Ex) 일방 통행

 

 

3. 힙(Heap)

최대값, 최솟값을 찾아내는 연산을 쉽게하기 위해 고안된 자료형이다.

각 노드의 키값이 그 자식의 키값보다 작지 않거나, 그 자식의 키값보다 크지 않은 완전이진트리이다.

 

특징

   · 힙을 저장하는 표준적인 자료구조는 배열

   · 힙의 삭제는 우선 순위가 가장 높은 루트 노드가 삭제되어야 한다.

 

 

출처

[자료구조] 그래프(Graph)란 - Heee's Development Blog