the-ze

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

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+트리는 데이터베이스와 파일 시스템에서 사용되는 인덱스 메커니즘의 일종이다. 이는 탐색, 삽입, 삭제, 순회 등의 동작을 로그 시간 내에 수행할 수 있는 이진 검색 트리의 확장된 형태로, 디스크 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는 검색 트리의 일종으로, 문자열의 집합을 저장하는데 특화된 자료구조이다. 주로 사전과 같은 문자열을 빠르게 검색하고, 추가하고, 삭제하는 데 사용된다. 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의 알고리즘이 더 효율적일 수 있다.

그래프(Graph)는 데이터의 집합을 정점(Vertex)과 이들 정점을 연결하는 간선(Edge)의 집합으로 표현한 자료구조다. 그래프는 다양한 종류가 있으며, 주요 분류 기준에는 방향성 여부와 가중치 존재 여부가 있다.

무방향 그래프(Undirected Graph)에서 간선은 방향성이 없어, 두 정점을 서로 연결만 시킨다는 의미를 가진다. 예를 들어, 정점 A와 B를 연결하는 간선은 "A에서 B로" 또는 "B에서 A로"의 구분 없이 양방향 모두를 의미한다. 서로간의 연결이 대칭적인 관계, 예를 들어 소셜 네트워크의 친구 관계, 도로망 등에서 사용된다.

방향 그래프(Directed Graph)에서 간선은 방향성을 가지며, "A에서 B로" 혹은 그 반대로의 명확한 방향이 존재한다. 이는 간선이 (A, B)로 표시될 때, A에서 B로의 한 방향 연결만을 의미한다. 방향이 중요한 관계를 모델링할 때 사용되며, 예로는 웹 페이지 간의 링크, 트위터의 팔로우 등이 있다.

가중치 그래프(Weighted Graph)에서 각 간선에는 가중치가 할당되어 있다. 이 가중치는 거리, 시간, 비용 등 간선을 통해 연결된 두 정점 사이의 관계의 "가중치"를 나타낸다. 가중치는 간선을 따라 이동하는 데 드는 비용이나 거리 등을 표현할 때 사용된다. 예를 들어, 도시 간의 이동 비용, 네트워크 상에서의 데이터 전송 시간 등을 모델링할 때 사용된다.

인접 행렬(Adjacency Matrix)은 그래프를 표현하는 방법 중 하나로, 그래프의 정점들 간의 연결 관계를 행렬로 나타낸 것이다. 이 방식은 그래프의 각 정점을 행렬의 행과 열에 대응시키고, 두 정점 사이에 간선이 존재하면 해당 위치의 행렬 값에 1(또는 가중치 값)을, 없으면 0을 저장한다.

V개의 정점을 가진 그래프는 V×V 크기의 행렬로 표현된다. 비방향 그래프의 경우, 인접 행렬은 대칭 행렬이 된다. 가중치가 있는 그래프의 경우, 1 대신 간선의 가중치 값을 행렬에 저장한다. 간선이 없는 경우 일반적으로 매우 큰 값(무한대를 의미하는 값)이나 -1을 사용하여 표현할 수 있다.

대각선 요소는 보통 0으로 설정된다, 자기 자신으로의 연결이 없다는 것을 의미한다. 하지만 특별한 경우(예를 들어, 루프를 허용하는 그래프)에는 다른 값을 가질 수도 있다.

그래프의 연결 관계를 간단하고 직관적으로 표현할 수 있고, 특정 두 정점 사이의 연결 여부를 O(1) 시간에 확인할 수 있다. 하지만 정점의 수에 따라 필요한 메모리 공간이 제곱으로 증가하기 때문에, 희소 그래프(Sparse Graph)에서는 메모리 낭비가 심할 수 있고, 간선의 수에 비례하지 않고, 정점의 수의 제곱에 비례하여 메모리 공간을 사용한다.

