[요약] 자료 구조 - 4 [그래프, 신장 트리, 균형 이진 트리, AVL, 히프]

※ 주의 ※
이 블로그는 어디까지나 CS관련 지식을 정리하는 것이 목적입니다. 제가 이해한 내용이 잘못 된 것 같다면 댓글로 남겨주세요. 여러분의 관심이 저의 지식 함양에 도움이 됩니다.

>> 그래프의 개념과 종류 

• 그래프는 다양한 객체와 객체 간의 관계를 표현하는 데 적합한 자료구조입니다. 일반적인 선형 자료구조나 트리 자료구조로는 표현하기 어려운 복잡한 관계를 모델링할 수 있습니다. 그래프는 다음과 같은 기본 개념과 종류로 나뉩니다:
• 그래프의 기본 개념
  • 정점 (Vertex): 그래프에서 객체를 나타내는 요소입니다.
  • 간선 (Edge): 정점 간의 연결 관계를 나타내는 요소입니다.
  • 그래프 G = (V, E): 여기서 V는 그래프의 정점들의 집합, E는 정점을 연결하는 간선들의 집합입니다.
• 그래프는 다양한 상황을 모델링할 수 있으며, 예를 들어, 교통 노선도, 사회적 네트워크, 수도 배관 시스템, 분자 구조 등이 있습니다.

>> 그래프의 구현 방법 

1. 인접행렬 (Adjacency Matrix)

• 개념: 2차원 배열을 사용하여 그래프를 표현합니다.
• 구성:
  • n x n 정방행렬: n은 그래프의 정점 수입니다.
  • 행 번호와 열 번호: 그래프의 정점을 나타냅니다.
  • 행렬 값: 두 정점이 인접하면 1, 아니면 0입니다.
• 무방향 그래프: 행 i의 합과 열 i의 합이 같으며, 이 값은 정점 i의 차수와 같습니다.
• 방향 그래프: 행 i의 합은 정점 i의 진출 차수, 열 i의 합은 정점 i의 진입 차수입니다.

예시 (Python):

def create_adjacency_matrix(vertices, edges):
    matrix = [[0] * len(vertices) for _ in range(len(vertices))]
    for (u, v) in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1  # For undirected graph
    return matrix

2. 인접리스트 (Adjacency List)

• 개념: 각 정점에 대해 인접한 정점들의 리스트를 연결하여 그래프를 표현합니다.
• 구성:
  • 각 정점은 인접 정점들과 연결된 단순 연결 리스트를 가집니다.
  • 각 정점에 대한 헤드 포인터 배열을 사용하여 인접 리스트를 구현합니다.
• 장점: 메모리 사용이 더 효율적이며, 동적 그래프의 경우 삽입과 삭제가 용이합니다.

예시 (Python):

from collections import defaultdict

def create_adjacency_list(vertices, edges):
    adj_list = defaultdict(list)
    for (u, v) in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)  # For undirected graph
    return adj_list

>> 그래프의 종류 

• 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프입니다. 간선이 양쪽 정점을 연결합니다.
• 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프입니다. 간선이 특정 방향으로 정점을 연결합니다.
• 가중 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다. 가중치는 간선의 비용이나 거리 등을 나타냅니다.
• 비가중 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다. 모든 간선의 가중치는 동일하다고 간주됩니다.
• 단순 그래프 (Simple Graph): 자기 루프가 없고, 모든 간선이 두 정점을 연결하는 그래프입니다.
• 완전 그래프 (Complete Graph): 모든 정점이 서로 연결되어 있는 그래프입니다.

>> 그래프의 순회: 깊이 우선 탐색과 너비 우선 탐색 

• 그래프의 탐색은 정점들을 방문하는 방법을 정의하며, 두 가지 주요 방법이 있습니다: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS). 각 방법은 특정 상황에서 유용하며, 알고리즘의 동작 방식과 활용도가 다릅니다.

1. 깊이 우선 탐색 (Depth-First Search, DFS)

