토픽 48 / 66·확률적 자료구조

Persistent Data Structure

수정 연산 시 기존 버전을 보존하면서 새로운 버전을 생성하는 불변(Immutable) 자료구조로, 이전 상태에 접근 가능하며 함수형 프로그래밍과 버전 관리에 적합

목적: 불변성 보장, 버전 관리, 롤백 지원, 동시성 안전, 함수형 프로그래밍

특징: 불변성, 버전 보존, 구조 공유(Structural Sharing), 효율적 복사

유형: 부분 영속(최신 버전만 수정 가능), 완전 영속(모든 버전 수정 가능), 합류 영속(버전 병합 가능)

구현 기법: Path Copying(경로만 복사, 공유), Fat Node(노드에 모든 버전 저장), Node Splitting(노드 분할)

구조 공유: 변경되지 않은 부분은 기존 버전과 공유 → O(log n) 복사만 필요

시간 복잡도: 연산 O(log n) - 경로 복사, 공간 O(n + k log n) - k = 버전 수

공간 복잡도: O(n log n) - 모든 버전 저장 시

장점: 불변성(버그 감소), 버전 히스토리, 롤백 용이, 동시성 안전(락 불필요), 디버깅 용이

단점: 메모리 사용 증가, 성능 오버헤드(복사), 구현 복잡도

적용사례: Git(버전 관리), Clojure/Haskell(함수형 언어), React/Redux(상태 관리), 데이터베이스 스냅샷, Undo/Redo

비교: 영속(불변/버전보존/메모리많음) vs 일시(가변/단일버전/메모리적음)

연관: 함수형 프로그래밍, 불변성, 구조 공유, Git, Clojure