class Graph:
    def __init__(self, size):
        self.adjMatrix = [[0 for _ in range(size)] for _ in range(size)]
        self.size = size
    
    def add_edge(self, v1, v2):
        if v1 == v2:
            print("같은 정점은 연결할 수 없습니다.")
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1  # 무방향 그래프의 경우

    def remove_edge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("연결된 간선이 없습니다.")
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0  # 무방향 그래프의 경우
    
    def __str__(self):
        return '\n'.join([' '.join([str(i) for i in row]) for row in self.adjMatrix])

# 그래프 생성 및 간선 추가 예시
graph = Graph(4)  # 4개의 정점을 가진 그래프
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

print(graph)

인접 리스트(Adjacency List)는 그래프를 표현하는 자료구조 중 하나로, 각 정점에 인접한 정점들을 연결 리스트로 나열하여 그래프의 연결 관계를 표현한다. 인접 리스트는 각 정점마다 해당 정점으로부터 나가는 간선의 목록을 저장한다. 이 방법은 특히 희소 그래프(Sparse Graph), 즉 정점들 사이의 간선이 상대적으로 적은 그래프를 표현하는 데 효율적이다.

각 정점마다 하나의 리스트를 갖고, 해당 리스트에는 그 정점에 인접한 모든 정점들이 포함된다. Python에서는 리스트의 리스트로 구현하거나, 리스트에 연결 리스트 또는 집합을 담아 구현할 수 있다. 가중치가 있는 그래프의 경우, (인접 정점, 가중치) 형태의 튜플을 리스트에 저장함으로써 간선의 가중치 정보를 함께 저장할 수 있다.

방향 그래프(Directed Graph)의 경우, 각 리스트에는 해당 정점에서 출발하는 간선의 정보만 저장한다. 비방향 그래프(Undirected Graph)에서는 두 정점 사이의 연결을 양쪽 정점의 리스트에 모두 표현한다.

실제로 연결된 간선의 정보만을 저장하기 때문에, 인접 행렬에 비해 메모리 사용이 효율적이다. 특히 간선의 수가 정점의 수보다 많지 않은 희소 그래프에서 유리하고 그래프의 정점이나 간선이 자주 추가되거나 삭제되는 동적인 상황에 유연하게 대응할 수 있다.

인접 리스트에서는 특정 두 정점 사이에 간선이 존재하는지 확인하기 위해 해당 정점의 리스트를 순회해야 하므로, 최악의 경우 O(V)의 시간이 소요될 수 있다.(V는 정점의 수)

class Graph:
    def __init__(self, numVertices):
        self.numVertices = numVertices
        self.adjList = [[] for _ in range(numVertices)]
    
    def add_edge(self, src, dest):
        self.adjList[src].append(dest)
        # 비방향 그래프의 경우, 아래 코드를 추가한다.
        # self.adjList[dest].append(src)
    
    def remove_edge(self, src, dest):
        if dest in self.adjList[src]:
            self.adjList[src].remove(dest)
            # 비방향 그래프의 경우, 아래 코드를 추가한다.
            # self.adjList[dest].remove(src)
    
    def print_graph(self):
        for i in range(self.numVertices):
            print(f"Vertex {i}: {self.adjList[i]}")

# 그래프 생성 및 간선 추가 예시
graph = Graph(4)  # 4개의 정점을 가진 그래프
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

graph.print_graph()

해싱(Hashing)은 데이터 관리를 위한 중요한 기법 중 하나이다. 해싱은 어떤 입력값을 고정된 길이의 값으로 변환하는 과정을 말하며, 이 때 사용되는 함수를 해시 함수라 한다. 해시 함수는 다양한 길이의 입력을 받아서 고정된 길이의 해시값을 출력한다. 이 해시값은 데이터의 저장 위치를 결정하는 데 사용된다.

해시 테이블(Hash Table)은 해싱 기법을 사용하여 데이터를 저장하는 자료구조이다. 각 데이터는 해시 함수를 통해 계산된 해시값에 따라 해시 테이블 내의 특정 위치에 저장된다. 해시 테이블은 키-값 쌍으로 데이터를 저장하며, 이때 키를 해시 함수에 입력하여 그 결과로 나온 해시값을 사용하여 값을 저장하거나 검색한다.

