Treap
목차
개요
이 포스트를 쓰며
언제 한번, Treap의 활용성에 대해서 적고 싶었다. 물론 여기서 내가 여러분에게 소개하고자 하는 것은 Treap을 BST로서 다루는 것이 아닌, 배열을 자유롭게 붙이고 떼고 뒤집는 것에 설명하기 위함이다. Treap은 기본적으로 BST로서 사용할 수 있지만, Splay Tree 처럼 배열을 다루는 데 사용할 수 있다. Splay Tree 처럼 여러가지의 method 들을 활용하여 amortized 시간을 내는것은 아니고, 확률에 의존하는 경향이 매우 크지만, 이러한 자료구조는 대회상황에서 의사난수를 적절히 활용하면 반례 데이터를 만들기 매우 어려워지며, 실제 개발에 쓰일지는 미지수지만, 만약 실제 상황에 쓰인다면 더더욱이 $O(log n)$ 시간이 보장된다. Splay Tree의 쉬운 구현의 장점을 가져오며, 동시에 확장성도 나쁘지 않은 Treap 에 대해 소개하겠다.
요구 지식
이번 포스트는 난이도가 은근히 있다. 적어도 BST에 대한 지식은 반드시 요구하며, Segment Tree의 lazy propagation의 원리 역시 알고 있어야 한다. 알고 있지 않더라도 구현에는 큰 부담이 없지만, 전체적인 내용을 이해하기 위해서는 반드시 필요하다.
개념
기본적으로 BST는 입력되는 데이터에 따라 BBST 가 되지 않을 확률이 매우 높다. 이러한 상황을 해결하기 위해 Key 값을 제외한 Weight 값을 추가적으로 부여하며, (물론 이 값은 랜덤이다.)동시에 Heap의 원리를 활용하여 BBST가 되게끔 균형을 맞춰 주는 것이다. 이것은 매우 기본적인 아이디어이며, 이 아이디어를 이용하여 BBST 를 만들어 활용하는 것은 매우 많이 알려져 있는 기법이므로 이번 포스트에서는 언급하지 않겠다. 이번 포스트는 이 Treap을 활용하여 배열을 붙이고 떼고, 그리고 뒤집는 것을 $O(log n)$ 안에 수행하는 작업을 보일 것이다.
이를 수행하기 위해서는 기본적으로 이해해야하는 것은 병합 작업이다. 일단, 일반적인 BST는 잠깐 구석에 두고 이 Treap의 작동원리를 살펴보자. 배열을 붙였다 떼었다 해야 하므로 x번째 변수를 찾는것은 매우 쉽게 할 수 있으나, 어떤 값이 Treap에 있는지 찾는것은 어렵다. 즉, 여기서 기억해야 할것은 BST의 기본인 Key 값이 위치, 즉, 몇번째인가에 대한것을 알 수 있다. 물론 실제로 Key 값을 활용하는건 당연히 아니고 size를 활용할 것이다. 이제 붙이는 작업, 조금 고급지게 표현해서 병합 작업을 살펴보자.
병합
병합은 우선 두개의 Treap을 붙여서 하나의 Treap을 만드는 작업이다. 좀더 쉽게 설명하면 두 배열을 붙여서 하나의 긴 배열을 만드는 작업이다. 보통 두 배열을 붙일때는 $O(n)$의 연산이 필요하지만, Treap은 오로지 $log(n)$의 연산을 필요로 한다. 이는 Treap이 이진 트리라는데에 기인한다. 먼저, 두 Treap을 병합하기 위해 mainT, leftT, rightT 가 있다고 해보자. 우선 leftT의 루트가 가르키는 값의 Weight값과 rightT가 가르키는 Weight 값을 비교했을때 leftT가 더 작다고 해보자. 그렇다면 합쳐질 Treap mainT에 leftT의 루트와 왼쪽 자식의 부트리가 붙게 된다. 이렇게 되면 기본적으로 left가 두 배열중 왼쪽에 해당되니 왼쪽으로 왼쪽의 모든 값들을 붙였다고 생각하면 된다. 완벽한 균형이었다고 가정한다면 절반만큼을 떼어서 mainT에 붙이는 것이다. 그리고 나서 leftT의 루트의 오른쪽 자식의 부트리를 새로운 leftT으로 간주하고 mainT는 원래의 leftT의 루트와 그 왼쪽 자식의 부트리를 붙인 상태에서 오른쪽 자식을 붙일 준비를 한다. 반대의 경우는 다음과 같다. rightT의 루트가 Weight가 작다고 해보자. 그렇다면 rightT의 루트와 그의 오른쪽 자식의 부트리를 mainT에 넣는다. 이것은 오른쪽 배열에 붙이는 것과 같다. 이후 왼쪽 자식이 비는 것을 처리하기 위해 rightT의 루트의 왼쪽 자식의 부트리를 새로운 rightT로 간주하고 붙여넣을 준비를 한다. 이것을 재귀적으로 처리하면 깔끔하게 해결된다. 이는 배열의 절반을 왼쪽에 붙이고 그 절반을 왼쪽에 또 붙이고 다시 절반을 오른쪽에 붙이고… 이런 작업들이 연속적으로 이루어진다고 생각하면 편하다.
이는 병합에 대한 설명이었다. 그 다음은 떼는 것, 역시 고급지게 표현하여 분할 작업을 살펴 보자.
분할
분할은 병합보다 복잡하다. 원래의 Treap을 두개의 Treap에 나눠담는 것이 목표이다. 이때 분할은, 만약 이것을 배열이라고 한다면, 맨 앞부터 k개 만큼을 왼쪽 Treap에 나머지는 오른쪽 Treap에 넣는거라고 생각하면 된다. 정확히 그말과도 일치하고 말이다. 그렇다면 이 작업은 기본적으로 Treap의 노드가 담고있는 size를 요구한다. 자 여기서는 Treap만 살펴보면 되니 간단하다. 우선 Treap의 왼쪽 자식의 size를 본다. 그리고 현재 필요한 k개 보다 작게, (왜 여기서 같은 경우는 포함하지 않는다면 현재 루트 자기자신도 포함해야하므로 정확히는 k-1까지 봐야하기 때문이다.)담아낼 수 있다면, 루트를 포함하여 왼쪽자식의 부트리를 통째로 왼쪽 Treap(여기서도 leftT라고 부르겠다.)에 담는다. 그렇다면 그러한 leftT는 당연하게도 오른쪽 자식이 비게되는데, 그 오른쪽 자식부터 채워나간다고 생각하면 된다. 잘 생각해보면 왼쪽부터 붙여나가기 때문이다. 그렇다면 k보다 같거나 큰 반대의 경우도 마찬가지, 오른쪽 Treap(마찬가지로 rightT)에 담아야 하는 상황의 경우 현재 루트를 포함한 오른쪽 자식의 부트리를 rightT에 담게 된다. 그러면 왼쪽 자식이 비게되는 상황이 오므로 그곳을 채우러 간다. 이것을 재귀적으로 수행하면 깔끔하게 해결된다.
구현
일단은 가장 중요한 구조체 선언과 getter 부분을 살펴보자.
long long seed = 1987152371;
long long mod = 1000000007;
long long salt = 101;
int rnd() {
seed *= seed;
seed %= mod;
seed += salt;
seed %= mod;
return (int)seed;
}
struct node {
node *left, *right;
node *par;
int weight, size, val;
node() {
par = left = right = nullptr;
weight = rnd();
size = 1;
val = 0;
}
node(int v) {
par = left = right = nullptr;
weight = rnd();
size = 1;
val = v;
}
};
int get_size(node *treap) {
if(treap == nullptr) return 0;
return treap->size;
}
병합
void merge(node *&treap, node *left, node *right) {
if(left == nullptr) treap = right;
else if(right == nullptr) treap = left;
else {
if(left->weight < right->weight) {
merge(left->right, left->right, right);
treap = left;
}
else {
merge(right->left, left, right->left);
treap = right;
}
treap->size = get_size(treap->left) + get_size(treap->right) + 1;
}
}
병합을 구현하는 것 역시 매우 간단하다. 개념에서 설명한 있는 그대로를 구현하면 되기 때문이다. 다만 주의할 것은 후술할 분할을 구현하기 위해 세그먼트 트리에서 구간의 값을 가져오듯이 size 값을 갱신시켜주는 것을 해야한다. 또한 *&로 시작하는 변수가 다소 생소할 수 있을텐데, 이는 reference variable 의 포인터 타입을 의미한다. 자바로 생각하면 객체인데, 포인터를 담는 객체라고 생각하면 편하겠다. 즉, 다른 함수에서 호출되면서 그 함수에서 호출한 변수를 바꾸어야 하는데 이를 편하게 작업하고자 사용한 변수이다. treap = left; 로 바꾸는 행위는 main 함수 내부에서 호출됐을때의 그 변수를 바꾸는 목적도 있지만, 오른쪽 자식을 채우기 위해 재귀적으로 탐색할때 그 오른쪽 자식을 대체하는 역할도 한다.
분할
void split(node *treap, node *&left, node *&right, int k) {
if(treap == nullptr) left = right = nullptr;
else {
if(get_size(treap->left) < k) { // -1 하고 = 붙여도 된다. 좀더 엄밀한 것을 좋아한다면 (~ - 1 <= k) 로 나타내보자.
split(treap->right, treap->right, right, k - get_size(treap->left) - 1);
left = treap;
}
else {
split(treap->left, left, treap->left, k);
right = treap;
}
treap->size = get_size(treap->left) + get_size(treap->right) + 1;
}
}
구현은 위와 같이 매우 간단하다. 위 개념에서 설명은 안했지만, 방문하는 작업이 모두 끝난 다음엔 항상 반드시 트립의 size 값을 변화시켜 주어야 한다. 이는 나중에 쿼리 문제를 해결할 때 구간에 대한 값을 구하는데 매우 용이하게 사용됨을 보여주고자 한다.
응용
지금부터 설명할 것은 Treap이 갖는, Splay Tree 처럼, 그리고 Segment Tree 처럼 구간합, 최대, 최소 를 구하는 작업과 동시에 배열 뒤집기의 작업까지 몽땅 $O(log n)$에 처리하는 것을 보여주고자 한다. 이는 Splay Tree 처럼 Treap이 갖는 장점이며, 확장성이 매우 높기 때문에 위의 코드에서 점차 확장되는 방식으로 쿼리를 처리하게 할 수 있다.
구간합, 최대, 최소를 구하는건 매우 간단하다. 세그먼트 트리처럼 병합, 혹은 분리 작업이 끝나고 나서 두 자식이 갖고 있는 정보로 자기 자신을 갱신하면 되기 때문이다. 뒤집기는 어떻게 해야할까? 뒤집기가 다소 어려울 수 있는데 이 작업은 모든 자식이 있는 노드에 대해서 두 자식의 left right 를 바꿔주면 된다. 한마디로 트리 전체를 뒤집는 것이다. 그렇다면 $O(n)$이 아니지 않느냐는 반박을 할 수 있다. 이것을 해결하기 위해 lazy propagation 을 도입하는 것이다. 지금 당장 필요한게 아니라면, 나중에 뒤집어도 트리의 보존성은 유지되기 때문에 굳이 뒤집지 않아도 되는 것이다. 이 작업들은 전부 세그먼트 트리를 공부해보았다면 위의 코드에 증축하는 형식으로 바로 추가할 수 있으므로 곧바로 구현 단계로 넘어가겠다.
구조체, 갱신 함수
struct node {
node *left, *right;
node *par;
int weight, size, val;
int lazy;
int mx, mn;
long long sum;
node() {
par = left = right = nullptr;
weight = rnd();
size = 1;
val = 0;
lazy = 0;
mx = mn = 0;
sum = 0;
}
node(int v) {
par = left = right = nullptr;
weight = rnd();
size = 1;
val = v;
lazy = 0;
mx = mn = v;
sum = v;
}
};
구조체를 조금 확장했다. lazy와 mx, mn, sum을 추가했으며, par는 후술할 문제에서 요긴하게 사용된다.
void lazy_prop(node *treap) {
if(treap == nullptr) return;
treap->lazy = 1 - treap->lazy; // 반대로 뒤집는다.
}
void update(node *treap) {
if(treap == nullptr) return;
if(treap->lazy) {
treap->lazy = 0;
swap(treap->left, treap->right);
lazy_prop(treap->left);
lazy_prop(treap->right);
}
treap->sum = treap->mx = treap->mn = treap->val;
if(treap->left != nullptr) {
treap->left->par = treap;
treap->sum += treap->left->sum;
treap->mn = min(treap->mn, treap->left->mn);
treap->mx = max(treap->mx, treap->left->mx);
}
if(treap->right != nullptr) {
treap->right->par = treap;
treap->sum += treap->right->sum;
treap->mn = min(treap->mn, treap->right->mn);
treap->mx = max(treap->mx, treap->right->mx);
}
}
lazy propagation 을 위한 함수와 구간의 최소, 최대, 합을 구하기 위한 update 함수이다. 너무 당연한 구현이므로 넘어가도록 한다.
병합
void merg(node *&treap, node *left, node *right) { // merge 라는 함수가 있길래 피하기 위해 merg로 바꾸었다.
if(left == nullptr) treap = right;
else if(right == nullptr) treap = left;
else {
if(left->lazy) { // 합치는 과정중에 left의 lazy가 1이라면
left->lazy = 0;
swap(left->left, left->right); // 왼쪽자식 오른쪽 자식을 뒤집어줌
lazy_prop(left->left);
lazy_prop(left->right);
}
if(right->lazy) { // 위와 동일
right->lazy = 0;
swap(right->left, right->right);
lazy_prop(right->left);
lazy_prop(right->right);
}
if(left->weight < right->weight) {
merg(left->right, left->right, right);
treap = left;
}
else {
merg(right->left, left, right->left);
treap = right;
}
treap->size = get_size(treap->left) + get_size(treap->right) + 1;
}
update(treap); // 모든 작업이 끝나고 update 해준다.
}
세그먼트 트리와 유사하지 않은가? 위 코드에서 그저 lazy propagation 작업과 update 작업을 추가해준 코드이다. 구현 하는데에는 별로 어렵지 않을 것이다.
분할
void split(node *treap, node *&left, node *&right, int k) {
if(treap == nullptr) {
left = right = nullptr;
}
else {
if(treap->lazy) {
treap->lazy = 0;
swap(treap->left, treap->right);
lazy_prop(treap->left);
lazy_prop(treap->right);
}
if(get_size(treap->left) < k) {
split(treap->right, treap->right, right, k - get_size(treap->left) - 1);
left = treap;
}
else {
split(treap->left, left, treap->left, k);
right = treap;
}
treap->size = get_size(treap->left) + get_size(treap->right) + 1;
}
update(treap);
}
lazy 갱신하고 update하고… 병합과 다를 게 없다.
뒤집기
void rev(node *treap) {
if(treap == nullptr) return;
swap(treap->left, treap->right);
lazy_prop(treap->left);
lazy_prop(treap->right);
}
트리의 전체를 뒤집는 것, 간단하지 않은가? 루트의 두 자식만 뒤집고 lazy 만 전달해주면 끝난다.
문제풀이
트립의 운용 방법을 살펴 보았다. 이제 문제를 풀어보도록 하자.
이 링크를 통하여 문제를 볼 수 있다.
이 문제는 주어진 1, 2, 3, …, n - 1, n 배열에 대해 특정 구간의 합, 최솟값, 최댓값을 구하고 shift 연산을 하거나 뒤집기 연산을 하는 문제이다. 그리고 중요한 x번째 숫자 찾기, a숫자의 번째수 찾기 등을 찾는 질의도 포함된 복잡한 문제이다.
우선, 이 문제는 UCPC 2016 A번 문제로서 splay tree 가 정해였던 문제였다. 하지만 splay tree를 안쓰고도 충분히 구현 할 수 있음을 알 수 있다.
우선 splay tree 가 갖는 장점을 treap 역시 갖고 있으므로 그 장점을 모두 활용하면 된다.
기본적으로 l, r의 구간을 찾아내는 것은 배열을 세개로 나누는 것과 동일하다고 볼 수 있다. [1, l - 1], [l, r], [r + 1, n] 으로 나눈 뒤 가운데의 배열을 지지고 볶으면 되는 것이다. 배열을 세개로 나누는 것은 트립의 입장에서는 매우 간단하다. split 연산 두번만 하면 해결되기 때문이다. 이 모든 시간복잡도는 $O(log n)$ 이므로 시간초과를 걱정하지 않아도 된다.
그 다음 뒤집기인데, 뒤집기는 말 안해도 알지 않겠는가? 응용에서 구현해둔 함수를 저 세개의 트립중 가운데것을 뒤집으면 된다.
shift 역시 간단하다. 배열을 shift 하는 개수만큼 자르고 뒤에다, 혹은 앞에다 이어 붙이는 게 전부이다. 위의 코드들을 전부 이해하고 구현할 수 있다면 이 단계는 매우 간단한 것이다.
어려운 것은 역시 x번째 숫자 찾기와, a숫자의 번째수 찾기인데, 사실 전자는 그렇게 어렵지는 않다. size를 잘 활용하면 몇번째 숫자가 무엇인지는 쉽게 알아낼 수 있다. 물론 이 작업 와중에 lazy가 작용이 된다면 당연히 갱신해야 되는것을 잊지 말자. a숫자의 번째 수 찾기는 복잡하다. 여기서 사용되는 것이 parents 인데 현재 그 값의 위치를 안다면 부모를 따라 올라가면서 내가 몇번째인지 x번째 숫자 찾기의 역으로 생각하여 구해낼 수 있기 때문이다. 이 방법 역시 lazy의 갱신을 생각하며 구현해야 한다.
node *pt[300010]; // 위치를 저장할 변수
int main() {
int n, q;
scanf("%d %d", &n, &q);
node *treap = pt[1] = new node(1); // 처음에 1을 생성하여 treap 의 루트로 한다.
for(int i = 2; i <= n; i++) {
pt[i] = new node(i);
merg(treap, treap, pt[i]); // 트립에 붙여준다.
}
for(int i = 0; i < q; i++) {
int req;
scanf("%d",&req);
if(req == 1) {
int l, r;
scanf("%d %d", &l, &r);
node *h1, *h2, *h3;
split(treap, h1, h2, l - 1);
split(h2, h2, h3, (r - l + 1));
printf("%d %d %lld\n", h2->mn, h2->mx, h2->sum);
rev(h2);
merg(treap, h1, h2);
merg(treap, treap, h3);
}
if(req == 2) {
int l, r, x;
scanf("%d %d %d", &l, &r, &x);
node *h1, *h2, *h3;
node *a1, *a2;
split(treap, h1, h2, l - 1);
split(h2, h2, h3, (r - l + 1));
printf("%d %d %lld\n", h2->mn, h2->mx, h2->sum);
if(x >= 0) {
if(x % (r - l + 1) != 0) {
split(h2, a1, a2, (r - l + 1) - (x % (r - l + 1)));
merg(h2, a2, a1);
}
}
else {
if((-x) % (r - l + 1) != 0) {
split(h2, a1, a2, (-x) % (r - l + 1));
merg(h2, a2, a1);
}
}
merg(treap, h1, h2);
merg(treap, treap, h3);
}
if(req == 3) {
int x;
scanf("%d", &x);
printf("%d\n", get_val(treap, x));
}
if(req == 4) {
int x;
scanf("%d", &x);
printf("%d\n", get_pos(pt[x], nullptr, 1));
}
}
print(treap);
printf("\n");
return 0;
}
3번, 4번을 제외하고는 구현에 그리 어렵지 않을것이다. 초기화 작업도 익숙할 것이다. 만들고 나서 그냥 붙이면 되는것이다.
이제 중요한 핵심인 번째수 찾기와 숫자 찾기이다.
int get_val(node *treap, int pos) {
if(treap->lazy) {
treap->lazy = 0;
swap(treap->left, treap->right);
lazy_prop(treap->left);
lazy_prop(treap->right);
}
if(pos - get_size(treap->left) == 1) return treap->val;
else if(pos - get_size(treap->left) - 1 >= 1) return get_val(treap->right, pos - get_size(treap->left) - 1);
else return get_val(treap->left, pos);
}
int get_pos(node *treap, node *cmp, int flag) {
if(treap == nullptr) return 0;
int tmp = get_pos(treap->par, treap, 0);
if(treap->lazy) {
treap->lazy = 0;
swap(treap->left, treap->right);
lazy_prop(treap->left);
lazy_prop(treap->right);
}
tmp += treap->right == cmp || flag ? get_size(treap->left) + 1 : 0;
return tmp;
}
먼저 번째수가 주어졌을 떄, 값 찾기이다. 일단 lazy 갱신은 당연하다듯이 맨 위에서 부터 시작한다. 그 다음 해야할 작업은 내 앞에 있는 숫자들, 즉, 내 왼쪽 자식을 뺐을때 내가 가능성이 있는지 확인한 뒤, 가능성이 있으면 오른쪽으로 이동, 없으면 왼쪽으로 이동한다. 만약 왼쪽 자식을 뺐더니 1이 나온경우 자기 자신이 정답이므로 그 노드의 value 값을 return 한다.
두번째는 값이 주어졌을 때, 번째수 찾기이다. 이것의 구현은 어쩔 수 없이 배열의 힘을 빌렸는데, 초기에 각 노드들을 저장해둔 이유는 이를 위한 것이다. 일단 부모노드들이 update 되는 것을 update 코드에서 확인해보고 오자, 확인하고 왔다면, 이제 부모노드를 따라 올라가는 과정을 보자, 따라 올라가면서, 함수에서 다시 빠져나오는, 즉, 루트노드 까지 도달했으면 함수에서 빠져나오면서 lazy를 확인한다. 이는 값 찾기때와 달리 내려가는 것이 아닌 위로 올라가는 것이기 때문이다. 그렇게 했으면 내가 오른쪽 자식인지 확인하고 오른쪽 자식이면 left의 size를 더해준다. 그리고 마지막 자기자신에 도달했을 땐, 항상 왼쪽 자식을 더해주면 된다.
여기 까지 구현했으면 마무리로 마지막 배열의 상태를 출력하는것이 남았다. 이는 BST를 알고 있다면 자명한 사실이지만, 그냥 중위순회 하면 끝난다.
void print(node *treap) {
if(treap == nullptr) return;
update(treap);
print(treap->left);
printf("%d ", treap->val);
print(treap->right);
}
굳이 부연설명은 필요 없을 것 같아서 넣지 않았다.
이제 이 코드들을 전부 조합하면 위 문제를 풀 수 있다. 하나하나의 작업들을 모아서 큰 문제를 해결하는 좋은 문제이다.
마무리
이번 포스트를 통하여 treap의 BST로서가 아닌 배열로서의 사용법을 공유하고 문제 풀이에 어떻게 적용할 수 있는가를 공유할 수 있게 되었다. 문제 풀이 말고도 실제 상황에 적용할 여지가 있는지는 좀 고민해보아야겠지만 확실히 강력한 알고리즘임에는 틀림없다고 생각한다.
참고자료
- Laaksonen, Antti, “treap.” 알고리즘 프로그래밍 대회 입문 가이드. 2019.05.09: pp302-307. 조승현 역