B-tree, B+tree, Trie, Minimum Spanning Tree

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

 

B-tree는 데이터베이스와 파일 시스템에서 널리 사용되는 자료구조로, 데이터를 정렬된 상태로 저장하고 효율적인 검색, 순차 접근, 삽입, 삭제를 지원한다. 이진 탐색 트리(BST)를 확장한 형태로, 더 많은 자식을 가질 수 있어 디스크와 같은 보조 메모리에 저장된 대량의 데이터를 관리하는 데 적합하다.

 

모든 리프 노드가 같은 레벨에 있어 균형 잡힌 트리를 유지한다.노드가 가득 찰 경우, 중간값을 기준으로 노드를 분할하여 상위 노드로 키를 올린다.루트에서 리프로 가는 경로의 길이가 모두 동일하다.각 노드는 최대 m개의 자식을 가질 수 있는데, 이때 m은 트리의 차수이다.

 

트리를 탐색하며 키 값을 비교하여 데이터 위치를 찾는다.적절한 위치에 새로운 키를 삽입하고, 필요시 노드 분할을 수행한다.키를 삭제하고, 필요시 노드 병합이나 재배치를 통해 트리의 균형을 유지한다.

 

키-값 쌍을 사용하여 레코드를 빠르게 찾을 수 있게 해준다. 파일의 메타데이터를 관리하거나, 파일 내의 특정 데이터를 찾는 데 사용된다.

def insert(node, key):
    # 적절한 리프 노드 찾기
    if node is leaf:
        if node has space:
            insert key in node
        else:
            split node
            insert key in appropriate node
    else:
        find child node that should contain key
        insert(child node, key)

 

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+ Tree Visualization

 

B+트리는 데이터베이스와 파일 시스템에서 사용되는 인덱스 메커니즘의 일종이다. 이는 탐색, 삽입, 삭제, 순회 등의 동작을 로그 시간 내에 수행할 수 있는 이진 검색 트리의 확장된 형태로, 디스크 I/O 작업의 최소화를 목표로 한다.

 

B+트리는 전에 포스팅한 RB트리처럼 몇 가지 규칙이 있다.

1. 모든 데이터는 리프 노드에 저장된다: 이로 인해 순차 탐색이 용이하다.
2. 내부 노드는 데이터가 아닌 키를 저장한다: 이 키들은 리프 노드에 있는 데이터를 가리키는 포인터 역할을 한다.
3. 리프 노드는 서로 연결리스트로 연결되어 있다: 이는 범위 검색을 효율적으로 만든다.
4. 균형 트리이다: 모든 리프 노드는 같은 레벨에 위치한다. 따라서 탐색 시간이 일정하다.
5. 분할과 병합을 통한 동적 조정이 가능하다: 삽입이나 삭제로 인해 노드의 크기가 최대 또는 최소를 초과하면, 자동으로 분할 또는 병합이 이루어진다.

B+트리는 노드의 최대 차수(또는 분기)를 M이라 할 때, 

• 각 내부 노드는 최대 M-1개의 키를 가질 수 있으며, 최소 ceil(M/2)-1개의 키를 가져야 한다. (단, 루트 노드는 이 조건에서 예외일 수 있다.)
• 각 리프 노드는 최대 M개의 데이터를 가질 수 있으며, 최소 ceil(M/2)개의 데이터를 가져야 한다.

https://www.cs.usfca.edu/~galles/visualization/Trie.html

Trie Visualization

 

Trie는 검색 트리의 일종으로, 문자열의 집합을 저장하는데 특화된 자료구조이다. 주로 사전과 같은 문자열을 빠르게 검색하고, 추가하고, 삭제하는 데 사용된다. Trie의 각 노드는 문자열의 한 문자를 나타내며, 루트에서부터 특정 노드까지의 경로는 그 노드에 도달하기 위한 문자열의 접두사를 형성한다.

