Splay Tree와 amortized 시간복잡도

본 글은 이 자료의 전반부를 포스트로 옮긴 것입니다.

독자가 Binary Search Tree와 알고리즘의 연산 시간을 계산하는 법을 안다고 가정하고 글을 작성합니다.

 

Self-Balancing Binary Search Tree(BBST)

이진 검색 트리는 각 노드마다 key를 가지고 있으며 어떤 노드 x의 left children에는 x의 key보다 작은 key를 가지고 있는 노드들이 존재하며, right children에는 x의 key보다 큰 key를 가지고 있는 노드들이 존재하도록 구성한 이진트리입니다.

따라서 이 자료구조는 inorder로 탐색을 진행했을 때, 그 순서가 노드들의 key값을 정렬한 순서와 동일합니다. 그리고 이 순서를 유지하도록 하면서 노드의 삽입, 읽기, 갱신, 삭제(CRUD)를 지원합니다.

이때, 구성된 트리가 치우쳐져(unbalance) 있을 경우 위 연산들의 시간 복잡도가 $O(N)$이 돼버립니다.

이런 참사를 막기 위한 연구는 정말 예전부터 있었으며 그 결과로 나왔던 것이 Self-Balancing Binary Search Tree(BBST)로 위 연산들이 일어남과 동시에 트리의 구조를 알아서 조절하는 자료구조입니다. 이를 통해서 트리가 unbalance하지 못하도록 하는 것이지요.

그러한 트리 중 유명한 것이 Red-Black Tree, AVL Tree, Splay Tree 등이 있으며, 이 포스트에서 다룰 내용은 Splay Tree입니다.

Rotate and Splay

BBST를 이해하기 위해서 알아야 할 제일 기본적인 연산은 Rotate입니다. 이 연산은 이진트리의 inorder 순서는 유지하면서 트리의 구조를 바꿔줍니다. 어떤 노드 x에 rotate 연산을 취하면 x의 높이가 1 낮아지면서 트리 전체의 inorder는 유지하도록 합니다.

아래는 rotate연산이 어떻게 트리를 바꾸는지 보여주는 그림입니다.

Rotate(x)

Splay Tree는 rotate 연산에 더해서 Splay라는 연산을 추가적으로 사용해서 트리를 치우치지 않도록 유지합니다.

CRUD 연산이 발생한 노드에 대해서 해당 연산이 끝난 뒤에 splay연산을 수행합니다. 놀랍게도 이것만으로도 트리는 치우치지 않게 됩니다.

그럼 이 splay연산이 뭔지 알아보죠. 어떤 노드 x에 대해서 splay 연산을 취한다면 x가 속하는 트리에서 x를 해당 트리의 루트로 만들어줍니다. 이 과정은 일련의 rotate들로 inorder를 유지하면서 가능합니다.

아래는 splay 연산의 예시를 그림으로 나타낸 것입니다.

Splay(x)

이 연산이 어떤 과정을 통해 이루어지는지 자세히 알아봅시다.

Break Down Splay

Splay 연산의 상세한 과정을 설명하기 위해서 notation을 정리하겠습니다.

• x : splay 대상 노드
• p : x의 부모 노드
• g : p의 부모 노드(존재할 경우)

Splay는 x가 본인이 속하는 트리의 root가 될 때까지 x에 대해서 Splaying-step을 반복합니다.

Splaying-step은 다음과 같은 세 가지 케이스가 있습니다.

Case 1(Zig step)

p가 root일 경우입니다. rotate(x)를 수행합니다.

Case 2(Zig-Zig step)

g가 존재하며 x와 p가 둘 다 left child이거나 right child일 경우입니다.

rotate(p), rotate(x)의 순서로 rotate를 수행합니다.

Case 3(Zig-Zag step)

g가 존재하며, x가 left child이고 p가 right child이거나, 그 반대일 경우입니다.

rotate(x)를 두 번 수행합니다.

각 케이스를 그림으로 살펴봅시다.

Case 1 Zig step

일반적인 rotate를 하는 것과 동일한 상황입니다. rotate(x)를 수행하면 x는 root가 되고 Splay 연산은 종료됩니다.

Zig Step

Case 2 Zig-Zig Step

