Non-Linear Data Structure

이번에는 비선형 자료구조에 대해 살펴보자.

비선형 자료구조는 1:N 또는 N:N의 관계를 가진 자료구조이다. 대표적으로 트리와 그래프형 자료구조가 바로 비선형 자료구조이다.

Tree

1개 이상의 노드로 구성되어 마치 나무의 모양을 하고 있기에 트리라는 이름이 붙은 자료구조이다. 우리에게 가장 익숙한 트리 형 자료구조가 바로 컴퓨터의 폴더 구조이다.

위 그림과 같이 하나의 최상위 부모 노드로(root) 부터 자식 노드 들이 파생되는 형태를 가지고 있다. 비선형 자료 구조이기 때문에 각각의 노드 들에 순차적으로 데이터가 저장되지 않으며, 트리 내에 트리가 있는 재귀적 형태의 자료구조이다.

트리 중, 한 방향으로만 자식 노드를 가질 경우 편향 트리라고 하며, 부모 노드의 자식 노드가 2개 이하인 트리를 이진 트리라고 한다. 이진 트리 중 자주 사용되는 트리가 바로 힙 과 이진 탐색 트리이다.

Heap (힙)

힙은 완전 이진트리로써, 최대/최소 값을 찾는 연산을 편리하기 위해 고안된 자료구조이다.

완전 이진 트리란 모든 노드 들이 2개 이하의 자식노드를 가진 트리를 말한다.

힙은 부모 노드가 자식 노드의 합 보다 큰 최대 힙 (parent node >= childs node1 + childs node2)과

반대로 부모 노드가 자식 노드의 합 보다 작은 최소 힙 (parent node <= childs node1 + childs node2) 으로 나뉜다.

공통점은 부모 노드의 값이 항상 최대 힙 에서는 최대, 최소 힙 에서는 최솟값을 가진다는 점이다.

일반적으로 배열을 통하여 힙을 구현하며, 최대 / 최소 힙 에 노드를 삽입 시, 아래와 같은 과정을 따른다.

• 데이터를 마지막 인덱스에 추가

• 부모 노드와 비교해 부모 노드보다 (작다면/ 크다면) 그대로

• 비교 시 부모 노드보다 (크다면 / 작다면) 부모 노드와 위치를 바꾼다.

반대로 노드 삭제 시

• 루트 노드 삭제

• 루트 노드가 있던 자리에 마지막 노드 위치 시킴

• 힙을 재구성 -> 만약 자식 노드보다 루트 노드가 (크다면 / 작다면) 그대로, (작다면 / 크다면) 자식 노드와 위치 변경

이진 탐색 트리 (Binary Search Tree)

이름 그대로 탐색을 위해 사용되는 이진 트리의 형태를 가진 자료구조이다. 따라서, 탐색을 위해 각 노드는 유일한 키 값을 가지며, 노드의 왼쪽 자식 노드는 해당 노드의 키 값보다 항상 작은 값을, 오른쪽 노드는 큰 값을 가진다. 물론, 자식 노드 들도 이진 탐색 트리여야 한다.

이진 탐색 트리는 아래와 같은 과정을 반복하며 탐색을 실행한다.

• 루트 노드 (현재 노드)와 목적 키 값 비교 (일치하면 종료)

• 목적 키 값보다 현재 노드 값이 크다면 왼쪽 자식 노드로 탐색 진행

• 목적 키 값보다 현재 노드 값이 작다면 오른쪽 자식 노드로 탐색 진행

즉, 트리의 높이만큼 탐색이 진행되게 되는데, 위 그림에서는 최대 3번의 탐색이 이루어진다.

노드 삽입 시에는

• 목표 값을 루트 노드 (현재 노드) 와 비교해 같다면 중복 값 발생으로 종료

• 중복되지 않고 목표 값이 현재 노드와 비교해 작다면 왼쪽 자식 노드를 탐색해 비어 있다면 추가, 비어있지 않다면 1의 과정부터 반복

• 중복 되지 않고 목표 값이 현재 노드와 비교해 크다면 오른쪽 자식 노드를 탐색해 비어 있다면 추가, 비어있지 않다면 1의 과정부터 반복

의 연산을 실시한다.

Graph

여러 개의 노드(정)와 노드 들을 연결하는 간선으로 이루어진 자료구조이다. 위에서 살펴본 트리도 그래프의 일종이며, 트리와 다르게 부모/자식 노드의 개념이 없다.

그래프에는 두 정점을 연결하는 간선에 방향이 없는 무 방향 그래프, 방향이 있는 방향 그래프, 그래프의 모든 정점이 연결되어있는 완전 그래프 등의 여러 그래프 가 존재한다.

보통 그래프 구현 시 인접 리스트를 사용하여 구현한다. 인접 리스트란, 각 정점에 인접한 정점 들을 리스트로 표현한 것을 말한다.