Complex Data Structures 정리 (with Python 예제)

이번 글에서는 Data Structures & Algorithms 로드맵의 Complex Data Structures 파트를 정리한다. 복잡한 자료구조는 대규모 데이터를 효율적으로 저장, 관리, 탐색하기 위해 고안된 고급 구조로, 트리(Tree), 그래프(Graph), 해시 테이블(Hash Table), 힙(Heap) 등이 대표적이다.

---

Complex Data Structures란?

복잡한 자료구조는 단순한 배열이나 연결 리스트로는 효율적으로 다루기 어려운 데이터셋을 다루기 위해 설계되었다.

• 트리(Tree): 계층적 구조를 표현 (예: 파일 시스템)
• 그래프(Graph): 네트워크 구조 표현 (예: SNS, 네트워크 토폴로지)
• 해시 테이블(Hash Table): 키-값 기반 빠른 탐색
• 힙(Heap): 우선순위 큐(Priority Queue) 구현에 활용

---

2-3 트리 (2-3 Trees)

2-3 트리는 각 노드가 2개 또는 3개의 자식을 가질 수 있는 균형 트리다. 삽입과 삭제 시에도 균형이 유지되어 O(log n) 시간 복잡도를 보장한다.

class TwoThreeTreeNode:
    def __init__(self, keys=None, children=None):
        self.keys = keys or []
        self.children = children or []

# 간단한 예시: 루트 노드에 2개의 키가 있고, 자식이 3개 있는 구조
root = TwoThreeTreeNode(keys=[10, 20], children=[
    TwoThreeTreeNode([5]),
    TwoThreeTreeNode([15]),
    TwoThreeTreeNode([25])
])
print(root.keys)  # [10, 20]

---

B 트리 / B+ 트리

B 트리와 B+ 트리는 데이터베이스와 파일 시스템에서 자주 사용되는 균형 트리 구조다.

• B 트리: 모든 노드에 키와 데이터 포인터 저장
• B+ 트리: 데이터 포인터는 리프 노드에만 저장, 리프 노드는 연결 리스트로 연결되어 순차 접근이 효율적

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.children = []

# 루트에 2개의 키를 저장하는 예시
root = BTreeNode(leaf=False)
root.keys = [10, 20]
print(root.keys)  # [10, 20]

실제 DBMS의 인덱스 구조 대부분이 B+ 트리 기반으로 구현되어 있다.

---

스킵 리스트 (Skip List)

스킵 리스트는 다층 연결 리스트로, 평균적으로 O(log n) 탐색 성능을 제공한다. 랜덤성을 이용해 레벨을 유지하므로 구현은 간단하면서도 빠른 검색이 가능하다.

import random

class SkipNode:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=4):
        self.max_level = max_level
        self.header = SkipNode(-1, max_level)
        self.level = 0

    def random_level(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.max_level:
            lvl += 1
        return lvl

    def insert(self, value):
        update = [None] * (self.max_level + 1)
        current = self.header
        for i in reversed(range(self.level + 1)):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current

        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header
            self.level = lvl

        new_node = SkipNode(value, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

# 테스트
sl = SkipList()
for v in [3, 6, 7, 9, 12]:
    sl.insert(v)
print("SkipList 삽입 완료")

---

ISAM (Indexed Sequential Access Method)

ISAM은 IBM이 개발한 디스크 접근 방식으로, 데이터는 기본적으로 순차 저장되지만 인덱스(index)를 통해 빠른 검색이 가능하다. 이는 오늘날 DB의 인덱스 개념과 유사하다.

파이썬으로 ISAM 전체를 구현하기는 어렵지만, 개념적으로는 다음과 같이 표현할 수 있다.

class ISAM:
    def __init__(self):
        self.data = []
        self.index = {}

    def insert(self, key, value):
        self.data.append((key, value))
        self.data.sort(key=lambda x: x[0])
        self.index[key] = value

    def search(self, key):
        return self.index.get(key)

# 사용 예시
isam = ISAM()
isam.insert(1, "Alice")
isam.insert(3, "Bob")
isam.insert(2, "Charlie")

print(isam.search(2))  # Charlie

---

마무리

복잡한 자료구조들은 단순히 데이터를 저장하는 것을 넘어, 효율적인 탐색과 대규모 데이터 관리를 위한 핵심 기술이다.

• 트리와 그래프는 구조적 관계를 표현하는 데 강점이 있다.
• 해시 테이블은 평균 O(1)의 빠른 검색 성능을 제공한다.
• 스킵 리스트와 ISAM은 데이터베이스와 같은 시스템에서 효율성을 높이는 기반이 된다.