비선형 자료구조 ( Non - Linear )

비선형 자료구조 ( Non - Linear Data Structure )

지금까지 데이터가 일렬로 보관되는 선형 자료구조에 대해 배웠다.

데이터의 여러 관계도를 나타낼 수 있는 비선형 자료구조에 대해 다뤄보겠다.

비선형 자료구조를 사용하는 이유 중 하나는 데이터 간의 관계도 혹은 계층을 표현하기 위함이 크다.

비선형 자료구조는 그 종류가 정말 많은데, 사용하는 목적 경우에 따라 아주 다양한 자료구조로 활용할 수 있다.

비선형 자료구조에는 대표적으로 두 가지의 기본 형태인 그래프와 트리가 있다.

그래프 ( Graph ) 는 다소 불규칙적인 연결 관계를 보여준다.

트리 ( Tree ) 는 깔끔하게 정렬되어 있는 모습을 보여준다.

 

비선형 자료구조란?

데이터가 계층적 ( Hierarchical ) 또는 망 ( Network ) 형태로 연결되어 있는 구조

원소들이 단일 직선 ( 선형 ) 으로 나열되지 않고, 하나의 원소가 여러 개와 연결될 수 있다.

탐색 , 삽입 , 삭제가 더 복잡할 수 있지만 복잡한 관계를 표현하기 유리하다.

 

 

▼그래프 ( Graph )

그래프 ( Graph ) 는 정점 ( Vertex , Node ) 과 간선 ( Edge ) 으로 이루어진 자료구조이다.

객체 간의 관계를 표현하는데 사용한다.

정점은 개체를 나타내고 , 간선은 두 정점 간의 연결 관계를 의미한다.

 

▼정점 ( Vertex , Node )

정의 : 그래프에서 표현하는 대상 ( 객체 , 데이터 , 위치 등 )

예시 : 

• 소셜 네트워크 - 사람 한명
• 지도 - 도시 , 역
• 웹 - 웹 페이지

표현 방식 : 일반적으로 원 ( circle ) 으로 표시하고, 고유한 번호 ( ID ) 나 이름 ( Label ) 을 붙인다.

쉽게 말하면, "점" 자체를 나타낸다.

 

▼간선 ( Edge )

정의 : 두 정점을 연결하는 선 ( 관계나 경로 )

종류 :

• 무방향 간선 ( Undirected Edge ) : 양방향 관계 ( A 와 B 가 서로 연결됨 )
• 방향 간선 ( Directed Edge ) : 한쪽 방향만 가능 ( A 에서 B 로 가는 관계 )
• 가중치 간선 ( Weighted Edge ) : 비용이나 거리 같은 값이 붙은 간선 ( 지하철 거리 , 도로 시간 )

쉽게 말하면, "점과 점을 이어주는 선" 이다.

 

 

▼트리 ( Tree )

트리는 계층적 구조로 표현하는 자료구조이다.

노드 ( Node ) 와 간선 ( Edge ) 으로 이우러지며 부모 - 자식 관계를 가진다

 

▼노드 ( Node )

정의 : 트리의 구성 요소 ( 데이터를 담는 단위 )

하나의 노드는 데이터와 자식 노드( 들 )에 대한 참조를 가진다.

트리에서의 역할 구분

 

1. 루트 노드 ( Root Node )

• 최상위에 있는 노드 ( 부모가 없다 )
• 트리 전체의 시작점

 

2. 내부 노드 ( Internal Node )

• 부모도 있고 자식도 있는 중간 단계 노드

 

3. 리프 노드 ( Leaf Node )

• 더 이상 자식이 없는 노드 ( 끝 점 )

 

▼간선 ( Edge )

정의 : 노드와 노드를 연결하는 선

부모 - 자식 관계를 나타낸다.

항상 방향성이 있으며 ( 위에서 아래로 ) 순환이 없다.

 

 

 

비선형 자료구조를 사용하면 좋은 상황

1. 복잡한 관계 표현

• 선형 자료구조 ( 배열 , 리스트 ) 는 순차적인 관계만 표현 가능
• 현실 세계의 데이터는 계층 구조 ( 회사 조직도 , 폴더 구조 ) 또는 망 형태 ( SNS 친구 관계, 네트워크 ) 가 많다.
• 이런 복잡한 관계를 자연스럽게 모델링하기 위해 필요하다.

 

2. 효율적인 탐색과 연산

• 트리 : 이진 탐색 트리 ( BST ) 에서는 탐색 , 삽입 , 삭제가 평균적으로 빠르다
• 힙 ( Heap ) : 우선순위 큐 구현 시 , 최대값 / 최소값을 빠르게 꺼낼 수 있다
• 그래프 : 최단 경로 탐색 ( BFS ) 등 특정 문제를 빠르게 해결 가능

 

3. 자연스러운 계층적 데이터 저장

• XML , JSON 같은 데이터 포맷은 트리 구조로 표현
• 데이터베이스 인덱스 ( B - Tree ) , 운영체제 파일 시스템도 트리 기반이다.

 

4. 최적화된 문제 해결

• 네비게이션 길찾기 - 그래프
• 게임 AI 트리 ( 의사결정 트리, 상태 머신 ) - 트리
• 압축 알고리즘 ( 허프만 트리 ) - 트리

 

 

정리

비선형 자료구조는 계층적 망형 관계를 표현

효율적인 탐색과 최적화 문제 해결을 위해 사용한다.