해시 테이블의 주요 장점은 데이터의 추가, 삭제, 검색 작업을 평균적으로 상수 시간(O(1)) 내에 수행할 수 있다는 점이다. 하지만 최악의 경우(모든 키가 동일한 위치에 해시되는 경우)에는 모든 데이터를 검색해야 하므로 성능이 크게 저하될 수 있다.

Python의 dict, Java의 HashMap 같은 프로그래밍 언어의 내장 자료구조도 내부적으로 해시 테이블을 사용한다. Python에서는 hash() 함수를 사용하여 객체의 해시값을 얻을 수 있다. 이 함수는 내장 데이터 타입(예: 정수, 문자열)에 대해 해시값을 반환한다. 하지만 사용자 정의 객체의 경우, 객체가 해시 가능하도록 __hash__() 메소드를 구현해야 한다.

또한, Python의 dict 타입은 내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장한다. 이를 통해 키에 대한 빠른 접근과 검색, 추가, 삭제 작업을 지원한다.

# 정수의 해시값
hash_value = hash(100)
print(hash_value)

# 문자열의 해시값
hash_value = hash("Hello, World!")
print(hash_value)

class Student:
    def __init__(self, id, name):
        self.id = id
        self.name = name

    # 객체가 해시 가능하도록 __hash__ 메소드 구현
    def __hash__(self):
        return hash((self.id, self.name))

    # __eq__ 메소드도 구현하여 객체의 동등성 비교 가능하게 함
    def __eq__(self, other):
        return self.id == other.id and self.name == other.name

# 사용자 정의 객체 생성
student = Student(1, "John Doe")

# 사용자 정의 객체의 해시값
print(hash(student))

__hash__() 메소드는 객체의 해시값을 계산하여 반환하며, __eq__() 메소드는 두 객체의 동등성을 비교한다. Python에서는 두 객체가 동등하다고 판단되면, 이들의 해시값도 동일해야 한다.

해시 충돌(Collision)은 두 개 이상의 키가 해시 함수를 통해 동일한 해시값(즉, 동일한 위치)을 가리키는 경우 발생하는 현상이다. 해시 테이블의 효율성을 저하시키며, 이를 효과적으로 처리하는 것이 해시 테이블 설계의 핵심적인 부분이다. 충돌이 발생했을 때 체이닝과 재해싱은 이를 해결하기 위한 두 가지 주요 방법이다.

체이닝(Chaining)은 충돌이 발생했을 때 같은 해시값을 가진 요소들을 연결 리스트와 같은 자료구조를 사용하여 연결하는 방식이다. 이렇게 하면 한 버킷에 여러 요소가 저장될 수 있으며, 충돌로 인한 문제를 효율적으로 해결할 수 있다. 체이닝 방식의 장점은 해시 테이블의 크기와 무관하게 충돌을 관리할 수 있다는 점이며, 구현이 비교적 간단하다는 것도 장점이다. 다만, 체인이 길어지면 검색 성능이 저하될 수 있다.

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash_function(self, key):
        return key % self.size
    
    def insert(self, key, value):
        hash_index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[hash_index]):
            if k == key:
                self.table[hash_index][i] = (key, value)
                return
        self.table[hash_index].append((key, value))
    
    def search(self, key):
        hash_index = self.hash_function(key)
        for k, v in self.table[hash_index]:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        hash_index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[hash_index]):
            if k == key:
                del self.table[hash_index][i]
                return True
        return False

재해싱(rehashing)은 해시 테이블의 크기를 조정하고, 모든 요소를 새로운 크기에 맞는 해시 함수를 사용하여 재배치하는 방법이다. 주로 해시 테이블의 사용률(로드 팩터)이 높아져 성능 저하가 예상될 때 사용된다. 재해싱은 충돌의 가능성을 줄이고, 해시 테이블의 성능을 유지하는 데 도움이 된다. 재해싱 과정은 모든 요소를 새로운 해시 테이블로 이동시켜야 하므로, 리소스와 시간이 많이 소모되는 작업이다. 그래서, 재해싱은 해시 테이블의 성능을 개선하기 위해 필요할 때만 수행되어야 한다.

