Codeforce #765 (Div. 2)의 D. Binary Spiders를 풀다가 익혀두면 좋을 것 같은 trie의 활용법이 있어 정리해보고자 한다.

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)$시간에 수행 할 수 있다.