[자료구조] 비선형 자료 구조

비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 의미한다. 일반적으로 트리(Tree)나 그래프(Graph)를 의미한다.

1. 그래프(Graph)

그래프는 정점과 간선으로 이루어진 자료 구조를 의미한다. "어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다"고 하였을 때, 여기서 말하는 어떠한 곳은 정점(Vertex)을 의미하며, 무언가는 간선(Edge)를 의미한다.
간선은 단방향 간선과 양방향 간선으로 나뉘어진 두 가지로 나뉘어진다.

1-1. 단방향 간선 (Directed Edge)

단방향 간선은 한쪽 방향으로만 이동할 수 있는 간선이다. 노드 A에서 노드 B로의 경로가 있을 때, 이 간선을 따라 A에서 B로 이동할 수 있지만, 반대 방향(B에서 A로)은 불가능하다. 이러한 간선은 방향이 명확히 지정된 유향 그래프(directed graph)에서 사용된다.

1-2. 양방향 간선 (Undirected Edge)

양방향 간선은 두 노드 간의 이동이 양쪽 모두 가능한 간선이다. 노드 A와 B가 양방향 간선으로 연결되어 있다면, A에서 B로, B에서 A로 자유롭게 이동할 수 있다. 이러한 간선은 방향이 없는 무향 그래프(undirected graph)에서 사용된다.

정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다. 앞 선 그림은 outdegree는 3개, indegree는 두 개인 상태이다.

또한, 정점은 약자로 V 또는 U라고 하며, 보통 어떤 정점으로부터 시작해서 어떤 정점까지 간다를 "U에서부터 V로 간다"라고 표현한다. 지금까지 설명한 정점과 간석으로 이루어진 집합을 그래프(Graph)라고 한다.

1-3. 가중치(weight)

가중치는 간선과 정점 사이에 드는 비용을 의미한다. 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면 1번 노드에서 2번 노드까지의 가중치는 한 칸을 의미한다.

2. 트리(Tree)

트리(Tree)는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합을 의미한다. 루트 노드, 내부 노드, 리프 노드 등으로 구성된다. 트리로 이루어진 집합을 '숲'이라고 한다.

2-1. 트리의 특징

트리는 그래프의 일종이며 다음 특징을 가진다는 점이 다르며 부모, 자식 계층 구조를 가진다. 현재 5번 노드는 6번 노드와 7번 노드의 부모 노드이고, 6번 노드와 7번 노드는 5번 노드의 자식 노드이다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모 노드이며, 아래에 있으면 자식 노드가 된다.

V - 1 = E라는 특징을 가진다. 간선 수는 노드 수 - 1를 의미한다. 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.

2-2. 트리의 구성

트리는 루트 노드, 내부 노드, 리프 노드로 이루어져 있다.

루트 노드는 가장 위에 있는 노드를 의미한다. 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.

내부 노드는 루트 노드와 내부 노드 사이에 있는 노드를 의미한다. 리프 노드는 자식 노드가 없는 노드를 의미한다.

 

트리의 높이와 레벨

깊이는 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 의미한다. 높이는 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미한다. 레벨은 보통 깊이와 같은 의미를 한다. 서브트리는 트리 내 하위 집합을 의미한다. 또한, 트리 내에 있는 부분집합이라고도 본다.

2-3. 이진 트리

이진 트리는 자식의 노드 수가 두 개 이하인 트리를 의미한다. 이진 트리의 종류로는 정이진 트리, 완전 이진 트리, 변질 이진 트리, 포화 이진 트리, 균형 이진 트리가 있다.

2-4. 이진 탐색 트리

이진 탐색 트리는(BST)는 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리를 의미한다.

왼쪽 및 오른쪽 하위 트리도 해당 특성을 가진다. 이렇게 두면 '검색'을 하기에 용이하다. 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있기 때문에 10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으면 된다. 보통 요소를 찾을 때 이진 탐색 트리의 경우 O(logn)이 걸린다. 하지만 최악의 경우 O(n)이 걸린다. 왜냐하면 이진 탐색 트리는 삽인 순서에 따라 선형적일 수 있기 때문이다.

2-5. AVL 트리

AVL 트리(Adelson-Velsky and Landis tree)는 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다는 특징을 가지고 있다.

탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며, 삽입, 삭제할때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.

2-6. 레드 블랙 트리

레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며, 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용된다.

"모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다" 라는 규칙을 기반으로 균형을 잡는 트리이다.

3. 힙 (Heap)

힙(Heap)은 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지닌 트리이다.

최대힙은 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져있다.

최소힙은 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 하며 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져있다.

3-1. 최대힙의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. 새로운 노드를 부모 노드들과 크기를 비교하며 교환을 수행하면서 힙의 성질을 만족시킨다.

3-2. 최대힙의 삭제

최대힙에서 최대값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성된다.

4. 우선순위 큐 (Priority Queue)

우선순위 큐는 우선순위 대기열이라고 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조를 의미한다. 이러한 우선순위 큐는 힙을 기반으로 구현된다.

5. 맵 (Map)

맵 (Map)은 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조를 의미한다. 맵은 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.
맵을 쓸때는 Map<String, int> 형태로 구현한다. 배열과 비슷하게 clear() 메서드로 맵에 있는 모든 요소를 삭제할 수 있으며, size()로 map의 크기를 구할 수 있다. 또한, earase()로 해당 키와 키에 매핑된 값을 지울 수 있다.

맵은 해시 테이블을 구현할 때 사용하며 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map으로 구성되어 있다.

6. 셋 (Set)

셋 (Set)은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 희소한(unique)값만 저장하는 자료구조이다.

7. 해시 테이블 (Hash Table)

해시 테이블 (Hash Table)은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블을 의미한다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현한다.