[알고리즘] PS를 위한 Splay Tree

Splay Tree는 Balanced Binary Search Tree의 한 종류로 데이터의 삽입, 삭제, 탐색을 $O(\log N)$에 준하는 속도로 처리할 수 있도록 하는 자료구조이다. 보통 학부과정에선 저런 기본 연산들을 배우게 되는데 Splay Tree를 사용해야만 해결할 수 있는 알고리즘 문제에서는 극한의 테크닉을 사용하여 많은 쿼리를 처리할 수 있다. 이 글에서는 Splay Tree가 어떤 자료구조인지 소개하기보다는 해결할 수 있는 application을 중점으로 소개한다. Splay Tree는 1985년에 Self-Adjusting Binary Search Tree라는 논문으로 소개가 되었고 여기에도 Tarjan이 저자로 들어가있다. 정말 많은 공헌을 하신 분이다.

 

Basic

Splay Tree에는 Rotate와 Splay 연산이 들어있는데 이는 간략하게 짚고 넘어간다.

Rotate 연산은 현재 노드를 부모 위치로 옮기는 연산이다. 그림을 보면 쉽게 이해할 수 있다.

Rotate

이렇게 하면 여전히 BBST의 특징인 중위순회 했을 때 정렬된 순서가 유지되고 특정 노드의 위치를 바꿀 수 있다. 링크드리스트를 구현하듯이 C++의 포인터를 사용하여 구현하면 편하다. 파이썬으로는 안해봤는데 조금 불편하지만 가능할 것 같다.

 

Splay 연산은 특정 노드를 Rotate연산을 통해 루트로 옮기는 연산이다. Rotate 연산을 하면 현재 노드를 부모의 위치로 옮기니까 적당한 횟수를 수행하면 root에 도달하게 된다. 여기에서 Rotate하는 데 규칙이 있다.

• 조부모-부모, 부모-현재 노드의 방향이 같다. -> 부모를 먼저 Rotate하고 현재 노드를 Rotate한다. (zig-zig step)
• 조부모-부모, 부모-현재 노드의 방향이 다르다. -> 현재 노드를 두 번 Rotate한다. (zig-zag step)

방향이 같다는 것은 부모가 조부모의 왼쪽 노드, 현재 노드가 부모의 왼쪽 노드인 경우를 말한다. 대부분 쿼리를 처리하기 전에 Splay연산을 한 후 진행하게 된다. Splay 트리는 AVL 트리와 다르게 트리 자체가 balancing 하진 않다. 좌우 서브트리 높이 차이가 클 수도 있으며 연산을 진행하며 편향된 모양의 트리가 나오기도 한다. 그래서 언제나 $O(\log N)$이 되는 건 아니고 가끔 편향된 상태로 Splay를 수행하면 $O(N)$이 걸릴 수도 있다. 다만 편향된 상태에서 Splay를 진행하면 높이가 절반정도로 줄어들고 다음 연산부터는 다시 $O(\log N)$에 수행할 수 있다. 이러한 특성 때문에 Splay tree의 연산들은 amortized $O(\log N)$으로 알려져있다. 

 

그럼 이제 Splay tree를 사용하여 처리할 수 있는 쿼리들을 알아보자.

 

삽입 삭제 탐색

삽입연산은 BBST에서 탐색하듯이 내려가는 현재 노드 값보다 크면 오른쪽, 작으면 왼쪽으로 이동하며 삽입할 위치를 찾으면 된다. 찾았다면 그 위치에 노드를 추가하고 해당 노드를 Splay하여 다음 연산에 용이하게 한다.

삭제연산은 삭제할 노드를 Splay하여 루트로 올리고 삭제한 후 양쪽 서브트리를 합쳐주면 된다.

탐색연산은 삽입할 때처럼 BBST탐색하여 노드를 찾고 Splay하여 루트로 올려준다. 

 

이 연산들은 set, map에서도 지원하는 기능이라 이 쿼리만을 위해 Splay tree를 사용할 필요는 없다.

 

$K$번째 값 찾기

각 노드에 서브트리의 크기를 추가로 저장하면 K번째 값을 찾을 수 있다. 그리고 Rotate 할 때마다 서브트리의 크기가 바뀌기때문에

업데이트해야하는데 이는 Rotate 대상이 되는 현재 노드와 부모 노드의 값만 업데이트하면 된다는 것을 알 수 있다.

 

위 그림에서 각 서브트리의 크기를 $A, B, C$라고 할 때 현재 노드를 루트로 하는 서브트리의 크기는 $A + B + 1$에서 $A + B + C + 2$가 된다. 즉 Rotate할 때 현재 서브트리 크기 값에서 $C + 1$을 더해준다. 부모 노드를 루트로 하는 서브트리의 크기는 $A + B + C + 2$에서 $B + C + 1$가 된다. 부모의 서브트리 크기 값에서 $A + 1$을 빼면 된다.

 

이제 $K$번째 값을 찾으려면 다음 과정을 루트부터 재귀적으로 수행하면 된다.

• $K$가 왼쪽 서브트리의 크기보다 작거나 같으면 왼쪽으로 내려간다.
• $K$가 왼쪽 서브트리의 크기 + 1이라면 현재 노드의 값이 $K$번째 값이다.
• $K$가 왼쪽 서브트리의 크기 + 1보다 크다면 $K$에서 왼쪽 서브트리의 크기 + 1 을 빼고 오른쪽으로 내려간다.

$K$번째 값에 해당하는 노드를 찾았다면 Splay연산을 통해 루트로 보낸다. 이 작업을 수행하는 함수를 앞으로 find_kth(K)라고 부를 것이다.

이 쿼리도 PBDS를 사용하면 쉽게 해결할 수 있으므로 Splay tree를 사용할 필요는 없다.

 

