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)

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

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