2024년 6월 1일 작성
비선형 자료 구조 (Non-linear Data Structure)
비선형 자료 구조는 data가 순서 없이 복잡하게 연결된 구조로, 계층적 또는 network 형태로 연결된 자료 구조를 의미합니다.
비선형 자료 구조 : Data가 순서 없이 복잡하게 연결된 구조
flowchart TD
A --- B
A --- C
A --- F
B --- D
B --- F
C --- D
C --- E
D --- F
E --- F
- 비선형 자료 구조(Non-linear Data Structure)는 data가 순차적으로 나열되지 않고 계층적 또는 network 형태로 연결된 자료 구조를 의미합니다.
- 비선형 자료 구조는 한 node가 여러 개의 자식 node를 가질 수 있으며, data 사이의 관계가 더 복잡하게 얽혀 있습니다.
- 따라서 선형 자료 구조보다 data 요소들 간의 복잡한 관계를 더 잘 표현할 수 있습니다.
- 비선형 자료 구조는 한 node가 여러 개의 자식 node를 가질 수 있으며, data 사이의 관계가 더 복잡하게 얽혀 있습니다.
비선형 자료 구조의 특징
- 계층적 관계 : data 요소들이 부모-자식 관계와 같이 계층적으로 배열됩니다.
- 이러한 구조는 Tree와 같이 조직도나 file system에서 자주 사용됩니다.
- 다대다 관계 : 각 data 요소가 여러 다른 요소들과 연결될 수 있습니다.
- 예를 들어, Graph에서는 하나의 정점이 여러 간선을 통해 다른 여러 정점들과 연결될 수 있습니다.
- 복잡한 연결 : data 요소들 간의 관계가 복잡하게 얽혀 있으며, 순환 구조를 가질 수도 있습니다.
- 이는 network나 social network graph와 같은 구조를 표현할 때 유용합니다.
비선형 자료 구조의 장점
- 효율적인 검색 및 접근 : 비선형 자료 구조는 특정 data에 대한 빠른 검색 및 접근을 가능하게 합니다.
- 예를 들어, 이진 탐색 Tree에서는 data의 삽입, 삭제, 검색이 평균적으로
O(log n)
의 시간 복잡도로 이루어질 수 있습니다.
- 예를 들어, 이진 탐색 Tree에서는 data의 삽입, 삭제, 검색이 평균적으로
- 유연한 Data 표현 : 비선형 자료 구조는 복잡한 data 관계를 자연스럽게 표현할 수 있어, 현실 세계의 다양한 문제를 modeling하기에 적합합니다.
- 예를 들어, Graph는 도로망, social network, 전기 회로 등을 modeling하는 데 유용합니다.
- 효율적인 Memory 사용 : 비선형 자료 구조는 필요한 부분만 memory에 적재(load)하여 사용할 수 있습니다.
- 따라서 대규모 data를 처리할 때 memory 사용을 효율적으로 관리할 수 있습니다.
비선형 자료 구조의 단점
- 구현의 복잡성 : 비선형 자료 구조는 선형 자료 구조보다 구현이 복잡합니다.
- 각 data 요소 간의 연결을 관리하고 유지하는 것이 어렵기 때문에, 구현 시 더 많은 주의가 필요합니다.
- 탐색의 복잡성 : data 요소 간의 관계가 복잡하여, 특정 data를 찾기 위한 탐색 과정이 복잡해질 수 있습니다.
- 예를 들어, Graph 탐색에서는 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)과 같은 algorithm을 사용해야 합니다.
- 추가적인 Overhead : data 요소 간의 관계를 저장하기 위한 추가적인 memory overhead가 발생할 수 있습니다.
- 예를 들어, Graph의 인접 행렬 또는 인접 list를 저장하기 위한 추가적인 memory 공간이 필요합니다.
비선형 자료 구조의 종류 : Graph와 Tree
Graph | Tree | |
---|---|---|
정의 | node와 그 node를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조. | Graph의 한 종류. DAG(Directed Acyclic Graph, 방향성이 있는 비순환 Graph)의 한 종류. |
방향성 | 방향(directed) Graph, 무방향(undirected) Graph 모두 존재함. | 방향(directed) Graph. |
Cycle | cycle 가능. 자체 간선(self-loop) 가능. 순환(cyclic) Graph, 비순환(acyclic) Graph 모두 존재함. |
cycle 불가능. 자체 간선(self-loop) 불가능. 비순환(acyclic) Graph. |
Root Node | root node의 개념이 없음. | 한 개의 root node만이 존재함. 모든 자식 node는 한 개의 부모 node만들 가짐. |
부모-자식 | 부모-자식의 개념이 없음. | 부모-자식 관계. top-bottom 또는 bottom-top으로 이루어짐. |
Model | network model. | 계층 model. |
순회 | DFS, BFS. | DFS, BFS 안의 Pre-order, In-order, Post-order. |
간선의 수 | Graph에 따라 간선의 수가 다름. 간선이 없을 수도 있음. |
node가 N개인 Tree는 항상 N-1개의 간선을 가짐. |
경로 | - | 임의의 두 node 간의 경로는 유일함. |
예시 및 종류 | 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목. | 이진 Tree, 이진 탐색 Tree, 균형 Tree(AVL Tree, Red-Black Tree), 이진 Heap(최대 Heap, 최소 Heap). |