x와 p가 둘 다 같은 방향의 자식일 경우입니다. rotate(p)를 먼저 수행하고 rotate(x)를 수행합니다.

Zig-Zig step

Case 3 Zig-Zag step

x와 p가 서로 다른 방향의 자식일 경우입니다. rotate(x)를 두 번 수행합니다.

Zig-Zig step

Splay 연산은 정말 단순하게도 연산 대상인 노드 x가 root가 될 때까지 위 과정을 반복합니다.

Amortized Time Complexity

놀랍게도 각 연산을 수행할 때마다 연산의 대상 노드(Delete라면 그 부모)에 대해서 splay를 수행하는 것만으로도 기본 연산들의 시간 복잡도는 amortized $O(\log{n})$이 됩니다.

우리가 일반적으로 얘기하던 시간 복잡도와는 다른 말이 하나 붙었습니다. amortized라는 단어가 붙음으로 의미가 어떻게 바뀌는 것일까요?

어떤 연산의 amortized time complexity라는 것은 연산 한 번에 대한 시간 복잡도가 아니라 해당 연산의 최악의 경우에 해당하는 연산 순서열(operation sequence)를 수행했을 때의 연산의 평균적인 시간복잡도를 말합니다.

여기서 최악의 경우라는 것은 어떤 알고리즘에서 최악의 시간 복잡도가 나올 수 있는 경우를 말합니다. 퀵소트의 최악의 경우의 시간복잡도가 $O(n^2)$인 것처럼요

위에서 최악의 연산 순서열을 수행했을 때의 연산의 평균적인 시간 복잡도라고 말했는데 이것은 평균 시간 복잡도와 분명히 다른 개념입니다.

흔히 말했던 평균 시간 복잡도라는 것은 최악의 경우(Worst Case), 최고의 경우(Best Case)를 포함한 모든 경우에 대해서 연산 시간을 측정했을 때, 그 경우 모두에 대해서 평균을 취한 것을 말합니다.

amortized time complexity는 최악의 경우인 연산 순서열을 수행했을 때, 각 operation의 평균 시간 복잡도를 말합니다. 최악의 경우이기 때문에 이것은 연산의 upper bound로도 사용할 수 있겠죠.

최악의 경우인 연산 순서열이 어려울 수도 있으니 예시를 하나 생각해봅시다.

비어있는 BST에 대해서 1부터 n까지 차례대로 삽입을 하면 선형적으로 트리가 구성될 것입니다. 그리고 $n$에 대한 접근이 $n$번 발생하는 총길이 $2n$의 연산 순서열이 있다고 합시다.

이러면 전체 시간복잡도는 $O(n^2)$일 것이고 각 연산의 시간복잡도는 $O(n)$이 됩니다. 이런 것이 최악의 연산 순서열이 될 것입니다.

이런 경우에 대해서 Splay Tree는 각 연산의 평균적인 시간 복잡도가 $O(\log n)$임을 보장해준다는 것입니다.

How to Calculate Amortized Time

이제 Amortized Time Complexity를 어떻게 계산하는지 알아보고 Splay 연산의 시간복잡도를 계산해봅시다.

Amortized Time Complexity를 계산하기 위해서는 Potential Function $\Phi$를 정의해야 합니다. 이 함수는 어떤 자료구조의 상태를 수치로 바꿔주는 함수입니다.

이 퍼텐셜 함수를 사용해서 어떤 연산의 amortized time을 정의합니다.

$a$를 amortized time, $t$를 실제 연산시간이라고 하면 아래와 같이 정의됩니다.
$$
a = t + \Phi'-\Phi
$$
$\Phi'$는 어떤 연산을 수행한 뒤의 퍼텐셜이고 $\Phi$는 연산을 수행하기 전의 퍼텐셜입니다.

$m$개의 연산을 처리했을 때의 amortized time을 식으로 나타내면 아래와 같습니다.
$$
\begin{aligned}
\sum^ma_i&=\sum^m(t_i+\Phi_i-\Phi_{i-1}) \\
&=\sum^mt_i+\Phi_m-\Phi_0
\end{aligned}
$$
이 때, $\Phi_0$는 초기 퍼텐셜이고 $a_i, t_i, \Phi_i$는 각각 $i$번째 연산을 했을 때의 amortized time, 실제 시간(actual time), 퍼텐셜입니다.