• 개념: 시작 정점에서 가능한 한 깊이 탐색을 진행하다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길로 되돌아와 다른 방향으로 탐색을 계속하는 방법입니다.
• 구현:
  • 스택 사용: DFS는 후입선출(LIFO) 구조의 스택을 사용하여 마지막에 만난 갈림길에서부터 탐색을 재개합니다. 재귀 호출을 사용하거나 명시적 스택을 사용할 수 있습니다.
  • 순서: 시작 정점에서 출발하여 인접한 정점을 차례로 깊이 탐색 후, 모든 정점을 방문합니다.

예시 (Python):

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

print(dfs(graph, 'A'))

2. 너비 우선 탐색 (Breadth-First Search, BFS)

• 개념: 시작 정점에서 인접한 정점을 모두 방문하고, 그 다음 단계에서는 방문했던 정점에서 다시 인접한 정점을 차례로 방문하는 방식입니다. 가까운 정점부터 방문합니다.
• 구현:
  • 큐 사용: BFS는 선입선출(FIFO) 구조의 큐를 사용하여 가까운 정점부터 차례로 탐색합니다.
  • 순서: 시작 정점에서 출발하여 인접한 모든 정점을 먼저 방문한 후, 그 다음 단계의 정점들을 방문합니다.

예시 (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
    return visited

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

print(bfs(graph, 'A'))

>> 신장 트리 (Spanning Tree) 

• 개념: 무방향 그래프에서 모든 정점을 포함하면서 사이클이 없는 연결 그래프입니다. 정점의 개수(n)에 대해 간선의 개수는 n-1입니다.
• 생성:
  • 깊이 우선 탐색 신장 트리: DFS를 사용하여 신장 트리를 생성합니다.
  • 너비 우선 탐색 신장 트리: BFS를 사용하여 신장 트리를 생성합니다.
• 최소 비용 신장 트리 (Minimum Spanning Tree, MST)
  • 개념: 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소가 되도록 구성된 신장 트리입니다. 가중치는 간선의 비용, 거리, 시간 등을 나타냅니다.
  • 알고리즘:
    • 크루스칼의 알고리즘 (Kruskal's Algorithm): 모든 간선을 가중치에 따라 정렬한 후, 사이클이 형성되지 않도록 간선을 선택하여 신장 트리를 구성합니다.
    • 프림의 알고리즘 (Prim's Algorithm): 하나의 정점에서 시작하여, 가장 적은 가중치의 간선을 선택하여 트리를 확장합니다.

크루스칼의 알고리즘 예시 (Python):

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    return mst

edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

print(kruskal(4, edges))

프림의 알고리즘 예시 (Python):

import heapq

def prim(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, weight in edges:
        adj[u].append((weight, v))
        adj[v].append((weight, u))
    mst = []
    min_heap = [(0, 0)]
    visited = set()
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u not in visited:
            visited.add(u)
            mst.append((weight, u))
            for edge_weight, v in adj[u]:
                if v not in visited:
                    heapq.heappush(min_heap, (edge_weight, v))
    return mst[1:]

edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

print(prim(4, edges))

>> 이진 탐색 트리의 탐색, 삽입, 삭제 연산 

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

• 이진 탐색 트리는 각 노드가 다음과 같은 성질을 가지는 트리입니다:
  • 모든 노드는 왼쪽 서브트리에 있는 모든 노드보다 큰 값
  • 모든 노드는 오른쪽 서브트리에 있는 모든 노드보다 작은 값
• 이진 탐색 트리에서의 주요 연산은 탐색, 삽입, 삭제입니다.
• 탐색 연산
  • 목표: 주어진 값이 트리에 존재하는지 확인합니다.
  • 절차:
    1. 현재 노드의 값과 검색할 값을 비교합니다.
    2. 검색할 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동합니다.
    3. 검색할 값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동합니다.
    4. 현재 노드가 None일 때까지 이 과정을 반복합니다.

예시 (Python):

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

def search(root, key):
    if root is None or root.value == key:
        return root
    if root.value < key:
        return search(root.right, key)
    return search(root.left, key)

• 삽입 연산
  • 목표: 주어진 값을 이진 탐색 트리에 삽입합니다.
  • 절차:
    • 먼저 탐색을 통해 삽입할 위치를 찾습니다. 탐색 중 같은 값이 발견되면 삽입을 건너뜁니다.
    • 적절한 위치에 새 노드를 삽입합니다.

예시 (Python):

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.value:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

• 삭제 연산
  • 목표: 주어진 값을 트리에서 삭제합니다.
  • 절차:
    1. 삭제할 노드를 탐색하여 찾습니다.
    2. 노드 삭제에는 세 가지 경우가 있습니다:
       • 삭제할 노드가 리프 노드: 노드를 직접 삭제합니다.
       • 삭제할 노드가 하나의 자식만 있는 경우: 삭제할 노드를 삭제하고, 그 자식을 삭제된 노드의 자리에 삽입합니다.
       • 삭제할 노드가 두 자식을 가진 경우: 오른쪽 서브트리에서 최소값을 가진 노드를 찾아서 삭제할 노드의 값으로 대체하고, 그 노드를 삭제합니다.

예시 (Python):

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
    if key < root.value:
        root.left = deleteNode(root.left, key)
    elif key > root.value:
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = minValueNode(root.right)
        root.value = temp.value
        root.right = deleteNode(root.right, temp.value)
    return root

>> 균형 이진 탐색 트리와 AVL 트리 

• 균형 이진 탐색 트리는 노드들의 균형을 유지하여 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 보장하는 트리입니다.
• AVL 트리
  • AVL 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 균형 이진 탐색 트리입니다. 주요 특징은 다음과 같습니다:
    • 균형 인수: 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이. 이 값은 -1, 0, +1이 될 수 있습니다.
    • 균형 유지: 삽입 및 삭제 연산 후 균형을 맞추기 위해 회전 연산을 수행합니다.
• AVL 트리의 회전 연산
  • 회전 연산은 AVL 트리의 균형을 맞추기 위해 사용됩니다. 기본적으로 단일 회전과 이중 회전이 있습니다.
  • 단순 회전:
    • LL 회전: 삽입이나 삭제로 인해 왼쪽 서브트리가 너무 높아질 때 발생합니다. 현재 노드의 왼쪽 자식 노드로 회전합니다.
    • RR 회전: 삽입이나 삭제로 인해 오른쪽 서브트리가 너무 높아질 때 발생합니다. 현재 노드의 오른쪽 자식 노드로 회전합니다.
  • 이중 회전:
    • LR 회전: 왼쪽 서브트리의 오른쪽 자식이 높아질 때 발생합니다. 먼저 왼쪽 자식 노드에 대해 RR 회전을 수행한 후, 현재 노드에 대해 LL 회전을 수행합니다.
    • RL 회전: 오른쪽 서브트리의 왼쪽 자식이 높아질 때 발생합니다. 먼저 오른쪽 자식 노드에 대해 LL 회전을 수행한 후, 현재 노드에 대해 RR 회전을 수행합니다.

회전 연산 예시 (Python):

def rightRotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    return x

def leftRotate(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    return y

def balance(node):
    if not node:
        return node
    balance_factor = height(node.left) - height(node.right)
    if balance_factor > 1:
        if height(node.left.left) >= height(node.left.right):
            return rightRotate(node)
        else:
            node.left = leftRotate(node.left)
            return rightRotate(node)
    if balance_factor < -1:
        if height(node.right.right) >= height(node.right.left):
            return leftRotate(node)
        else:
            node.right = rightRotate(node.right)
            return leftRotate(node)
    return node

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

>> 히프(Heap)의 개념과 추상 자료형 

• 히프의 개념
• 히프는 완전 이진 트리를 기반으로 하는 자료구조로, 각 노드의 키값이 특정한 조건을 만족하는 트리입니다. 주로 두 가지 형태가 있습니다:
  • 최대 히프 (Max-Heap):
    • 각 노드의 키값이 자식 노드의 키값보다 크거나 같습니다.
    • 루트 노드는 히프에서 가장 큰 키값을 가집니다.
  • 최소 히프 (Min-Heap):
    • 각 노드의 키값이 자식 노드의 키값보다 작거나 같습니다.
    • 루트 노드는 히프에서 가장 작은 키값을 가집니다.
• 완전 이진 트리는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 차례로 채워지는 트리입니다.
• 히프의 추상 자료형 (Abstract Data Type, ADT)
  • 히프의 추상 자료형은 다음과 같습니다:
  • 데이터:
    • 원소 n개로 구성된 완전 이진 트리.
    • 각 노드의 키값은 자식 노드의 키값보다 크거나 같거나 작거나 같습니다 (최대 히프 또는 최소 히프에 따라 다름).
  • 연산:
    • 생성: 빈 히프를 생성합니다.
    • 공백 검사: 히프가 비어 있는지 검사합니다.
    • 삽입: 새로운 원소를 히프에 삽입합니다.
    • 삭제: 히프에서 원소를 삭제합니다.
• 히프의 삽입 연산
  1. 완전 이진 트리의 조건을 유지:
     • 새로운 원소를 히프의 마지막 위치에 추가하여 완전 이진 트리의 구조를 유지합니다.
  2. 크기 조건을 만족:
     • 새로 추가된 원소를 적절한 위치로 이동시켜 히프의 속성을 유지합니다.
     • 부모 노드와의 비교를 통해 히프 속성을 만족하도록 조정합니다 (상향식 조정).

예시 (Python):

def heapify_up(heap, index):
    parent = (index - 1) // 2
    if index > 0 and heap[index] > heap[parent]:  # 최대 히프의 경우
        heap[index], heap[parent] = heap[parent], heap[index]
        heapify_up(heap, parent)

def insert(heap, value):
    heap.append(value)
    heapify_up(heap, len(heap) - 1)

• 히프의 삭제 연산
  1. 루트 노드의 원소 삭제:
     • 루트 노드를 삭제하고, 히프의 마지막 원소를 루트 위치로 이동시킵니다.
  2. 원소 개수 조정:
     • 원소의 개수를 n-1로 줄여서 조정합니다.
  3. 히프 속성 유지:
     • 루트 노드에서 시작하여 적절한 위치로 이동시킵니다 (하향식 조정).

예시 (Python):

def heapify_down(heap, index):
    size = len(heap)
    largest = index
    left = 2 * index + 1
    right = 2 * index + 2

    if left < size and heap[left] > heap[largest]:  # 최대 히프의 경우
        largest = left
    if right < size and heap[right] > heap[largest]:  # 최대 히프의 경우
        largest = right
    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        heapify_down(heap, largest)

def delete_root(heap):
    if len(heap) == 0:
        return None
    root_value = heap[0]
    heap[0] = heap.pop()  # 루트 노드의 값을 삭제하고 마지막 노드를 루트로 이동
    heapify_down(heap, 0)
    return root_value

>> 순차 자료구조를 이용한 히프의 구현 

• 히프는 1차원 배열을 사용하여 구현할 수 있습니다. 이 배열에서의 인덱스 관계를 통해 부모 노드와 자식 노드를 쉽게 찾을 수 있습니다.
  • 부모 노드 인덱스: i번째 노드의 부모 노드는 인덱스 (i - 1) // 2에 위치합니다.
  • 왼쪽 자식 노드 인덱스: i번째 노드의 왼쪽 자식 노드는 인덱스 2 * i + 1에 위치합니다.
  • 오른쪽 자식 노드 인덱스: i번째 노드의 오른쪽 자식 노드는 인덱스 2 * i + 2에 위치합니다.