SPLAY (1) 썸네일형 리스트형 Randomize Binary Search Trees, Treap INTRO 잘 아려진 BBST(Balanced Binary Search Tree : 균형이진탐색트리)의 종류로는 rb tree, b tree 등이 있습니다. 그러나 위의 rb tree와 같이 대부분의 연산을 \(O(logN)\)에 처리하는 트리는 동작 자체도 복잡하고 구현량이 많기 때문에 직접 구현해가며 PS에 사용하기 어렵습니다. (stl에 있는 것을 가져다 쓰면 좋겠지만 연산을 변형해야하는 경우도 존재하니까요) 그래서 삽입, 삭제 등의 연산에 amortized \(O(logN)\)의 시간복잡도를 가지며 상대적으로 구현량이 적은 Splay Tree를 가장 많이 사용합니다. 하지만 Splay Tree도 zig-zag step 등 헷갈릴만한 요소가 많아서 저는 Treap을 선호합니다. Treap은 일반적인.. 이전 1 다음
