문제 링크

• http://icpc.me/1395

문제 링크

• http://icpc.me/12844

문제 링크

• http://icpc.me/7578

문제 링크

• http://icpc.me/8980

문제 링크

• http://icpc.me/2512

지난 글에서는 splay tree의 기본이 되는 두 가지 연산(rotate, splay)을 알아보았습니다.
이번 글에서는 splay tree에서 삽입/삭제/검색 연산이 어떻게 이루어 지는지 알아보도록 하겠습니다.

문제 링크

• http://icpc.me/2867

Splay Tree란?

이번 글은 균형 이진 탐색 트리(Balanced Binary Search Tree, BBST) 중 splay tree라는 자료 구조에 대한 설명입니다.
가장 자주 쓰이는 BBST는 레드 블랙 트리(Red-Black tree, RB Tree)이지만, 구현이 너무 복잡합니다.
그러나 이번에 소개할 splay tree는 구현이 쉽고 레드 블랙 트리에 버금가는 속도를 갖고 있기 때문에 STL을 못 쓰는 환경에서 유용하게 쓸 수 있습니다.

문제 링크

• http://icpc.me/15918

문제 링크

• http://icpc.me/3015