class HashTableRehashing:
    def __init__(self, size=10):
        self.size = size
        self.count = 0
        self.table = [None] * size
    
    def hash_function(self, key):
        return key % self.size
    
    def rehash(self, key, step=1):
        return (key + step) % self.size
    
    def resize_and_rehash_all(self):
        old_table = self.table[:]
        self.size *= 2
        self.table = [None] * self.size
        self.count = 0
        for item in old_table:
            if item:
                key, value = item
                self.insert(key, value)
    
    def insert(self, key, value):
        if self.count / self.size >= 0.7:  # Load factor threshold
            self.resize_and_rehash_all()
        
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                self.table[hash_index] = (key, value)
                return
            hash_index = self.rehash(hash_index, step)
            step += 1
        
        self.table[hash_index] = (key, value)
        self.count += 1
    
    def search(self, key):
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                return self.table[hash_index][1]
            hash_index = self.rehash(hash_index, step)
            step += 1
        return None
    
    def delete(self, key):
        hash_index = self.hash_function(key)
        step = 1
        while self.table[hash_index] is not None:
            if self.table[hash_index][0] == key:
                self.table[hash_index] = None
                self.count -= 1
                return True
            hash_index = self.rehash(hash_index, step)
            step += 1
        return False

위 코드에선 해시 테이블이 일정 수준으로 채워지면(load factor >= 0.7), 해시 테이블의 크기를 늘리고 모든 요소를 새로운 크기에 맞게 재해싱하여 충돌 가능성을 줄인다.

Array(배열)은 컴퓨터 과학에서 기본적인 자료 구조 중 하나로, 동일한 자료형의 요소들을 순서대로 나열한 것이다. 배열은 연속적인 메모리 위치에 데이터 요소들을 저장하여, 인덱스를 통해 각 요소에 빠르게 접근할 수 있는 장점을 가진다.

대부분의 프로그래밍 언어에서 배열을 생성할 때 그 크기가 고정되며, 나중에 크기를 변경할 수 없다. 모든 배열 요소는 같은 자료형이어야 한다. 이로 인해 메모리 관리가 용이하고, 요소 접근 시간이 단축된다. 배열의 요소는 0부터 시작하는 인덱스를 사용하여 접근할 수 있다. 인덱스를 통한 접근은 O(1)의 시간 복잡도를 가진다.

인덱스를 사용하여 배열의 어떤 위치에도 즉시 접근할 수 있고 연속적인 메모리 할당 덕분에 메모리 사용이 효율적이다.

배열을 생성할 때 크기를 정해야 하며, 크기를 동적으로 변경하는 것이 어렵다. 그리고  배열 중간에 요소를 삽입하거나 삭제할 경우, 나머지 요소들을 이동해야 하므로 비효율적이다.

간단한 리스트 데이터를 다룰 때 유용하며, 크기가 고정되어 있고, 자주 변경되지 않는 데이터 집합에 적합하다. 수학적 계산이나 고정된 데이터 집합을 다루는 알고리즘에서 주로 사용된다.

# 배열(리스트) 생성
numbers = [1, 2, 3, 4, 5]

# 배열 요소에 접근
print(numbers[0])  # 첫 번째 요소 출력, 결과: 1

# 배열 요소 수정
numbers[2] = 10  # 세 번째 요소를 10으로 변경
print(numbers)  # 결과: [1, 2, 10, 4, 5]

# 배열에 요소 추가
numbers.append(6)  # 배열의 끝에 6 추가
print(numbers)  # 결과: [1, 2, 10, 4, 5, 6]

# 배열의 특정 위치에 요소 추가
numbers.insert(1, 20)  # 두 번째 위치에 20 추가
print(numbers)  # 결과: [1, 20, 2, 10, 4, 5, 6]

# 배열의 요소 삭제
del numbers[1]  # 두 번째 요소 삭제
print(numbers)  # 결과: [1, 2, 10, 4, 5, 6]

# 배열의 길이 확인
print(len(numbers))  # 결과: 6

# 배열을 순회하며 요소 출력
for number in numbers:
    print(number)

