BST
$$a_i = c_i + \Phi(s_i) - \Phi(s_{i-1})$$

Splay tree는 비교적 간단한 동작 방식을 가지고 있다. 단순히 접근한 노드를 splay할 뿐인데 어떻게 각 쿼리가 (쿼리의 개수가 충분히 많을 때) $amortized \space O(\log n)$의 시간복잡도를 가질 수 있는 것일까? Potential method를 사용해 분할상환분석을 해보자.

BST(Binary Search Tree)의 한 종류인 Splay tree는, Splay라는 rotation 기반의 간단한 연산을 통해 쿼리를 할 때마다 Self Balancing을 수행한다. Splay tree는 다른 Balanced Binary Search Tree보다 구현이 (알고리즘 대회에서 구현 할 수 있을 만큼) 간단하고, 다양한 종류의 쿼리를 $amortized \space O(\log n)$시간에 수행 할 수 있다.