경로 복사 기법

넓은 의미에서 데이터 구조란 데이터를 저장하는, 참조로 연결된 노드들의 집합입니다.

일반 배열도 이 정의에 해당합니다. 배열에는 노드가 하나 있고, 그 노드에 $n$개의 칸이 저장됩니다.

각 노드가 $O(1)$개의 필드와 링크를 저장하는, 조금 더 좁은 범위의 구조 클래스를 살펴봅시다. 예를 들어, 뒤에서 살펴볼 세그먼트 트리와 트립이 이 성질을 만족합니다.

이러한 구조에는 구조를 완전히 영속으로 만드는 간단하고 일반적인 방법이 있습니다. 바로 경로 복사 방법입니다.

균형 이진 트리를 예로 들어 살펴봅시다. 새 원소를 추가하는 것과 같은 어떤 갱신을 수행해야 하는데, 이때 이전 트리에 대한 정보는 하나도 잃지 않아야 한다고 합시다.

새 자식을 추가해야 하는 정점을 하나 잡읍시다. 새 자식을 그 정점에 직접 추가하는 대신, 루트에서 그 정점까지의 경로 전체를 모든 데이터 및 포인터와 함께 복사한 다음, 복사된 경로에서 해당하는 정점에 자식을 추가합니다. 변경된 노드에 도달할 수 없는 나머지 모든 정점은 건드리지 않습니다.

이러한 연산의 결과로 새 루트에서는 갱신된 트리의 모든 정점에 도달할 수 있고, 이전 루트와 기존에 존재하던 모든 정점에서는 이전과 정확히 같은, 변경되지 않은 정점들에 도달할 수 있습니다. 우리는 아무것도 삭제하거나 변경하지 않았고, 단지 로그 정도 개수의 새 정점을 만들었을 뿐이기 때문입니다.

각 연산 후에 트리의 루트를 별도의 배열에 저장해 두면, 임의의 이전 버전에 접근할 수 있게 되며, 그 버전들로부터 자유롭게 「포크」할 수 있습니다.

#점근적 복잡도

대부분의 연산에서는 어차피 로그 시간만큼의 작업을 해야 하므로 시간 복잡도는 변하지 않지만, 메모리 사용량은 $O(n \log n)$까지 늘어납니다.

하지만 실제로는 영속 구조가 상당히(2~5배) 느릴 수 있습니다. 데이터가 더 이상 재사용되지 않아 프로세서 캐시의 이점이 거의 사라지기 때문입니다.

또한 영속 구조에서는 최악의 경우 분할 상환이 작동하지 않습니다. 어떤 무거운 연산(예를 들어 «대나무 압축»)이 있다면, 그 연산 직전까지 여러 번 되돌아가서 그 연산을 반복할 수 있기 때문입니다. 따라서 서로소 집합이나 splay 트리 같은 구조는 더 나쁜 점근적 복잡도를 가지게 됩니다.

#영속 스택

영속 트리의 구현과 활용은 다음 글들에서 살펴보고, 지금은 학습 목적으로 이 방법을 스택에 적용해 봅시다.

마지막 원소를 가리키는 포인터를 둔 배열 외에도, 스택은 링크를 이용해 구현할 수도 있습니다. 이 경우 스택의 “루트"는 스택의 맨 위 원소입니다.

struct Node {
    int val;
    Node *prev;
};

Node *head;

void add(int x) {
    head = new Node(x, head);
}

int top() {
    return head.val;
}

void pop() {
    Node *old = head;
    head = head->prev; // если на память пофиг, можно оставить только эту строчку
    delete old;
}

이제 스택을 퍼시스턴트하게 만들기 위해 추가 필드는 필요하지 않지만, 전역 버전 배열을 추가하고 모든 메서드에 추가 매개변수를 넣어야 합니다:

vector<Node*> versions;

void add(int x, int v);
int top(int v);
void pop(int v);

참조 기반 구조를 영속으로 만들려면 그 상태를 어떻게든 변경하는 연산만 수정하면 됩니다. 우리의 경우에는 add와 pop입니다.

add의 경우 같은 절차를 사용하되, head를 덮어쓰는 대신 새 노드를 만들어야 합니다:

void add(int x, int v) {
    versions.push_back(new Node(x, versions[v]));
}

pop도 같은 방식으로 처리할 수 있지만, 이미 존재하는 노드에 대한 참조를 버전 목록 끝에 추가하기만 하는 요령을 쓸 수도 있습니다:

void pop(int v) {
    versions.push_back(versions[v]->prev);
}

두 연산 모두 $O(1)$의 시간과 추가 메모리로 동작합니다.

영속 스택을 사용하면 영속 큐를 (두 개의 영속 스택을 통해) 쉽게 구현할 수 있지만, 상환 분석에 의존하기 때문에 최악의 경우 연산당 $O(n)$ 시간이 걸립니다. 또한 다섯 개 또는 여섯 개의 스택으로 연산당 순수 $O(1)$ 시간에 큐를 구현하는 복잡한 방법들도 있습니다.