Linked List(연결 리스트)는 선형 자료 구조의 일종으로, 데이터 요소들이 노드 형태로 저장되며 각 노드는 다음 노드를 가리키는 포인터(또는 참조)를 포함한다. 연결 리스트는 배열과 비교했을 때, 동적으로 메모리를 할당하며 요소의 추가와 삭제가 유연하게 이루어진다는 특징을 가진다.

노드(Node)는 데이터와 다음 노드를 가리키는 포인터로 구성된다. 마지막 노드는 다음 노드가 없음을 나타내기 위해 보통 null을 포인터 값으로 갖는다.

헤드(Head)는 리스트의 첫 번째 노드를 가리키는 포인터이다. 리스트의 시작점 역할을 한다.

단일 연결 리스트(Singly Linked List)는 각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트다.

이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드와 다음 노드 양쪽을 가리킨다. 양방향 탐색이 가능하다.

원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키는 형태로, 리스트의 끝과 시작이 연결된다.

배열과 달리 미리 크기를 지정할 필요가 없으며, 요소의 추가와 삭제 시 리스트의 크기가 동적으로 조절되고  필요할 때마다 메모리 공간을 할당받아 사용하기 때문에, 사용하지 않는 메모리 공간이 생기지 않는다. 포인터만 변경하면 되기 때문에, 배열에 비해 훨씬 효율적으로 데이터의 삽입과 삭제가 이루어진다.

배열처럼 인덱스를 통한 직접 접근이 불가능하며, 특정 요소에 접근하기 위해서는 헤드부터 순차적으로 탐색해야 한다. 그리고 각 노드가 데이터 외에도 포인터를 저장해야 하므로, 추가적인 메모리 공간이 필요하다.

연결 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하거나, 데이터의 크기를 미리 예측하기 어려운 경우에 유용하게 사용된다. 예를 들어, 운영체제에서 프로세스 관리, 메모리 관리 등에 연결 리스트가 활용된다.

class Node:
    def __init__(self, data):
        self.data = data  # 노드가 저장할 데이터
        self.next = None  # 다음 노드를 가리키는 포인터

class LinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리키는 헤드

    def append(self, data):
        #리스트의 끝에 새로운 노드를 추가한다.
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        #리스트의 모든 요소를 출력한다.
        cur_node = self.head
        while cur_node:
            print(cur_node.data, end=" -> ")
            cur_node = cur_node.next
        print("None")

# 연결 리스트 사용 예시
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)

llist.print_list()
# 출력: 1 -> 2 -> 3 -> None

C로 Linked List 구현 코드

이진 탐색 트리, AVL 트리

레드 블랙 트리 시뮬레이터

레드 블랙 트리는 이진 탐색트리의 한 종류로써, 스스로 균형을 잡는 트리이다. BST의 worst case의 단점 O(N)을 개선했다. 이 레드 블랙 트리에는 몇 가지 규칙들이 있다.

1. 모든 노드는 red 혹은 black

2. 최상위 루트 노드는 black

3. 모든 nil(leaf) 노드는 black

4. red의 자녀들은 black (red가 연속적으로 존재할 수 없다.)

5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)

여기서 nil 노드란?

1. 존재하지 않음을 의미하는 노드

2. 자녀가 없을 때 자녀를 nil 노드로 표기 (nil이 있다면 자녀가 없는 것을 의미)

3. 값이 있는 노드와 동등하게 취급

4. RB트리에서 leaf노드는 nil 노드

5. 모든 nli 노드는 black

RB 트리가 위 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 속성은 여전히 만족한다.

RB트리는 주로 삽입/삭제할 때 균형을 맞춘다.

red의 자녀들은 black , red가 연속적으로 존재할 수 없다.

임의의 노드에서 자손 nil노드들까지 가는 경로들의 black의 수는 같다.

​

이 둘을 위반하며 이들을 해결하려고 구조들 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

삽입 방식

​

1. 삽입 전 RB트리 속성 만족한 상태

2. 삽입 방식은 일반적인 BST와 동일

3. 삽입 후 RB트리 위반 여부 확인

4. RB트리 속성을 위반했다면 재조정

5. RB트리 속성을 다시 만족

삽입하는 노드의 색깔은 항상 red이다.