구간쿼리 수행하기

세그먼트트리로 해결할 수 있는 구간쿼리문제(구간합, 최대/최소)의 대부분은 Splay tree로도 해결할 수 있다.

구간 합 쿼리를 예로 들어보자.

우선 주어진 배열을 Splay tree로 변환해야한다. 하지만 BBST의 특성상 수열을 그냥 insert하면 정렬시켜버리기 때문에 구간쿼리를 처리할 수 없다. 그래서 이러한 쿼리를 처리할 때는 insert함수를 수정하여 무조건 가장 오른쪽에만 insert하도록 수정한다. 그렇다면 인덱스 접근은 어떻게 하는가? 배열의 $i$번째 인덱스를 Splay tree에서 접근하려면 위에서 소개한 find_kth(i)를 사용하면 된다.

구간 합 쿼리를 수행하기 위해 각 정점에 sum값을 저장한다. sum값은 현재 노드를 루트로 하는 서브트리 값의 총 합이다. 이는 find_kth에서 서브트리 크기를 관리한 것과 동일하게 관리하면 된다. 

이제 $[L, R]$범위에 포함된 구간 합을 구하는 쿼리를 하려면 어떻게 할까? 굉장히 단순하다!

• $R+1$번째 노드를 Splay한다.
• $L-1$번째 노드를 Splay한다.
• 구하고자 하는 값은 루트의 오른쪽 자식의 왼쪽 자식의 sum값이다.

왜 이게 가능할까? 역시 그림을 그려보면 쉽다.

 

 

두 번의 Splay 과정을 통해 $[L, R]$범위가 한 곳으로 모였다. 루트의 오른쪽 자식의 왼쪽 자식의 sum 값은 해당 범위에 존재하는 값들의 합이므로 구하고자하는 값이 된다. $L-1 \rightarrow R+1$순서대로 Splay하고 루트의 왼쪽 자식의 오른쪽 자식의 sum값을 구해도 같은 결과가 나온다. 구간 최대/최소 쿼리도 유사하게 진행하면 답을 얻을 수 있다.

 

Lazy 연산 수행하기

위와 같이 $[L, R]$구간을 모으고 나면 해당 노드에 lazy를 뿌려주어 lazy 갱신도 할 수 있다. 탐색하면서 내려가는 도중에 대상 노드에 lazy가 있다면 자식에게 뿌려주고 탐색하면 된다.

 

여기까진 Splay tree 없이도 가능한 쿼리들이었다. 그럼 이제 Splay tree를 사용해야만 처리할 수 있는 쿼리를 알아보자!

$i$번째 자리에 값 추가/삭제하기

find_kth(i)를 수행하면 왼쪽 서브트리의 크기는 $i-1$이 된다. 그렇다면 find_kth(i)를 수행하고 왼쪽 자식노드의 가장 오른쪽에 노드를 추가하면 $i$번째 자리에 값을 추가한 것과 같아진다. 추가하고 나면 sum값이나 서브트리의 크기를 잘 업데이트해준다.

삭제도 마찬가지로 find_kth(i)를 한 다음에 처음에 설명한 삭제 연산을 수행하면 된다.

일반 배열이면 $O(N)$이 걸렸을 연산을 Splay tree로 amortized $O(\log N)$에 수행했다!

 

구간 뒤집기

Splay tree의 꽃이다. 세그먼트트리와 다르게 Splay tree는 트리 모양이 동적으로 변하기 때문에 뒤집기연산이 가능하다. $[L, R]$구간을 뒤집는다고 하자. 구간쿼리 수행할 때처럼 구간을 모아주고 구간을 뒤집어야하는 지 여부(is_flip)를 추가로 저장한다. 이는 lazy와 동일한 형태로 동작하며 탐색할때마다 is_flip이 활성화돼있다면 좌우 서브트리 위치를 swap하고 자식에게 is_flip을 전파한다. 서브트리 swap이지만 포인터 교환이기때문에 $O(1)$에 가능하다!

구간 shift

구간 뒤집기가 가능하면 구간 shift도 가능하다. 예를 들어 $[1, 2, 3, 4, 5, 6]$인 배열을 오른쪽으로 $2$만큼 shift한다고 하자. 결과는 $[5, 6, 1, 2, 3, 4]$가 될 것이다. 전체를 뒤집으면 $[6, 5, 4, 3, 2, 1]$이 되고 앞에서 2만큼 뒤집으면 $[5, 6, 4, 3, 2, 1]$, 남은 구간을 뒤집으면 $[5, 6, 1, 2, 3, 4]$가 되므로 뒤집기 연산만으로 shift를 할 수 있다.

일반화하면 $[L, R]$구간을 오른쪽으로 $K$만큼 shift하는 연산은 $[L, R]$을 뒤집고 $[L, L+K-1]$과 $[L+K, R]$을 순차적으로 뒤집으면 된다. 왼쪽으로 shift하는 것도 유사하게 수행하면 된다.

 

Splay Tree로 해결할 수 있는 쿼리 목록

모두 $O(\log N)$에 가능하다.

• 중간/앞/뒤 값 하나 삽입, 삭제, 갱신
• $K$번째 값 찾기 (오름차순, 내림차순, 랜덤 액세스)
• 구간 삭제
• 구간 쿼리 (최대, 최소, 합, gcd, ...)
• Lazy Propagation
• 구간 뒤집기
• 구간 shift (좌, 우)

 

연습문제

https://www.acmicpc.net/problem/2844

https://www.acmicpc.net/problem/13159

https://www.acmicpc.net/problem/13543

https://www.acmicpc.net/problem/17607

 

Additional Question

Splay tree로 Segment tree beats문제도 해결할 수 있을까요?

https://www.acmicpc.net/problem/17474