[자료구조] 비선형(NonLinear) 자료 구조

 

자료 구조는 생각보다 다양한 형태를 가진다.
어떤 형태의 자료 구조를 사용하느냐에 따라 알고리즘의 효율성도 천차만별이다. 

 

 

비선형(NonLinear) 자료 구조

선형 구조는 자료를 저장하고 꺼내는 것에 초점을 맞추는 반면 비선형 구조는 자료를 어떻게 표현할지에 초점을 맞추고 있다.

 

다른 말로 표현하면 선형 구조는 일렬로 정렬된 데이터 구조, 비선형 구조는 하나의 자료 뒤에 여러 개의 자료가 연결되어 있는 형태다. 즉, 데이터 요소가 계층 구조를 가지고 있다.

 

2024.08.23 - [CS] - [자료구조] 선형(Linear) 자료구조

[자료구조] 선형(Linear) 자료구조의 종류와 특징

 

그래프(Graph)

그래프는 정점과 간선으로 구성되어 있는 자료구조다.

 

정점: 노드들의 집합

간선: 정점들 사이의 상호 연결의 집합

 

그래프는 G = (V, E) 와 같이 표현한다.

 

그래프 종류

무방향 그래프

무방향 그래프는 간선을 표현하는 두 정점 사이의 순서가 없는 그래프를 말한다.

n개의 정점으로 구성된 무방향 그래프의 최대 간선 수는 n(n-1)/2개다.

 

방향 그래프

방향 그래프는 간선을 표현하는 두 정점 사이의 순서가 있는 그래프를 말한다.

n개의 정점으로 구성된 무방향 그래프의 최대 간선 수는 n(n-1)개다.

트리(Tree)

트리는 그래프 중 하나로 그래프의 특징을 가짐과 동시에 트리 구조로 배열된 계층적 데이터의 집합이다.

 

인공지능에서의 결정 트리, 컴퓨터 디스크의 디렉토리 구조 등 여러 분야에서 트리 구조가 활용된다.

 

트리는 크게 루트 노드, 내부 노드, 리프 노드로 구성된다. 이렇게 구성된 하나의 트리를 숲이라고 한다.

 

루트 노드: 가장 위에 있는 노드

내부 노드: 루트 노드와 내부 노드 사이에 있는 노드

리프 노드: 자식 노드가 없는 노드

 

트리의 종류

이진트리

자식의 노드 수가 두 개 이하인 트리

 

이진탐색트리

노드의 오른쪽 하위 트리에 노드 값보다 큰 값만 포함되고 왼쪽 하위 트리에는 노드 값보다 작은 값만 포함되는 트리

 

AVL 트리

왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1이 넘지 않는 트리