node_t *rbtree_insert(rbtree *t, const key_t key)
{
  // TODO: implement insert
  // 적절한 위치 찾는 코드
  // 값 삽입
  node_t *SENTINEL_NODE = t->nil;
  node_t *parent_node = t->nil;

  node_t *new_node = malloc(sizeof(node_t));
  new_node->key = key;
  new_node->right = SENTINEL_NODE;
  new_node->left = SENTINEL_NODE;
  new_node->color = RBTREE_RED;

  node_t *cur_node = t->root;
  while (cur_node != SENTINEL_NODE)
  {
    parent_node = cur_node;
    if (cur_node->key > key)
    {
      cur_node = cur_node->left;
    }
    else
    {
      cur_node = cur_node->right;
    }
  }
  new_node->parent = parent_node;

  if (parent_node == SENTINEL_NODE)
  {
    t->root = new_node;
  }
  else if (new_node->key < parent_node->key)
  {
    parent_node->left = new_node;
  }
  else
  {
    parent_node->right = new_node;
  }

  rbtree_insert_fixup(t, new_node);
  return new_node;
}

일반적인 삽입만 했다면, 맨 위의 5가지 규칙이 깨지지 때문에 이를 규칙에 맞게 다시 재조정할 필요가 있다.

위의 시뮬레이터로 계속 삽입을 하면 보이다 싶이, 결국 black 노드가 많아지는 것을 볼 수가 있다.

위 사진에서 insert(25)를 해보자.

그럼 30의 좌측 자식 red노드로 처음엔 삽입될 것 이다. 이는 5가지 규칙 중 노드가 red라면 자녀들은 black을 위반한 상태이다. 부모와 삼촌을 black으로, 할아버지는 red로 변경하고 할아버지인 35에서 확인해보자 50 > 35가 레드가 되니 노드가 red라면 자녀들은 black을 위반한 상태이다. 그러면 50을 기준으로 오른쪽으로 회전해보자

그러면 또 35와 50을 보면 문제가 생기는데, 20과 35의 색깔을 바꿔주고 20을 기준으로 왼쪽으로 회전하면 된다.

구현할 때, 이런 재조정에 신경을 쓰며 구현을 해야한다.