루트 노드: Trie의 시작점. 보통 비어있거나, 특정 기준으로 시작 문자를 가질 수 있다.

 

자식 노드: 각 노드는 0개 이상의 자식을 가질 수 있으며, 각 자식 노드는 알파벳이나 문자열 내의 다음 문자를 나타낸다.

 

마지막 노드: 문자열의 끝을 나타내는 특별한 표시(예: * 또는 특정 플래그)를 갖는 노드. 이를 통해 문자열의 존재 여부를 판별할 수 있다.

 

문자열을 검색할 때, 길이가 n인 문자열에 대해 최악의 경우 시간 복잡도는 O(n)이다. 하지만 실제로는 저장된 문자열의 수보다 검색할 문자열의 길이에 더 의존적이므로, 매우 효율적이다. 그리고, Trie는 접두사를 공유하는 문자열들을 효율적으로 관리할 수 있어, 자동 완성과 같은 기능 구현에 적합하다.

 

문자와 노드 매핑을 위해 추가적인 메모리 공간이 필요하며, 특히 문자의 종류가 많은 경우(예: 유니코드 문자열) 메모리 사용량이 많아질 수 있으므로 주의해야 한다.

 

Trie는 문자열 검색, 자동 완성, 사전 추천 시스템, IP 라우팅 등 다양한 분야에서 활용된다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

# Trie 사용 예제
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # True를 출력
print(trie.search("app"))    # False를 출력, "app"은 단어의 끝이 아님

trie.insert("app")
print(trie.search("app"))    # True를 출력, "app"이 삽입되었기 때문

 

1. TrieNode 클래스는 Trie의 각 노드를 나타내며, 자식 노드들을 딕셔너리(children)로 관리하고, 단어의 끝을 나타내는 플래그(is_end_of_word)를 갖는다.
2. Trie 클래스는 Trie 자체를 나타내며, 루트 노드(root)를 가지고 있고, 단어를 삽입(insert)하고 검색(search)하는 메서드를 제공한다.
3. insert 메서드는 주어진 단어를 한 글자씩 Trie에 삽입한다. 해당 글자의 노드가 존재하지 않으면 새 노드를 생성한다.
4. search 메서드는 주어진 단어를 Trie에서 찾는다. 단어의 모든 글자가 순서대로 Trie에 존재하고, 마지막 글자가 단어의 끝을 나타내는 노드면 True를, 그렇지 않으면 False를 반환한다.

Minimum Spanning Tree(MST, 최소 신장 트리)는 가중치가 있는 그래프에서 만들 수 있는 신장 트리 중에서 가중치의 합이 최소인 트리를 말한다. 신장 트리란, 원래의 그래프의 모든 정점을 포함하며 사이클이 없는 연결 부분 그래프이다. MST는 네트워크 설계, 클러스터 분석, 그래프 분석 등 다양한 분야에서 응용된다.

 

Kruskal의 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 방식으로 간선을 선택한다. 이 과정에서 분리 집합 자료구조(Disjoint Set)를 사용하여 효율적으로 사이클을 확인한다.

 

Prim의 알고리즘은 시작 정점을 선택한 후, 트리에 인접한 간선 중에서 최소 가중치를 가진 간선을 선택하여 트리를 확장한다. 이 과정은 모든 정점이 트리에 포함될 때까지 반복한다.

 

Kruskal 알고리즘을 구현하기 위해 분리 집합(Disjoint Set) 자료구조를 사용하는 것이 일반적이다. 이는 각 정점을 자신만을 포함하는 집합으로 초기화하고, 간선을 하나씩 확인하면서 두 정점이 서로 다른 집합에 속해 있다면(즉, 사이클을 형성하지 않으면) 두 집합을 합치는 방식으로 작동한다.

 

Krulskal 알고리즘 구현 방법은

1. 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 간선을 순회하며, 현재 선택한 간선이 사이클을 형성하지 않으면 신장 트리에 포함시킨다.
3. 모든 정점이 연결될 때까지 2번을 반복한다.

