[Data Structure] 자료구조 : #2 비선형구조

[Data Structure] 자료구조의 분류 : #1 선형구조

 

이전 포스팅에서는 선형구조를 알아봤다.

오늘은 비선형 구조인 트리 / 그래프에서 유의해야 할 특징에 대해 하나씩 정리해보려고 한다.

(트리도 그래프의 일종!)

 

---

 

비선형구조

 

선형구조는 데이터가 연속적으로 연결되어있는

1:1의 구조로 하나의 데이터 뒤에는 하나의 데이터가 존재하지만,

 

비선형구조는 데이터가 비연속적으로 연결되어있는

1:n의 구조로 하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있다.

 

 

트리 (Tree)

트리 또한 방향 그래프의 한 종류이다!

 

이름처럼 트리는 나무를 뒤집어 놓은 듯이 데이터를 저장한다.

데이터를 순차적으로 나열하는 선형 구조와 다르게

계층적으로 연관되도록 구조화시킨 형태로 데이터 간의 연관성을 표현한다.

 

트리의 기본 구성 요소로는 노드와 가지로 나누는데

트리는 노드(Node)와 가지(Branch)를 이용하여 '사이클을 이루지 않도록' 구성한 그래프이다.

(쉽게 비선형 구조의 대표적인 예로는 조직도나 디렉토리 구조를 생각하면 된다!)

 

데이터를 담는 기억 공간을 노드, 노드와 노드를 잇는 선을 브랜치 또는 링크 등으로 표현한다.

(여기서 노드는 우리가 보는 동그란 기억공간(자료 항목)뿐만 아니라 + 다른 항목에 대한 가지를 합친 것을 의미한다.)

 

 

트리에도 다양한 유형이 있지만,

오늘은 기본적인 이진 트리 그 중에서도 이진 탐색 트리에 대해 알아보자!

 

이진 트리(Binary Tree)

 

이진 트리는 하나의 부모노드에 자식노드가 최대 2개로 구성된 트리를 이야기한다.

 

+)

트리의 형태에 따라 분류할 수 있는데 대표적으로 아래와 같다.

• 정 이진 트리 (포화 이진 트리, Full Binary Tree)
• 완전 이진 트리  (Complete Binary Tree)
• 균형 이진 트리 (Balanced Binary Tree)
• 편향 이진 트리 (Skewed Binary Tree)

 

이진 탐색 트리 (Binary Search Tree)

 

이진 탐색 트리는 같은 이진 트리이지만 보다 세부적인 정의를 가지고 있다!

 

이진 트리의 경우 노드간의 대소관계를 고려하지않지만,

이진 탐색 트리는 노드간의 대소관계를 고려하기 때문에

왼쪽의 노드들은 부모 노드보다 작아야하고, 오른쪽 노드들은 부모 노드보다 커야한다.

 

그리고 노드가 비어있지 않다면 모두 다른 값을 가져야한다.

마지막으로 서브 트리는 각각 루트 노드를 가진 또 하나의 이진 탐색 트리 구조여야 한다.

 

그래프 (Graph)

그래프는 정점과 간선으로 구성된 자료구조로

정점과 간선을 통해 데이터 간의 연결관계를 표현한다.

(지하철 노선도를 생각하면 쉽다!)

 

구조적, 계층적 연결 관계를 나타내는 트리와 달리

그래프는 루트 노드나 부모-자식의 개념이 존재하지 않기 때문에 '네트워크 모델' 개념이다!

또한 트리 구조는 사이클을 이루지않았지만 그래프는 사이클이 있을 수 있다.

 

그래프는 대표적으로 방향 그래프와 무방향 그래프로 나누는데

방향 그래프는 방향성이 존재하는 것으로 도로로 치면 일방통행, 무방향 그래프는 양방통행의 개념이다.

 

+)

그외에도 그래프는 다양한 유형을 가진다.

 

• 방향 그래프(Directed Graph)
• 무방향 그래프(Undirected Graph)
• 연결 그래프
• 비연결 그래프
• 순환 그래프(Cyclical Graph)
• 비순환 그래프(Aycyclical Graph)
• 완전 그래프(Complete Graph)
• 부분 그래프(Sub Graph)
• 가중치 그래프(Weighted Graph)

 

 

오늘은 간단히 알아보았기 때문에

다음 포스팅에서는 각각 따로 자세히 알아보도록 하자! 🎉

---

Tree Data Structures in JavaScript for Beginners

자료구조 이진 트리(Binary Tree)의 종류

그래프 종류 [정보통신기술용어해설]

 

 

⚠️ 아래 내용은 모두 개인적인 참고 / 기록을 위한 용도입니다. 참고해주시고 편안하게 봐주세요 :)  ⚠️

***    혹시라도 잘못된 정보가 있다면  언제든지 알려주시면 감사하겠습니다  !    ***