[CS] 자료 구조의 분류 - 비선형 자료 구조 #1 (그래프, 트리)

Janet·2023년 9월 18일

CS 자료 구조

CS

목록 보기

15/17

자료 구조는 크게 선형 자료 구조와 비선형 자료 구조로 나뉜다.

선형 자료 구조: 연결 리스트, 배열(선형 리스트), 스택, 큐, 벡터 등.
비선형 자료 구조: 그래프, 트리, 해시 테이블, 힙, 맵, 셋, 우선순위 큐 등.

비선형 자료 구조 (Non-Linear Data Structures)

비선형 자료 구조란 데이터 요소들 간에 계층적인 관계가 없는 자료 구조를 의미한다.
데이터 요소들이 일렬로 연결되어 있지 않으며, 자료 순서나 관계가 복잡한 구조로 각 요소가 다른 요소와 관련성을 갖는 경우가 많다.
비선형 자료 구조는 선형 자료 구조와 대조되며, 선형 자료 구조는 요소들이 일렬로 나열되어 있는 구조를 가진다.

1. 그래프 (Graph)

그래프는 다양한 형태의 객체 간 연결 관계를 표현하는 데 사용된다. 각종 네트워크(소셜/컴퓨터 네트워크), 도로망 등을 모델링하는 데 유용하다.
그래프는 정점과 간선으로 이루어진 자료 구조이다.
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 '어떠한 곳'은 정점(vertax)이 되고, '무언가'는 간선(edge)이 된다.

1-1. 그래프의 구성 요소 (정점, 간선, 가중치)

정점 (Vertax / Node)
- 정점(또는 노드)은 객체나 개체를 나타낸다.
- 예시로는 소셜 네트워크에서 각 사용자, 도로망에서 각 교차로, 컴퓨터 네트워크에서 각 컴퓨터는 정점으로 표현될 수 있다. 또한, A라는 사람이 B라는 사람이 있는 곳을 향해 간다고 했을 때, A라는 사람과 B라는 사람은 하나의 정점이고, B로 향하는 길은 간선이 된다.
간선 (Edge)
- 간선(엣지)은 정점(노드)들을 연결하는 선으로, 그래프 내의 두 정점 간의 관계를 나타낸다.
- 두 정점 간의 관계는 양방향 혹은 단방향이다.
가중치 (Weight)
- 가중 그래프에서 간선은 가중치를 가질 수 있다.
- 가중치는 간선과 정점 사이에 드는 비용을 의미한다.
- 예시로는 1번 노드(정점)에서 2번 노드(정점)까지 가는 비용(거리)가 1칸이라면, 1번 노드에 2번 노드까지의 가중치가 1칸이라는 의미이다.
- 가중 그래프는 실제 세계의 다양한 상황을 모델링하는 데 유용한데, 최단 경로 문제, 네트워크 흐름 최적화, 스패닝 트리 등의 다양한 문제에 응용된다.

1-2. 그래프의 종류

무방향 그래프(Undirected Graph)
- 간선에 방향이 없는 그래프로, 간선은 두 정점을 양방향으로 연결한다.
- 사용 예시
  - 소셜 네트워크 그래프: 여러 사용자 간의 친구 관계를 표현할 때, 사용자를 정점으로, 친구 관계를 무방향 간선으로 나타낼 수 있다. 간선의 방향성이 없으며 친구 관계는 양방향이다.
  - 도로 네트워크: 도로와 교차로를 정점으로 나타내고, 도로를 무방향 간선으로 표현한다. 차량은 양방향으로 이동할 수 있으므로 간선의 방향성이 없다.
방향 그래프 (Directed Graph / Digraph)
- 간선에 방향이 있는 그래프로, 간선은 한 정점에서 다른 정점으로 방향을 가지며, 단방향으로 이동한다.
- 사용 예시
  - 웹 페이지 링크 그래프: 웹 페이지를 정점으로 나타내고, 하나의 웹 페이지에서 다른 웹 페이지로의 하이퍼링크를 방향 간선으로 표현한다. 이러한 방식으로 웹 검색 엔진은 웹 페이지의 중요성을 계산하고 검색 결과를 반환한다.
  - 전자 메일 통신 그래프: 사용자 간의 이메일 통신을 나타내는 그래프에서, 이메일 메시지는 보낸 사람에서 받는 사람으로의 방향 간선으로 표현된다. 각 이메일은 단방향 통신을 나타낸다.
가중 그래프 (Weighted Graph)
- 간선에 가중치가 할당된 그래프로, 간선마다 추가 정보(가중치)가 포함된다.
- 사용 예시
  - 도시 간 비행 노선 그래프: 여러 도시를 정점으로 나타내고, 도시 간의 항공 노선을 가중치가 있는 간선으로 표현한다. 가중치는 비행 거리나 비용을 나타내어 최소 비용 경로를 찾는 데 사용된다.
  - 소셜 네트워크 친밀도 그래프: 사용자 간의 친밀도를 나타내는 그래프에서, 간선의 가중치는 두 사용자 사이의 친밀도 또는 상호 작용의 정도를 나타낸다. 이를 통해 친밀한 관계를 분석하거나 추천 시스템을 개발할 수 있다.

