자료구조

Splay Tree

QCW-Yaho

2019년 11월 10일 • 7 min read

나는 야호다.

오늘은 Splay Tree에 대해 설명하겠다.

Splay Tree는 무엇인가

Splay Tree는 균형이진탐색트리(Balanced Binary Search Tree, BBST)의 한종류이다.

Splay Tree라는 이름이 붙은 건 Splay라는 재밌고도 신기한 연산을 사용하여 amortized $$O(log n)$$의 시간복잡도를 유지하기 때문이다.

설명에 앞서 균형이진탐색트리에 대해 잠깐 알아보고 가자.

이진탐색트리는 특정 데이터의 삽입, 삭제, 탐색이 가능한 자료구조이며, 각각의 노드를 기준으로 왼쪽에는 작은 데이터, 오른쪽에는 큰 데이터만 저장이 된다.

이런 조건을 만족하면서 트리를 만들어가면, 트리가 균형잡히지 않아졌을때, $$O(n)$$의 시간이 걸리게 되고 이를 해결하기 위해 self-balancing 과정을 진행하여 시간복잡도 $$O(log n)$$을 보장받는 자료구조가 바로 BBST가 되겠다.

혹시 이진탐색트리에 대해(BBST 말고) 구현하는 방법을 모른다면, 공부하고 오셈. 거기까지 설명하긴 귀찮...

Rotate

우선 대부분의 BBST는 Rotate연산을 기본으로 트리의 균형을 맞춘다. 이는 Rotate연산이 Tree의 inorder순회결과를 변경하지 않으면서 트리의 구조를 변경하는 연산이기 때문이다. Splay Tree 또한 Rotate를 사용한다.

Rotate(x)는 노드 x를 부모노드의 위치로 옮기는 작업이다.

Splay

Splay연산은 Splay tree의 핵심이 되는 연산으로, 특정 노드를 Rotate연산을 통해 루트 노드로 만들어주는 연산이다.

Splay(x)는 x의 노드를 다음 규칙에 의해 루트로 만드는 연산이다.

x가 루트라면 종료.
x의 부모가 루트라면 rotate(x)를 하고 종료.
x의 조부모를 g라고 하자.
3-1) g->p랑 p->x 방향이 같은 경우, rotate(p) 후에, rotate(x)를 한다. (Zig-Zig Step)
3-2) g->p랑 p->x 방향이 다른 경우, rotate(x) 후에, rotate(x)를 한다. (Zig-Zag Step)
1번으로 돌아가서 반복.

Splay Tree가 멋진 점은 일반 이진탐색트리와 똑같이 연산을 하면서, 연산 후에 Splay 연산을 한번씩만 해주면, amortized $$O(log n)$$이 된다는 점이다.

개쩜 ㄹㅇ 왜 되는지는 솔직히 잘 모른다. 난 그냥 받아들이고 쓰는중인데, 그림 좀 그려보면 $$O(log n)$$은 아니더라도 빠른 느낌은 든다. 대충 균형이 맞춰지는 그런 느낌.

추가) 이제 알았는데 여러분의 재미로 남긴다 ㅅㄱ

Insert, Find, Delete

이는 일반적인 이진탐색트리와 동일하며, 해당 연산을 진행한 뒤, 마지막으로 접근한 노드를 Splay 한번만 해주면 된다.

즉, Insert라면 삽입한 노드, Find라면 찾은 노드(못 찾았다면, 이진탐색으로 확인한 마지막 노드), Delete라면 삭제할 노드나 옮긴 노드 따위의 것을 적당히 splay하면서 진행하면 된다.

Kth element

C++에서는 STL map이나 set을 제공한다. 이는 이미 구현된 BBST이다. 그럼에도 우리가 PS에서 BBST를 구현하는 이유가 바로 Kth element 즉, k번째 원소를 찾는 연산을 $$O(logn)$$ 만에 할 수 있기 때문이다.

이를 구현하기 위해서는 이진탐색트리에서 각 노드별로 subtree의 노드의 개수를 저장하면 된다. 다시 이 그림을 보자.

자. 한번의 Rotate연산을 할때, P와 Q만이 자식의 정보가 바뀐다. 따라서, Rotate를 할때, P, Q 노드의 정보만 update해주면 된다.

구간 쿼리

자 kth element를 보고 구간쿼리가 가능하지 않을까? 하고 눈치챘을 수도 있지만 그러면 당신은 이미 쌉고인물이니 당장 팬티런을 끄고 유능한 일을 하러가라.

우리는 다음과 같이 주어진 구간 [L,R)에 해당하는 tree를 만들수 있다. 또한, 각 노드별로 서브트리의 구간에 해당하는 정보를 저장한다면 구간쿼리 쉽건웅!

'Splay 비슷하게'라는게 있는데, Splay 연산이 특정 노드를 루트로 만드는 연산이라면 여기서 'Splay 비슷하게'는 특정노드를 어떤 노드의 자식이 되게 만드는 녀석이다.

즉, Splay를 구현할때 애초에 인자를 두 개를 받아서 Splay(x,y)를 'x 노드를 y의 자식으로 만드는 연산'이라고 정의하고, 디폴트로 y=-1같은걸 넣어놓으면 구간쿼리를 위한 'Splay 비슷한'연산도 Splay 연산 코드를 그대로 이용할 수 있는것이다.

Lazy Propagation

물론 가능하다.

우리는 Segment Tree에서 Lazy를 떠올려보자. 어떤 구간 쿼리가 들어오면 그 구간에 해당하는 노드에 접근했을 때, Propagation을 진행시킨다.

똑같이 구간에 해당하는 노드에 접근했을 때, Propagation을 진행시키면 된다. Splay tree의 경우, Kth element의 시작에만 Propagtion을 진행해주면 충분하다.

구간 뒤집기

Splay Tree가 Segment Tree와 다른점은 바로 왼쪽 자식과 오른쪽 자식을 동적으로 바꿀수 있다는 점이고, 따라서 이를 이용하여 구간 뒤집기를 할 수 있다.

즉, 다음과 같은 쿼리가 가능하다는 것이다.

[L, R) 쿼리가 들어왔을 때, $$a_L, a_{L+1}, ..., a_{R-1}$$ 을 $$a_{R-1},..., a_{L+1}, a_L$$로 바꾼다.

우리는 Lazy Propagation이 가능하니 구간이 현재 뒤집힐 예정인지를 알려주는 lazy변수를 관리하면서, 뒤집힐 예정이라면 왼쪽 자식과 오른쪽 자식의 순서를 바꾼 후, 자식들에게 현재의 lazy를 전파해주면 된다.

결론

즉, 우리는 Segment Tree에서 할 수 있는 모든 것을 Splay Tree로 할 수 있고, 추가적으로 구간 뒤집기도 할 수 있는 것이다.

구현은 귀찮아서 안올림 ㅅㄱ