[CS] 비선형 자료구조 그래프, 트리, 힙, 맵, 셋, 해시 테이블에 대해 알아보자

hurlud 2024. 5. 7. 23:51

비선형 자료구조인 그래프, 트리, 힙, 맵, 셋, 해시테이블에 대해 작성한 글입니다.

비선형 자료구조

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

그래프는 정점(vertex)과 간선(edge)으로 이루어진 자료 구조를 말합니다.

정점(Vertex): 그래프의 구성 요소 중 하나로, 데이터를 저장하는 노드입니다. 예를 들어, 소셜 네트워크에서 사용자나 지역망에서 장치들이 정점이 될 수 있습니다.
간선(Edge): 그래프의 정점들을 연결하는 선으로, 노드들 간의 관계를 나타냅니다. 간선은 방향이 있을 수도 있고 없을 수도 있습니다.
방향성(Directionality): 간선이 방향 그래프(Directed Graph)일 경우, 방향성이 있습니다. 즉, 간선이 한 정점에서 다른 정점으로의 방향을 가집니다. 반면에 무방향 그래프(Undirected Graph)에서는 간선에 방향성이 없습니다.
가중치(Weight): 간선에 연결된 두 정점 간의 관계를 나타내는 값으로, 예를 들어 거리, 비용, 시간 등을 나타낼 수 있습니다. 이러한 그래프를 가중 그래프(Weighted Graph)라고 합니다.
사이클(Cycle): 그래프에서 한 정점에서 시작하여 다시 같은 정점으로 돌아오는 경로를 말합니다.

트리(Tree)는 비선형 자료구조로, 계층적인 관계를 가지는 데이터를 저장하는 데 사용됩니다. 트리는 한 노드가 다수의 자식 노드를 가질 수 있는 구조로, 부모-자식 관계를 가지는 그래프의 특별한 형태입니다.

트리의 주요 특징은 다음과 같습니다:

루트(Root): 트리의 최상위 노드로, 다른 모든 노드의 조상이 됩니다. 모든 경로는 루트에서부터 시작됩니다.
부모(Parent)와 자식(Child): 트리의 노드들은 부모-자식 관계를 가집니다. 부모 노드는 자식 노드를 가리키며, 자식 노드는 하나의 부모 노드를 가집니다.
리프(Leaf): 자식이 없는 노드를 말합니다. 즉, 리프 노드는 트리의 가장 하위에 위치합니다.
간선(Edge): 부모와 자식 노드를 연결하는 선을 말합니다. 트리에서는 각 노드들을 연결하는 간선의 수가 노드의 수보다 하나 작습니다.
높이(Height): 트리의 최대 레벨을 높이라고 합니다. 즉, 루트 노드부터 리프 노드의 거리를 깊이를 의미합니다.
깊이(Depth): 루트 노드부터 특정 노드까지의 경로 길이를 말합니다. 루트의 깊이는 0이며, 각 노드의 깊이는 부모의 깊이보다 1 증가합니다.

트리는 계층적인 구조를 효과적으로 표현하기 때문에 다양한 분야에서 사용됩니다. 예를 들어, 데이터베이스의 인덱스 구조, 파일 시스템의 디렉토리 구조, 계층적 조직 구조, 알고리즘의 재귀적 구현 등에 사용됩니다.

트리는 이진 트리(Binary Tree)를 포함하여 여러 종류로 확장될 수 있습니다. 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 또한, 이진 트리의 특별한 형태로 AVL 트리, 이진 탐색 트리(BST), 레드-블랙 트리 등의 자료구조가 있습니다.

정이진 트리(full binary tree): 자식 노드가 0 또는 두 개인 이진 트리
완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.
변질 이진 트리(defenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리
포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차있는 이진 트리
균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미합니다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나입니다.

이진 탐색 트리(Binary Search Tree)는 노드의 오른쪽 하위 츠리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값만 들어 있는 트리를 말합니다.

이때 왼쪽 및 오른쪽 하위 트리도 해당 특성을 가집니다. 이렇게 두면 검색을 하기에 용이합니다. 보통 요소를 찾을 때 이진 탐색 트리의 경우 O(logn)이 걸립니다. 하지만 최악의 경우 O(n)이 걸립니다.

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

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

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

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

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

힙에는 어더한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있습니다.

맵(Map)은 키(Key)와 값(Value)의 쌍으로 이루어진 자료구조입니다. 각 키는 고유하며, 키에 대응하는 값은 중복될 수 있습니다. 맵은 키를 사용하여 값을 검색하거나 저장하는 데 사용됩니다. 맵은 보통

맵의 주요 특징은 다음과 같습니다:

고유한 키: 맵은 각 키가 고유해야 합니다. 즉, 중복된 키를 허용하지 않습니다.
키-값 쌍 저장: 맵은 각 키와 값의 쌍을 저장합니다. 이를 통해 키를 사용하여 값에 빠르게 접근할 수 있습니다.
검색과 삽입: 맵은 키를 사용하여 값을 검색하거나 삽입하는 데 효과적입니다. 키를 사용하여 값을 검색할 때는 일반적으로 O(1) 또는 O(log n)의 시간 복잡도를 가집니다.
순서가 없음: 맵은 키-값 쌍의 순서를 보장하지 않습니다. 즉, 값들이 저장된 순서대로 반환되지 않습니다.

Set은 유일한 요소들의 집합을 표현하며, 요소들의 순서를 보장하지 않습니다. Set은 중복을 허용하지 않고 고유한 요소를 저장하고 관리해야 할 때 사용됩니다.

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