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

비선형 자료 구조

비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

1. 그래프

그래프는 정점과 간선으로 이루어진 자료 구조를 말한다.

[ 정점과 간선 ]

어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 "어떠한 곳"이 정점, "무언가"는 간선이 된다.

[ 그래프의 종류 ]

• 방향 그래프: 방향이 있는 간선을 갖는 그래프. 단방향 관계를 나타내고 각 간선은 한 방향으로만 진행할 수 있다.
• 무방향 그래프: 방향이 없는 간선을 갖는다. 간선은 양방향 관계를 나타내고 각 간선은 양방향으로 진행할 수 있다.
• 가중 그래프: 그래프의 간선에 특정 가중치가 부여된 형태의 그래프다. 가중 그래프에서는 간선이 연결하는 경로의 비용, 거리, 시간 또는 다른 유형의 가중치를 나타낸다.
• 완전 그래프: 그래프의 모든 정ㅇ점이 서로 연결된 그래프다. N개의 정점을 가진 완전 그래프는 모든 가능한 간선을 가지고 있으며 간선의 개수는 N x (N - 1) / 2다.

[ BFS / DFS ]

BFS( 너비 우선 탐색 ): 시작 정점에서 가장 가까운 정점부터 탐색을 시작하여, 점차 거리가 멀어지는 정점을 탐색한다. 현재 탐색중인 정점과 인접한 모든 정점을 방문하고, 다음으로 그 정점들과 인접한 정점을 탐색하는 방식으로 진행된다.

DFS( 깊이 우선 탐색 ) : 한 정점에서 시작하여 한 방향으로 갈 수 있을 때까지 깊게 탐색하고, 더 이상 갈 곳이 없으면 이전 정점으로 돌아와 다른 경로를 탐색하는 방식이다. 가능한 한 깊이 담색을 진행하고, 막히면 이전 정점으로 돌아가 다른 경로를 탐색한다.

2. 트리

트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 루트 노드, 내부 노드, 리프 노드 등으로 구성된다. 주로 데이터의 계층적인 관계를 표현하는 데 사용된다.

[ 트리의 특징 ]

• 노드가 n개인 트리는 항상 n-1 개의 간선을 가진다.
• 사이클이 없는 견결 그래프다. 트리에서 임의의 두 정점 사이에 유일한 경로만 존재해야 한다.
• 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.

[ 트리의 구성 ]

• 루트 노드: 가장 위에 있는 노드로 부모가 없는 유일한 노드다. 루트에서 시작하여 트리의 모든 노드를 탐색할 수 있다.
• 내부 노드: 루트 노드와 내부 노드 사이에 있는 노드를 뜻한다.
• 리프 노드: 자식이 없는 노드로, 트리의 가장 끝에 위치한다.

[ 이진 트리 ]

이진 트리는 자식의 노드 수가 두 개 이하인 트리를 말한다. 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분되며, 각 자식은 서브트리로 연결 될 수 있다.

이진 트리의 종류

• 정이진 트리: 자식 노드가 0 또는 두 개인 이진 트리를 의미한다.
• 완전 이진 트리: 왼쪽에서부터 채워져 있는 이진 트리를 의미한다. 마지막 레벨을 지외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
• 균형 이진 트리: 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미한다. 레드 블랙 트리는 균형 이진 트리 중 하나다.
• 포화 이진 트리: 모든 노드가 꽉 차 있는 이진 트리를 의미한다.

[ 이진 탐색 트리 ]

이진 트리의 한 종류로 탐색, 삽입, 삭제 등의 연산이 효율적으로 수행되도록 설계된 자료 구조다. 각 노드는 최대 두 개의 자식 노드를 가진다. 각 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들이, 오른쪽 서브트리에는 그 노드의 값보다 큰 값들이 위치한다.

[ AVL 트리 ]

이진 검색 트리의 한 종류다. 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 균형 이진 트리다. AVL 트리는 이진 검색 트리의 단점을 보완하기 위해 생겼다. 이진 검색 트리는 데이터를 삽입하는 순서에 따라 성능이 크게 달라질 수 있다. 최악의 경우 O(n) 시간 복잡도를 갖게 된다.
따라서 삽입이나 삭제 시 회전하며 균형을 유지하는 AVL 트리를 사용하여 시간 복잡도를 O(logn)을 유지하게 된다.

[ 레드 블랙 트리 ]

레드 블랙 트리는 자가 균형 이진 검색 트리의 한 종류로 데이터를 효율적으로 저장하고 검색할 수 있도록 만들어진 자료 구조다. AVL 트리와 유사하지만 균형을 유지하는 방식에서 차이가 있다.

• 각 노드는 레드 또는 블랙을 색칠된다.
• 루트 노드는 항상 블랙이다.
• 레드 노드는 두 개의 연속한 레드 노드를 가질 수 없다.
• 모든 리프 노드는 블랙이며, 리프 노드는 null 노드를 나타낸다.
• 각 노드에서 리프 노드까지의 모든 경로는 같은 수의 블랙 노드를 가져야 한다.

해당 조건들을 통하여 레드 블랙 트리는 높이를 균형 있게 유지한다. 이를 통해 최악의 경우 O(logn) 시간 복잡도를 갖게 된다.

3. 힙

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

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

최대힙의 삽입

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

최대힙의 삭제

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

4. 우선순위 큐

우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조다. 단순히 리스트를 이용하여 구현할 수도 있고 힙을 이용하여 구현할 수도 있다.

5. 해시 테이블

해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가진다. 해시 함수를 사용해 키 값을 특정 인덱스로 변환하고, 이 인덱스에 데이터를 저장하는 방식으로 동작한다. 데이터를 저장하면 직접 키를 기반으로 바로 인덱스를 찾을 수 있어 데이터 접근 속도가 매우 빠르다.