이 식으로부터 우리는 $m$개의 연산을 수행한 뒤의 퍼텐셜 변화가 0보다 크거나 같다면 amortized time은 actual time의 upper bound가 되는 것을 알 수 있습니다.

Amortized time of Splay

BST에서 기본 연산들의 시간은 접근하고자 하는 노드의 깊이에 비례합니다. 그리고 Splay 또한 root로 만들기 위해서는 해당 노드의 깊이에 비례한 수행시간을 가질 것입니다.

따라서, 러프하게 말하자면 splay연산의 시간복잡도와 기본 연산들의 시간복잡도 자체는 같을 것입니다.

이제 Splay의 시간 복잡도가 amortized $O(\log{n})$임을 증명하려고 합니다.

이를 위해서 BST의 퍼텐셜 $\Phi$를 정의하고 notation들을 정리하고 갑시다.

• $S(x)$ : $x$를 루트로 하는 서브트리의 크기
• $r(x)$ : $\log_2 S(x)$, 이 값을 노드 $x$의 $rank$라고 하겠습니다.
• $\Phi$ : 퍼텐셜함수입니다. 모든 노드의 $rank$의 합이 BST의 퍼텐셜입니다.
• $\Phi(T)$ : 트리 $T$의 퍼텐셜
• $a(o)$ : 연산 $o$의 amortized time
• $t(o)$ : 연산 $o$의 actual time

그리고 위 기호들에 $'$가 찍혀 있으면 어떤 연산을 수행한 뒤의 값을 나타냅니다.

어떤 연산의 시간복잡도를 알기 위해서는 연산 시간을 계산해야겠지요. 그리고 연산 시간을 계산하기에 앞서서 기본 연산을 정해야 합니다.

우리는 rotate연산을 기본 연산으로 정하겠습니다.

Splay는 일련의 Splaying-step으로 이루어집니다. 그리고 Splaying-step은 3가지 경우가 있었으며, 각 경우에 대해서 amortized time을 계산해봅시다.

중요한 점입니다. 지금부터 계산할 것은 amortized time complexity가 아닌 amortized time입니다. 그리고 목표는 이 amortized time의 upper bound입니다.

Case 1(Zig step)

p가 root일 경우입니다. rotate(x)를 수행합니다. 연산 전후의 퍼텐셜 변화를 그림과 수식으로 살펴봅시다.

$$
\begin{aligned}
\Phi &= r(x) + r(p)+\Phi(A)+\Phi(B)+\Phi(C) \\
\Phi' &= r'(x) + r'(p)+\Phi(a)+\Phi(B)+\Phi(C)
\end{aligned}
$$

여기서 x와 p외에는 rank가 변하지 않는 것을 확인할 수 있습니다.

이제 Zig step의 amortized time을 $a=t+\Phi' - \Phi$로 구해봅시다.