void rbtree_insert_fixup(rbtree *t, node_t *p)
{
  while (p->parent->color == RBTREE_RED)
  {
    if (p->parent == p->parent->parent->left)
    {
      node_t *y = p->parent->parent->right;
      if (y->color == RBTREE_RED)
      {
        p->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        p = p->parent->parent;
      }
      else
      {
        if (p == p->parent->right)
        {
          p = p->parent;
          left_rotate(t, p);
        }
        p->parent->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        right_rotate(t, p->parent->parent);
      }
    }
    else
    {
      node_t *y = p->parent->parent->left;
      if (y->color == RBTREE_RED)
      {
        p->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        p = p->parent->parent;
      }
      else
      {
        if (p == p->parent->left)
        {
          p = p->parent;
          right_rotate(t, p);
        }
        p->parent->color = RBTREE_BLACK;
        p->parent->parent->color = RBTREE_RED;
        left_rotate(t, p->parent->parent);
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

삭제하려는 노드의 *자녀가 없거나 하나라면 삭제되는 색 = 삭제되는 노드의 색

삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor

삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.

int rbtree_erase(rbtree *t, node_t *p)
{
  node_t *target_node = p;
  node_t *x;
  color_t target_node_orginal_color = target_node->color;
  if (p->left == t->nil)
  {
    x = p->right;
    rbtree_erase_transplant(t, p, p->right);
  }
  else if (p->right == t->nil)
  {
    x = p->left;
    rbtree_erase_transplant(t, p, p->left);
  }
  else
  {
    target_node = node_min(p->right, t->nil);
    target_node_orginal_color = target_node->color;
    x = target_node->right;
    if (target_node->parent == p)
    {
      x->parent = target_node;
    }
    else
    {
      rbtree_erase_transplant(t, target_node, target_node->right);
      target_node->right = p->right;
      target_node->right->parent = target_node;
    }
    rbtree_erase_transplant(t, p, target_node);
    target_node->left = p->left;
    target_node->left->parent = target_node;
    target_node->color = p->color;
  }
  if (target_node_orginal_color == RBTREE_BLACK)
    rbtree_erase_fixup(t, x);
  free(p);
  return 0;
}

10을 삭제시키면 임의의 노드에서 그 노드의 자손 nil노드들까지 가는 경로들의 black 수는 같다를 위반한다.

삭제된 10에 extra black을 부여해야한다. 근데 삭제하고 넣을 때 그 사이에 nil노드가 생겨버리기 때문에, 블랙이 두개가 생겨버린다. 이를 doubly black이라고 한다.

rb tree의 삭제는 해당 노드를 삭제하고 extra black을 부여 후, doubly black만 잘 해결하면 된다. 이를 해결하는 방법에는 4가지 case가 있다.

1. doubly black의 오른쪽 형제가 black이고, 그 형제의 오른쪽 자녀가 red일 때

2. doubly black의 오른쪽 형제가 black이고, 그 형제의 왼쪽 자녀가 red일 때

3. doubly black의 오른쪽 형제가 black이고, 그 형제의 두 자녀가 모두 black 일 때

4. doubly black의 오른쪽 형제가 red일 때

(위 모든 케이스 오른쪽, 왼쪽을 바꾼 상황이여도 적합함)

이 케이스들에 유의하며 코드를 짜야한다.

void rbtree_erase_fixup(rbtree *t, node_t *fixup_start_node)
{
  node_t *cur_node = fixup_start_node;
  node_t *sibling;
  while (cur_node != t->root && cur_node->color == RBTREE_BLACK)
  {
    if (cur_node == cur_node->parent->left)
    {
      sibling = cur_node->parent->right;

      if (sibling->color == RBTREE_RED)
      {
        sibling->color = RBTREE_BLACK;
        cur_node->parent->color = RBTREE_RED;
        left_rotate(t, cur_node->parent);
        sibling = cur_node->parent->right;
      }

      if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK)
      {
        sibling->color = RBTREE_RED;
        cur_node = cur_node->parent;
      }

      else {
        if (sibling->right->color == RBTREE_BLACK)
        {
          sibling->left->color = RBTREE_BLACK;
          sibling->color = RBTREE_RED;
          right_rotate(t, sibling);
          sibling = cur_node->parent->right;
        }
        sibling->color = cur_node->parent->color;
        cur_node->parent->color = RBTREE_BLACK;
        sibling->right->color = RBTREE_BLACK;
        left_rotate(t, cur_node->parent);
        cur_node = t->root;
      }
    }
    else {
      sibling = cur_node->parent->left;
      if (sibling->color == RBTREE_RED)
      {
        sibling->color = RBTREE_BLACK;
        cur_node->parent->color = RBTREE_RED;
        right_rotate(t, cur_node->parent);
        sibling = cur_node->parent->left;
      }
      if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK)
      {
        sibling->color = RBTREE_RED;
        cur_node = cur_node->parent;
      }
      else
      {
        if (sibling->left->color == RBTREE_BLACK)
        {
          sibling->right->color = RBTREE_BLACK;
          sibling->color = RBTREE_RED;
          left_rotate(t, sibling);
          sibling = cur_node->parent->left;
        }
        sibling->color = cur_node->parent->color;
        cur_node->parent->color = RBTREE_BLACK;
        sibling->left->color = RBTREE_BLACK;
        right_rotate(t, cur_node->parent);
        cur_node = t->root;
      }
    }
  }
  cur_node->color = RBTREE_BLACK;
}

위 코드는 URL sejin branch에 있음

참고한 유튜브

이진탐색트리는 binary search와 linked list를 결합한 자료구조이다. 이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다.

이진탐색의 경우 탐색에 소요되는 계산 복잡성은 O(logN)으로 빠르지만 자료 입력, 삭제가 불가능하다. 연결 리스트의 경우에는 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만, 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다.

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

​

이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 쓴다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회) 중위순회 방식을 사용하면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다. (1,5,6,10,14,17,21)

​

이진탐색트리의 핵심 연산은 검색, 삽입, 삭제 세 가지이다. 이밖에 이진탐색트리 생성, 이진탐색트리 삭제, 해당 이진탐색트리가 비어 있는지 확인, 트리순회 등의 연산이 있다.

​

탐색(검색)

이진탐색트리의 탐색 연산에 소요되는 계산복잡성은 트리의 높이(루트노드-잎새노드에 이르는 엣지 수의 최대값)가 h일 때 O(h)가 된다.

​

삽입

트리가 매우 적으면 그냥 중간에 삽입하면 되는데, 매우 길어질 때를 방지하기 위하여, 새로운 삽입은 무조건 리프노드에서 이루어지게된다. 삽입 연산에 소요되는 계산복잡성 역시 트리의 높이가 h일 때 O(h)이다. 삽입할 위치의 리프노드까지 찾아 내려가는 데 h번 비교를 해야 하기 때문이다.

​

삭제할 때의 경우

1. 자식노드가 없는 경우 - 그냥 삭제하면 된다.
2. 자식노드가 하나 있는 경우 - 본인을 삭제하고 부모와 자식을 연결하면 된다.
3. 자식노드가 두 개 있는 경우 - 아래 과정을 따른다.

자식노드가 두 개 있을 때 삭제 과정

1. 삭제 대상 노드의 오른쪽 서브트리를 찾는다.
2. successor 노드를 찾는다.
3. 2에서 찾은 successor의 값을 삭제 대상 노드에 복사한다.
4. successor 노드를 삭제한다.

successor란? 중위 순회를 나열한 배열에서 본인의 바로 다음에 있는 노드이다. 즉 본인보다 오른쪽에 있으면서, 가장 작은 노드이다. (맨위 사진에서 [1,5,6,10,14,17,21] 여기서 10의 successor는 14이다.)

17 우측에 있는 노드 중에 가장 작은 19가 successor이다.

트리의 높이가 h이고 삭제 대상 노드의 레벨이 n라고 가정할 때, 1번 과정에서는 n번의 비교 연산이 필요하다. 2번 successor 노드를 찾기 위해서는 삭제 대상 노드의 서브트리 높이(h-d)에 해당하는 비교 연산을 수행해야 한다. 3번 4번은 복사하고 삭제하는 과정으로 상수시간이 걸려 무시할 만 하다. 종합적으로 따지면 O(d+h-d), 즉 O(h)가 된다.

​

노드가 루트의 한쪽으로 쏠려버리면 균형이 안맞아서 비효율적이다. 그러면 O(n)이 되는데 이를 해결하기 위해 균형을 맞추는 AVL Tree가 고안되었다.

AVL 트리는 편향된 트리의 균형을 맞추기 위한 트리이다.

• 이진 탐색 트리의 속성을 가진다.
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
• 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
• 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수)

