[PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap

2026. 1. 13. 10:00

※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.

들어가기 전에

지금도 글쓴이는 구현력이 많이 부족하다고 느끼지만, 과거에는 구현력이 매우 부족했었다. (implicit) treap은 그 당시에 익혀보려고 도전했다가 실패했던 자료구조 중 하나이다. 이 때문에 글쓴이는 treap을 막연히 어려운 주제라고 생각하고 있었고, 익히는 도중에도 treap을 제대로 익힐 수 있을지 많은 걱정을 하였었다.

이제 과거의 기억에서 벗어나 treap을 다시 마주할 때가 왔다.

개요

이번 글에서 살펴볼 주제는 Cartesian Tree, Treap, Implicit Treap이다.

Cartesian Tree는 treap과 유사한 점이 많은 자료구조이다. 따라서 이 글에서는 treap을 다루기에 앞서 Cartesian Tree를 먼저 소개할 것이다.

한편, Cartesian Tree는 그 자체만으로도 좋은 성질을 가진 자료구조이기도 하다. PS/CP에서도 이러한 성질을 활용한 문제를 종종 만나볼 수 있다. 따라서 이 글에서는 PS/CP에서 Cartesian Tree가 어떻게 활용되는지 또한 간단히 살펴볼 것이다.

treap은 Randomized Binary Search Tree라고도 불리는 자료구조이다. treap은 (binary search) tree와 heap의 합성어로, BST의 성질과 heap의 성질을 동시에 가지는 특징을 따 이름지어졌다.

PS/CP의 범주에서 treap은 BBST의 역할을 수행하는 자료구조이다. 그런데 PS/CP에서는 정답 코드를 작성하는 시간을 줄이는 것도 중요하므로, BBST를 활용하려는 목적만으로는 그냥 불러와서 사용하면 되는 std::set과 std::map, pbds 등을 제치고 굳이 treap을 직접 구현해 사용할 필요가 없다. 그러면 treap은 공부하지 않아도 되는 자료구조일까?

implicit treap은 key가 추상화된 treap이다. implicit treap은 다양한 쿼리를 처리하기 좋은 자료구조이므로 알아둘 가치가 충분하다. 특히, implicit treap은 많은 경우 implicit splay tree의 기능을 상당수 대체할 수 있다. 그리고 이것이 이번 글의 최종 목표이다.

Cartesian Tree

Cartesian Tree는 서로 다른 수로 구성된 수열에 대하여 다음과 같이 정의되는 binary tree이다.

(1) Cartesian Tree의 각 노드는 주어진 수열의 각 수에 대응된다.

(2) Cartesian Tree에서 inorder traversal(중위순회)을 하면 원래의 수열을 얻는다.

(3) Cartesian Tree는 min-heap property를 갖는다. min-heap property란 부모 노드에 대응되는 수는 (존재하는 모든) 자식 노드에 대응되는 수보다 작아야 한다는 성질을 말한다.

즉, 가볍게 서술하면 Cartesian Tree는 수열에서 가장 작은 수를 root로 하고 그 위치를 기준으로 좌우로 나눠진 두 배열에 대하여 이와 같은 실행을 반복하여 얻게 되는 트리의 각 root를 자식으로 갖는 트리를 말한다.

여기에서 min이라는 것은 (일상적으로 사용하는) 정수의 대소관계만을 뜻하는 것은 아니므로, 대소의 정의를 적절하게 할 수만 있다면 다른 order topology를 대응시켜도 된다. 예를 들어, min-heap property 대신 max-heap property를 적용해도 대소의 정의가 반대로 된 min-heap property를 만족시킨다고 생각할 수 있으므로 정의에 따라 Cartesian Tree라고 볼 수 있다.

Cartesian Tree는 서로 다른 수로 구성된 수열에 대하여 정의되어 있지만, PS/CP 문제풀이에서는 대해서도 등장한 순서에 따라 구분자를 넣는 등의 방법으로 다른 수처럼 취급하여 Cartesian Tree를 활용하기도 한다. 다만 이 경우, 문제 풀이 과정에서 같은 수의 취급에 유의해야 한다.

\(O(n)\) Construction of Cartesian Tree

크기가 \(n\)인 배열의 Cartesian Tree는 몇 가지 방법으로 \(O(n)\)에 구성할 수 있다. 이 글에서는 monotonic stack을 이용한 접근을 알아본다.

수열 \(a_1, a_2,\cdots a_n\)의 Cartesian Tree는 1부터 \(n\)까지의 인덱스 \(i\)에 대하여 다음의 1~4의 과정을 차례대로 진행하는 것으로 구성할 수 있다.

(0) 빈 stack을 준비한다. 이 stack은 monotonic stack이다.

(1) stack이 비거나 끝에 저장된 인덱스의 수열 값이 \(a_i\)보다 작아질 때까지 stack의 원소를 빼낸다.

(2) stack이 비지 않았다면 스택의 끝에 저장된 인덱스의 노드의 오른쪽 자식을 \(i\)로 한다.

(3) (1)에서 stack에서 마지막으로 뺀 원소가 존재한다면 그 원소를 \(i\)의 왼쪽 자식을 그 원소로 한다.

(4) stack에 \(i\)를 넣는다.

랜덤 수열에 대한 Cartesian Tree

수열의 수가 랜덤으로 주어질 때 Cartesian Tree의 높이의 기댓값은 어느 정도일까?

그 답은 quicksort와 비교해 생각해보면 금방 얻을 수 있다. 매번 주어진 배열에서 가장 작은 수를 고르고 그 양 옆의 각 두 부분수열에 대하여 재귀적으로 기대 높이를 구하는 과정에서 배열의 길이가 줄어드는 과정은. quicksort에서 배열의 크기가 줄어드는 과정이랑 완전히 대응된다.

따라서 크기 \(n\)인 랜덤 수열의 Cartesian Tree의 높이의 기댓값은 \(O(\lg n)\)이며, 이 수열의 높이가 \(O(n)\)이 될 확률은 이 수열을 quicksort로 정렬하는 시간복잡도가 \(O(n^2)\)가 될 확률에 가깝다는 것을 알 수 있다. 즉, quicksort의 경우 적절하게 자료의 순서를 먼저 섞어주면 사실상 \(O(n\lg n)\)에 수행할 수 있는 것처럼, 가중치가 임의로 주어진 수열의 Cartesian Tree의 높이는 사실상 \(O(\lg n)\)이 된다.

따라서 랜덤 수열에 대한 Cartesian Tree는 어느 한 쪽으로 노드가 지나치게 치우치지 않은, 어느 정도 균형 잡힌 이진 트리와 같은 모양을 하게 된다는 점을 알 수 있다.

Treap(Randomized Binary Search Tree; Randomized BST)

위와 같은 관찰로부터, key와 랜덤 가중치를 가지는 노드로 구성된, key 순서대로 정렬된 배열의 랜덤 가중치에 대한 Cartesian Tree는 균형 잡힌 이진 트리처럼 다룰 수 있다는 것을 알 수 있다. 이와 같은 구성의 자료구조를 treap이라고 한다.

treap은 tree와 heap이 합쳐져 만들어진 이름이다. treap 자료구조의 key는 BST처럼 정렬되어 있으며, 각 노드의 배치는 랜덤 가중치에 대한 heap 구조를 이루고 있기 때문이다. 다른 이름으로는 랜덤성을 이용해 만든 BST라는 측면에서 Randomized Binary Search Tree라고 부르기도 한다.

treap을 실질적인 BBST처럼 사용하려면 자료의 삽입 및 제거 등 기본 BBST 연산을 수행할 수 있어야 한다. treap에서 이러한 연산은 대부분 split과 merge의 두 가지 기본 연산을 활용해 구현할 수 있다.

split 연산

split은 주어진 treap을 기준이 되는 값 \(val\)을 기준으로 두 개의 treap으로 쪼개는 연산이다.

설명 편의상 \(val\)이 treap의 key 와 distinct하다고 가정하자. 이 때 split은 \(val\)을 기준으로 이 값보다 작은 key가 저장되어 있는 treap과 큰 값이 저장되어 있는 treap으로 쪼갠다. 이를 진행하면서 treap의 min-heap property가 깨지지 않아야 한다는 점에 유의하자.

split하려는 treap의 root와 기준이 되는 값 \(val\)이 주어질 때, split 연산은 (1) root에서부터 시작해서 현재 노드가 어느 쪽 treap에 들어갈지를 기준삼아 leaf까지 내려가는 과정과 (2) 다시 root로 돌아오면서 노드를 적절하게 이어붙여 두 개의 treap으로 split하는 과정으로 이루어져 있다. 이 과정을 자세히 살펴보자.

과정 (1)은 단순하다. 현재 노드의 key와 \(val\)을 비교했을 때 key가 \(val\)보다 작다면 현재 노드는 split 이후 왼쪽 treap에 속하게 될 것이다. 한편, 이 노드의 왼쪽 자식 노드를 root로 갖는 부분 treap의 노드의 모든 key는 현재 노드의 key보다 작은 값을 가지므로, 이 노드들 또한 모두 왼쪽 treap에 속하게 된다. 그러나 이 노드의 오른쪽 자식 노드는 어느 쪽 treap에 속하게 될지 정보가 부족하다. 따라서 오른쪽 노드로 탐색을 진행한다.

key가 \(val\)보다 큰 경우도 위와 거의 같다. 이 경우 현재 노드는 split 이후 오른쪽 treap에 속하게 되며, 이 노드의 오른쪽 자식 노드와 그 밑에 연결된 노드 오른쪽 treap에 속해야 한다는 점을 알 수 있다. 그리고 왼쪽 자식 노드는 아직 어느 쪽 treap에 붙게 될지에 대한 정보가 부족하다. 따라서 왼쪽 노드로 탐색을 진행한다.

이 탐색은 아무런 정보도 담고 있지 않은 null 노드가 나올 때까지 진행한다.

과정 (2)는 정보가 없던 자식 노드쪽의 정보를 재귀적으로 위로 전달하며 왼쪽 treap과 오른쪽 treap을 구성해나가는 과정이다. 정보가 없던 자식 노드에 대하여 왼쪽 treap에 속할 부분treap의 root와 오른쪽 treap에 속할 부분treap의 root를 얻어 현재 노드를 root로 하는 부분treap을 둘로 쪼개어 올라가는 것을 반복하자.

이 때 treap은 Cartesian Tree의 구조를 따르므로, 어떤 노드가 조상 노드의 왼쪽 자식으로 붙어야 하는 상황이라면 부모로 거슬러 올라가는 과정 중 오른쪽으로 올라가는 상황을 처음 만났을 때 그 노드의 왼쪽 자식으로 붙게 되며, 오른쪽 자식으로 붙어야 하는 상황이라면 부모로 거슬러 올라가는 과정 중 왼쪽으로 올라가는 상황을 처음 만났을 때 그 노드의 오른쪽 자식으로 붙게 됨을 확인하자.

한편, 이 과정에서 새로 붙게 되는 부모-자식 관계의 노드쌍은 기존 treap에서도 조상-자손 관계에 있었으므로 이와 같은 수정은 min-heap property를 깨지 않는다는 점을 확인하자.

과정 (2)까지 마치면 split 과정이 종료되며, 분리된 두 treap과 각각의 root 노드를 얻는다.

split 연산의 시간복잡도는 그 과정에서 재귀적으로 들어가는 노드의 깊이에 비례하며, 이 값은 평균적으로 \(O(lg n)\)임을 앞서 살펴보았다. 따라서 각 노드의 가중치를 랜덤으로 부여하면 split의 평균시간복잡도는 \(O(\lg n)\)이 된다.

merge 연산

merge는 주어진 두 개의 treap을 하나의 treap으로 합치는 연산이다. 이 때, 여기에서 주어지는 두 treap의 key의 범위는 서로 겹치지 않아야 한다. 편의상 두 treap을 왼쪽 treap과 오른쪽 treap이라고 부르자.

merge 결과로 얻게 되는 treap의 root는 왼쪽 treap의 root거나 오른쪽 treap의 root일 것이다. 그 외의 노드가 root가 된다면 treap의 min-heap property가 깨지기 때문이다.

먼저 왼쪽 treap의 root의 가중치가 오른쪽 root의 가중치보다 더 작은 경우를 살펴보자. 이 때, 왼쪽 treap의 root는 최종적으로 merge된 treap의 root가 될 것이다. 또한, 왼쪽 treap의 오른쪽 자식을 root로 갖는 부분 treap과 오른쪽 treap을 merge하여 왼쪽 treap의 왼쪽 자식에 붙이면 key의 정렬 순서도 깨지지 않고 min-heap property도 깨지지 않음을 관찰할 수 있다. 따라서 이를 재귀적으로 수행하는 것으로 merge 연산을 수행할 수 있다.

merge 연산의 시간복잡도 또한 split처럼 그 과정에서 재귀적으로 들어가는 노드의 깊이에 비례하며, 이 값은 평균적으로 \(O(\lg n)\)임을 앞서 살펴보았다. 따라서 각 노드의 가중치를 랜덤으로 부여하면 merge의 평균시간복잡도는 \(O(\lg n)\)이 된다.

다른 연산들

split과 merge를 이용하면 BBST가 가져야 하는 모든 연산을 어렵지 않게 구현할 수 있다. 예를 들어 특정 key의 삽입은 key를 기준으로 treap을 split한 뒤 삽입하려는 자료 노드 하나로 구성된 tree를 사이에 넣어 merge를 두 번 하면 된다. 또한 특정 key의 제거는 이 key를 기준으로 각각 왼쪽과 오른쪽 자료로 구성된 treap을 split으로 얻어 이들을 다시 merge하면 된다.

정렬된 자료가 주어졌을 때, Treap을 \(n\)번의 merge를 통해서도 구성할 수 있지만 Cartesian Tree의 \(O(n)\) 구성과 같은 방식으로 \(O(n)\)에 구성할 수도 있다.

Implicit Treap

implicit treap은 treap를 BBST처럼 사용하는 대신 배열에 대응시킨 것과 같이 사용하는 자료구조이다. implicit treap에서 일반 treap의 key에 대응되는 개념은 배열의 인덱스이다. 그러나 implicit treap을 활용하는 과정에서 이러한 인덱스는 쉽게 변경될 수 있고, 실제로 implicit treap은 이러한 변경이 필요할 때 주로 사용하는 자료구조이기도 하다.

implicit treap을 활용하는 대표적인 두 예시를 보자.

(1) 부분배열을 잘라서 다른 위치에 삽입하기

먼저 자르려는 부분배열의 앞뒤와 삽입할 위치를 기준으로 split을 시행한 뒤, 자른 부분배열을 삽입할 위치에 오게끔 적절한 순서로 merge한다.

(2) 부분배열의 자료 순서를 뒤집기(역순으로 바꾸기)

이 작업을 하려면 먼저 뒤집기 연산에 대한 lazy tag를 노드에 기록해둬야 한다.

먼저 뒤집으려는 부분배열의 앞뒤를 기준으로 split을 시행한 뒤, 자른 부분배열 treap의 root에 뒤집기 lazy tag를 toggle한다. 그리고 lazy tag가 켜져 있는 노드에 대한 접근이 필요할 때, lazy tag를 propagate하면서 해당 노드의 두 자식을 swap한다.

어떤 노드와 그 노드의 모든 자손 노드들에 대하여 왼쪽 자식과 오른쪽 자식을 swap하면 그 노드에 대응되는 배열이 뒤집어짐을 확인하자.

implicit treap은 더 이상 BBST가 아니므로 위와 같은 연산으로 key의 정렬이 무너지거나 하는 것은 신경쓸 필요가 없다. 오히려 가상의 key로 생각하고 있는 개념인 배열의 index를 의도대로 바꾸므로 이는 적절한 사용 방법이다. 또한 이 연산을 통해 Cartesian Tree의 min-heap property가 깨지지도 않음을 확인하자.