Splay Tree

Splay Tree

• Data structure
• 2021년 6월 3일

Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리 1. 특징 구현이 단순 많이 접근한 노드에 대해서 빠른 접근이 가능하다 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다. AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다. 최악의 경우 높이가 선형, 즉 O(n)이 나올 수 있다. 세그먼트 트리로 이용이 가능하다. k번째 원소 찾기, 구간 합, lazy Propagation, 구간 뒤집기 모두 쉽게 할 수 있다. x노드를 접근한다면, splay를 통해 root로 올라오면서 x보다 작은 노드들은 Left에, 큰 노드들은 Right에 모이는 특성을 이용...