class DisjointSet:
    def __init__(self, vertices):
        self.vertices = vertices
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            return self.find(self.parent[item])

    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)
        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

def kruskal(graph):
    vertices, edges = graph
    disjoint_set = DisjointSet(vertices)
    mst = []
    edges.sort(key=lambda edge: edge[2])  # 간선을 가중치에 따라 오름차순으로 정렬

    for edge in edges:
        v1, v2, weight = edge
        if disjoint_set.find(v1) != disjoint_set.find(v2):
            disjoint_set.union(v1, v2)
            mst.append(edge)

    return mst

# 그래프 정의: (정점 리스트, 간선 리스트)
graph = (['A', 'B', 'C', 'D', 'E', 'F'], 
         [('A', 'B', 2), ('A', 'C', 3), ('B', 'C', 1), 
          ('B', 'D', 4), ('C', 'E', 6), ('D', 'E', 5),
          ('E', 'F', 2), ('D', 'F', 7)])

# Kruskal 알고리즘 실행
mst = kruskal(graph)
print("Minimum Spanning Tree:", mst)

1. DisjointSet 클래스는 각 정점의 부모를 저장하고, 두 정점이 같은 집합에 속하는지 확인하고, 두 집합을 합치는 기능을 제공한다.
2. kruskal 함수는 주어진 그래프에서 MST를 찾아 반환한다. 먼저 모든 간선을 가중치 기준으로 정렬하고, 사이클을 형성하지 않는 간선만 선택하여 MST를 구성한다.

Prim 알고리즘을 파이썬으로 구현할 때, 우선순위 큐를 사용하여 트리에 인접한 간선 중 최소 가중치를 가진 간선을 효율적으로 찾을 수 있다.

 

Prim 알고리즘 구현 방법은

1. 임의의 정점을 선택하여 시작한다.
2. 선택된 정점과 인접한 간선 중 가장 가중치가 낮은 간선을 선택하고, 해당 간선이 연결하는 정점을 트리에 추가한다.
3. 모든 정점이 트리에 포함될 때까지 2번을 반복한다.

import heapq

def prim(graph, start_vertex):
    visited = set([start_vertex])
    edges = [(cost, start_vertex, to) for to, cost in graph[start_vertex].items()]
    heapq.heapify(edges)
    mst = []

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst

# 그래프 정의: 각 정점에서 다른 정점으로의 가중치가 있는 엣지를 딕셔너리로 표현
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 4, 'E': 2},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 4, 'E': 3},
    'E': {'B': 2, 'D': 3, 'F': 3},
    'F': {'C': 5, 'E': 3},
}

# Prim 알고리즘을 이용해 최소 신장 트리(MST) 찾기
mst = prim(graph, 'A')
print("Minimum Spanning Tree:", mst)

 

1. 시작 정점을 선택하고 방문한 정점 집합에 추가한다.
2. 시작 정점에 인접한 간선을 우선순위 큐에 추가한다.
3. 우선순위 큐에서 가중치가 가장 낮은 간선을 추출한다. 이 간선이 연결하는 정점이 이미 방문한 정점 집합에 속하지 않는다면, 이 간선을 최소 신장 트리에 추가하고, 해당 정점을 방문한 정점 집합에 추가한다.
4. 새롭게 추가된 정점에 인접한 간선 중 아직 방문하지 않은 정점으로의 간선을 우선순위 큐에 추가한다.
5. 모든 정점이 방문될 때까지 3번과 4번 과정을 반복한다.

MST 알고리즘의 선택은 그래프의 특성(간선의 수, 그래프의 밀집도 등)에 따라 달라질 수 있다. 예를 들어, 간선의 수가 많이 밀집된 그래프에서는 Prim의 알고리즘이, 간선의 수가 상대적으로 적은 그래프에서는 Kruskal의 알고리즘이 더 효율적일 수 있다.