​

회전 과정에 대해 알아보기 전에 알아야 할 것이있다. AVL트리는 균형이 무너졌는지에 대해 판단할 때 Balance Factor라는 것을 활용한다. 이는 아래와 같은 공식으로 구한다.

BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이

​

우회전

1. y노드의 오른쪽 자식 노드를 z노드로 변경한다.

2. z노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.

​

좌회전

1. y노드의 왼쪽 자식 노드를 z노드로 변경한다.

2. z노드 오른쪽 자식노드를 y노드의 왼쪽 서브트리(T2)로 변경한다.

​

Case를 기준으로 트리의 균형을 맞춘다.

LL Case일 때 해당 노드 기준 우회전

RR Case일 때 해당 노드 기준 좌회전

LR Case왼쪽 자식노드 기준으로 좌회전 히고 해당 노드 기준 우회전

RL Case오른쪽 자식노드 기준으로 우회전 하고 해당 노드 기준 좌회전

AVL트리는 이진 탐색트리의 균형을 맞출 뿐, 삽입 삭제는 비효율적이기 때문에, Dictionary 같은 잘 변동이 없는 것을 구현할 때 주로 사용되고, 삽입 삭제를 효율적으로 하기 위해 고안된 트리가 바로 RB트리이다.

RB트리 : https://the-ze.tistory.com/entry/Red-Black-Tree-%EA%B5%AC%ED%98%84

Binary Search Tree 구현 (yunsejin 폴더에 있음)