2. 트리 (Tree)

트리는 계층적 자료 구조로서, 정점(노드)과 간선(edge)으로 이루어져 있다.
노드(Node)들이 연결된 방식을 나타내는 자료 구조로, 트리는 하나의 루트 노드(root node)에서 시작하여 여러 개의 자식 노드(child node)들로 확장되는 구조를 갖는다.
각 노드는 부모 노드와 자식 노드 사이의 관계를 가지며, 이러한 관계는 계층적인 구조를 형성한다.
루트 노드, 내부 노드, 리프 노드 등으로 구성된다.
트리로 이루어진 집합을 숲이라고 한다.

이미지 출처: https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

2-1. 트리의 구성

루트 노드(Root Node): 트리에서 최상위에 있는 노드.
내부 노드(Internal Node): Leaf Node가 아닌 노드.
리프 노드(Leaf Node): 자식이 없는 노드. '잎 노드', '단말 노드', '말단 노드'라고도 부른다.
부모 노드(Parent Node): 어떤 노드보다 위에 있는 노드.
자식 노드(Child Node): 어떤 노드보다 아래에 있는 노드.
형제 노드(Sibling Node): 같은 부모를 가지는 노드.
간선(Edge): 노드를 연결하는 선 ('Link' 혹은 'Branch'라고도 한다.)

2-2. 트리 관련 용어 (트리의 높이와 레벨 등)

크기(size): 자신을 포함한 모든 자손 노드의 개수
깊이(depth): 루트 노드에서 특정 노드까지 최단 거리로 도달하기 위해 거쳐야 하는 간선의 수
레벨(level): 트리의 레벨은 주어지는 문제마다 조금씪 다르지만 보통 깊이와 같은 의미를 지닌다. 트리의 특정 깊이(레벨)를 가지는 노드의 집합이다.
서브트리(subtree): 트리 내의 하위 집합(부분 집합)으로, 트리 내의 어떤 노드와 그 노드의 모든 자손 노드로 이루어진 부분 트리를 말한다.
차수(degree): 하위 트리의 개수 / 간선 수 = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height of tree): 루트 노드에서 가장 멀리 있는 리프 노드까지의 거리
간선 수 = 노드 수 - 1

2-3. 트리의 종류 (이진 트리, 이진 탐색 트리, AVL 트리, 레드 블랙 트리)

🌲 이진 트리 (Binary Tree): 자식의 노드 수가 2개 이하인 트리이다.

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

🌲 이진 탐색 트리 (BST, Binary Search Tree)

노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리를 말한다.
검색을 하기에 용이하다.
시간 복잡도: 평균적으로 O(log n)이 걸린다. 최악의 경우 O(n)이 걸린다. (삽입 순서에 따라 선형적일 수 있기 때문에.)

🌲 AVL 트리 (Adelson-Velsky and Landis Tree)

AVL 트리는 위에서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 항상 균형을 잡는 이진 탐색 트리, 즉 자가 균형 이진 탐색 트리(self-balancing binary search tree)이다.
두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다.
시간 복잡도: 탐색, 삽입, 삭제 모두 O(log n)이다. (n: 노드의 개수)
삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전(rotation)시키며 균형을 잡는다.
AVL 트리에서 균형이 무너졌는지 판단을 위해 Balance Factor(BF)를 활용한다.

BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이
AVL 트리는 모든 Node의 BF가 -1, 0, 1 중 하나여야 한다. 이를 벗어나면 균형이 깨졌다는 것을 의미하고, 회전(rotation)을 하게 된다.

🌲 레드 블랙 트리 (Red-Black Tree)

레드 블랙 트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)이다.
각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중 트리가 균형을 유지하도록 하는 데 사용된다.
"모든 리프 노드와 루트 노드는 블랙이고, 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 등의 규칙을 기반으로 균형을 잡는 트리이다.
시간 복잡도: 탐색, 삽입, 삭제 모두 O(log n)이다.

cf. NIL: 트리 구조를 나타낼 때, 어떤 노드는 자식(child)를 하나만 가질 수 있고, 리프 노드는 데이터를 담을 수 있다. 레드-블랙 트리도 이와 같은 방법으로 나타내 볼 수 있지만, 그런 표현 방식으로는 레드-블랙 트리의 특성이 변하고, 알고리즘과 상충될 수 있다. 그래서, 위 이미지에서는 "nil leaves" 나 "null leaves"를 표현하고 있는데, 이 "null leaf"는 위의 그림에서와 같이 자료를 갖지 않으며, 트리의 끝을 나타내는 데만 쓰인다. 트리 구조를 그림으로 표현할 때, 종종 이 "null leaf"를 생략하고 그리는 경우가 많은데, 그러면 그림상으로는 레드-블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있으나 실제로는 그렇지 않다. 이렇게 함으로써, 모든 노드들은 설령 하나 또는 두개의 자식이 "null leaf" 일지라도, 두개의 자식(children)을 가지게 된다.

Reference.