그리고 그 upper bound도 구해봅시다.
$$
\begin{aligned}
a(Zig\text{ }step)&=t(Zig\text{ }step)+\Phi'-\Phi \\
&=1+r'(x)+r'(p)-r(x)-r(p) \\
&=1+r'(p)-r(x) \quad (\because r'(x)=r(p)) \\
&\le1+(r'(x)-r(x)) \quad (\because r'(p) \le r'(x)) \\
&\le 1+3(r'(x)-r(x))
\end{aligned}
$$

$1 + 3(r'(x)-r(x))$는 $a(Zig\text{ }step)$의 upper bound라고 말할 수 있습니다. 굳이 3을 넣은 것은 다른 케이스들과의 통일성을 위해서입니다.

Case 2(Zig-Zig step)

g가 존재하며, x와 p가 둘 다 left child거나, right child일 경우입니다.

이번에도 연산 전후의 퍼텐셜을 봅시다.

$$
\begin{aligned}
\Phi&=r(x)+r(p)+r(g)+\Phi(A)+\Phi(B)+\Phi(C)+\Phi(D) \\
\Phi'&=r'(x)+r'(p)+r'(g)+\Phi(A)+\Phi(B)+\Phi(C)+\Phi(D)
\end{aligned}
$$

이것을 다시 또 수식에 넣어보면 아래와 같이 수식이 정리됩니다.

$$
\begin{aligned}
a(Zig\text{-}Zig\text{ }step)&=t(Zig\text{-}Zig\text{ }step)+\Phi'-\Phi \\
&=2+r'(x)+r'(p)+r'(g)-r(x)-r(p)-r(g) \\
&=2+r'(p)+r'(g)-r(x)-r(p) \quad (\because r'(x)=r(g)) \\
&\le 2+r'(x)+r'(g)-2r(x) \quad (\because r'(x) \ge r'(p), \; r(x) \le r(p))
\end{aligned}
$$

Zig step에서 나온 꼴로 upper bound를 찾고 싶은데 바로 보이지는 않습니다. 그래서 일단 우변에 $3(r'(x)-r(x))$를 놓아보죠. 그러면 아래와 같이 수식들을 정리할 수 있습니다.

$$
\begin{aligned}
\text{Claim : }2+r'(x)+r'(g)-2r(x) \le 3(r'(x)-r(x))
\end{aligned}
$$

$$
\begin{aligned}
2r'(x) - r(x) - r'(g) \ge 2 \\
r'(x)-r(x)+r'(x)-r'(g) \ge 2 \\
\log_2{\frac{S'(x)}{S(x)}}+\log_2{\frac{S'(x)}{S'(g)}} \ge 2 \\
\log_2{\frac{(S(A)+S(B)+S(C)+S(D)+3)^2}{(S(A)+S(B)+1)(S(C)+S(D)+1)}} \ge 2
\end{aligned}
$$

갑자기 $r(x), S(x)$가 나와서 당황하셨다면 위의 notation 정리를 살펴보신 뒤에 심호흡을 하고 천천히 살펴보시면 $r(x)$의 정의에 따라 식을 대입하고 그림과 맞춰보면 이해가 될 거 같습니다.

마지막으로 정리한 부등식에 있는 로그 안의 식을 좀 변형하는 것으로 위 주장을 아래와 같이 증명할 수 있습니다. 증명은 제가 전부 했으면 좋았겠지만 막혀서 오픈카톡방에 질문을 드렸더니 Lawali님이 도와주셨습니다.

\begin{gather}
\log_2{\frac{(S(A)+S(B)+S(C)+S(D)+3)^2}{(S(A)+S(B)+1)(S(C)+S(D)+1)}} \ge 2 \\ \\
\begin{aligned}
x&=S(A)+S(B)+1, \quad x \ge 1 \\
y&=S(C)+S(D)+1, \quad y \ge 1
\end{aligned}
\end{gather}
\begin{aligned} \\
\frac{(S(A)+S(B)+S(C)+S(D)+3)^2}{(S(A)+S(B)+1)(S(C)+S(D)+1)}&=\frac{(x+y+1)^2}{xy} \\
&\gt \frac{(x+y)^2}{xy} = \frac{y}{x}+\frac{x}{y}+2 \\
&\ge \;\; 4
\end{aligned}

이걸로 $3(r'(x)-r(x))$는 $a(Zig\text{-}Zig \; step)$의 upper bound라는 원래 주장을 증명했습니다.

Case 3 Zig-Zag step

g가 존재하며, x가 left child고 p가 left child이거나 그 반대일 경우입니다. 이번에도 연산 전후의 퍼텐셜을 살펴봅시다.

$$
\begin{aligned}
\Phi&=r(x)+r(p)+r(g)+\Phi(A)+\Phi(B)+\Phi(C)+\Phi(D) \\
\Phi'&=r'(x)+r'(p)+r'(g)+\Phi(A)+\Phi(B)+\Phi(C)+\Phi(D)
\end{aligned}
$$

여기서 해야할 일은 Case 2에서 했던 일과 동일합니다. 수식을 정리하고 $c(r'(x)-r(x))$ 꼴의 upper bound를 찾습니다.

$$
\begin{aligned}
a(Zig\text{-}Zag\text{ }step)&=t(Zig\text{-}Zag\text{ }step)+\Phi'-\Phi \\
&=2+r'(x)+r'(p)+r'(g)-r(x)-r(p)-r(g) \\
&\le 2+r'(p)+r'(g)-2r(x) \quad (\because r'(x) = r(g), \; r(x) \le r(p))
\end{aligned}
$$

$$
\begin{gather}
\text{Claim : }2+r'(p)+r'(g)-2r(x) \le 2(r'(x)-r(x)) \\
\\
2r'(x)-r'(p)-r'(g) \ge 2 \\
r'(x)-r'(p) + r'(x)-r'(g) \ge 2 \\
\log_2{\frac{S'(x)}{S'(p)}} + \log_2{\frac{S'(x)}{S'(g)}} \ge 2 \\
\log_2{\frac{(S(A)+S(B)+S(C)+S(D)+3)^2}{(S(A)+S(B)+1)(S(C)+S(D)+1)}} \ge 2
\end{gather}
$$

여기까지 Splaying step의 3가지 경우에 대해서 amortized time을 구하고 그 upper bound를 구했습니다. 이를 정리하면 아래와 같습니다.

$$
\begin{aligned}
a(Zig\text{-}Zag\text{ }step(x)) &\le 2(r'(x)-r(x)) \\
a(Zig\text{-}Zig\text{ }step(x)) &\le 3(r'(x)-r(x)) \\
a(Zig\text{ }step(x)) &\le 1+3(r'(x)-r(x)) \\
a(Splaying\text{-}step(x)) &\le 1+3(r'(x)-r(x))
\end{aligned}
$$

Splaying step의 upper bound를 구했습니다. 우리가 원래 목표로 했던 Splay의 amortized time의 upper bound에 더 가까워 졌어요

Splay 연산이 총 $d$개의 Splaying step으로 구성되었다고 합시다. 그러면 $d-1$개의 Zig-Zag 혹은 Zig-Zig가 있고 마지막에 Zig를 한번 하고 끝나게 됩니다.

그러면 Spaly의 amortized time은 다음과 같이 나타낼 수 있습니다.

$$
a(Splay) = \sum^{d-1}(a(Zig\text{-}Zag \; step) \lor a(Zig\text{-}Zig \; step))+a(Zig \; step)
$$

우리가 주목해야할 부분은 Splaying step이 모두 같은 노드 $x$에 대해서 이뤄진다는 점입니다. 이 때문에 현재 스텝의 $r(x)$와 이전 스텝의 $r'(x)$는 모두 상쇄되고 마지막의 $r'(x)$와 제일 처음의 $r(x)$만 남습니다.

그리고 마지막 Zig step의 x는 root이기 때문에 이 점을 이용해서 식을 정리하면 아래와 같습니다.

$$
\begin{gather}
\begin{aligned}
a(Splay) &= \sum^{d-1}(a(Zig\text{-}Zag \; step) \lor a(Zig\text{-}Zig \; step))+a(Zig \; step) \\
\\
&\le \; 3(r(root)-r(x)) + 1 \\
&\le 3\log_2\frac{S(root)}{S(x)} + 1
\end{aligned}
\end{gather}
$$

우변에서 $\log_2\frac{S(root)}{S(x)} \le \log_2n$이기 때문에 Splay의 amortized time은 $O(\log n)$임을 알 수 있습니다.

이렇게 Splay 연산의 amortized 시간복잡도를 증명했습니다.

증명을 시작하기 전에 BST의 기본 CRUD 연산들과 Splay의 시간복잡도가 왜 같을지에 대해서 직관적으로만 설명했습니다. 그리고 저 자신도 저정도로만 받아들이고 있기 때문에 왜 그런가에 대한 엄밀한 증명은 원 논문을 참고해주시기 바랍니다.

시간복잡도의 증명도 원 논문의 증명을 그대로 따라간 것입니다. 다만, 차이점은 $S(x)$에 대해서 살짝 정의가 다를 뿐입니다. 원 논문은 여기를 참고해주시면 될 거 같습니다.

스플레이 트리의 실제 구현이나 PS에서 어떻게 쓰는지에 대한 기본 내용은 아마 쓰지 않을 거 같습니다. 

실제 코드와 구현, 쓰임새는 Cubelover님의 블로그나 JusticeHui님의 블로그를 참고하시면 좋을 거 같습니다.

긴 글 읽어주셔서 감사합니다.  :)