Splay Tree

1정의#

스플레이 트리는 자기 조정 이진 탐색 트리다. splay(x) 연산이 노드 x를 루트로 이동시키며, m번의 연산에 걸쳐 O(m log n) 분할 상환 시간 복잡도를 보장한다.

2구현#

노드는 부모 포인터 p와 자식 포인터 l, r을 가진다.

struct Node {
    Node *p, *l, *r;
};

rotate(x)는 x를 위로 한 칸 올린다. x가 오른쪽 자식이면 왼쪽 회전, 왼쪽 자식이면 오른쪽 회전이다.

bool is_right(Node *x) { return x->p->r == x; }

void rotate(Node *x) {
    Node *p = x->p, *g = p->p;
    bool right = is_right(x);
    Node *inner = right ? x->l : x->r;
    if (right) { x->l = p; p->r = inner; }
    else       { x->r = p; p->l = inner; }
    if (inner) inner->p = p;
    p->p = x; x->p = g;
    if (g) (g->l == p ? g->l : g->r) = x;
}

splay(x)는 g의 존재 여부와 x, p의 방향에 따라 세 경우로 분기한다.

• zig (p가 루트, g 없음): rotate(x).
• zig-zig (g 있음, x와 p가 같은 방향 자식): rotate(p) 후 rotate(x).
• zig-zag (g 있음, x와 p가 반대 방향 자식): rotate(x) 후 rotate(x).

void splay(Node *x) {
    while (x->p) {
        Node *p = x->p;
        if (p->p) {
            if (is_right(x) == is_right(p)) rotate(p);
            else rotate(x);
        }
        rotate(x);
    }
}

3시간 복잡도#

포텐셜 함수를 Φ = ∑_v rank(v)로 정의한다. 여기서 rank(v) = log₂ size(v)이고 size(v) = |subtree(v)|는 v의 서브트리 노드 수이다. size(v) ≥ 1이므로 rank(v) ≥ 0이고 Φ ≥ 0이다.

3.1보조 정리#

a, b ≥ 1이고 a + b ≤ c이면 log₂ a + log₂ b ≤ 2 log₂ c − 2이다.

AM-GM에 의해 ab ≤ ((a+b)/2)² ≤ (c/2)². 양변에 log₂를 취하면 성립한다. ■

---

splay는 zig, zig-zig, zig-zag 단계를 반복하며 x가 루트에 도달한다. 각 단계의 분할 상환 비용 â = 실제 비용 + ΔΦ를 구한다. 이하에서 프라임(')은 단계 직후의 값이다.

3.2zig#

회전 1회로 실제 비용 1. rank가 변하는 노드는 x, p뿐이다. x가 p 자리를 차지하므로 rank'(x) = rank(p)이고 rank'(p) ≤ rank'(x)이다. 따라서

â_zig = 1 + [rank'(x) − rank(x)] + [rank'(p) − rank(p)] ≤ 1 + [rank'(x) − rank(x)] ≤ 1 + 3[rank'(x) − rank(x)].

3.3zig-zig#

회전 2회로 실제 비용 2. rank가 변하는 노드는 x, p, g뿐이다. x가 g 자리를 차지하므로 rank'(x) = rank(g)이다.

WLOG x가 p의 왼쪽 자식, p도 g의 왼쪽 자식이라 하자. zig-zig 전 x의 왼쪽 서브트리를 A, 오른쪽 서브트리를 B, p의 오른쪽 서브트리를 C, g의 오른쪽 서브트리를 D라 하면

size(x) = size(A)+size(B)+1, size'(g) = size(C)+size(D)+1, size(g) = size(A)+size(B)+size(C)+size(D)+3.

따라서 size(x) + size'(g) = size(g) − 1 < size(g)이고, 보조 정리에 의해 rank(x) + rank'(g) ≤ 2 rank(g) − 2 = rank(g) + rank'(x) − 2. 따라서 [rank'(g) − rank(g)] ≤ [rank'(x) − rank(x)] − 2.

rank'(p) ≤ rank'(x)이고 rank(p) ≥ rank(x)이므로 [rank'(p) − rank(p)] ≤ [rank'(x) − rank(x)].

â_zig-zig = 2 + [rank'(x)−rank(x)] + [rank'(p)−rank(p)] + [rank'(g)−rank(g)] ≤ 3[rank'(x) − rank(x)].

3.4zig-zag#

회전 2회로 실제 비용 2. rank'(x) = rank(g)이다.

WLOG x가 p의 오른쪽 자식, p가 g의 왼쪽 자식이라 하자. zig-zag 전 x의 왼쪽 서브트리를 B, 오른쪽 서브트리를 C, p의 왼쪽 서브트리를 A, g의 오른쪽 서브트리를 D라 하면

size'(p) = size(A)+size(B)+1, size'(g) = size(C)+size(D)+1, size(g) = size(A)+size(B)+size(C)+size(D)+3.

따라서 size'(p) + size'(g) = size(g) − 1 < size(g)이고, 보조 정리에 의해 rank'(p) + rank'(g) ≤ 2 rank(g) − 2 = rank(g) + rank'(x) − 2. 따라서 rank'(p) + [rank'(g) − rank(g)] ≤ rank'(x) − 2.

rank(p) ≥ rank(x)이므로 [rank'(p) − rank(p)] + [rank'(g) − rank(g)] ≤ [rank'(x) − rank(x)] − 2

â_zig-zag = 2 + [rank'(x)−rank(x)] + [rank'(p)−rank(p)] + [rank'(g)−rank(g)] ≤ 3[rank'(x) − rank(x)].

---

zig 단계는 최대 하나이므로 â_splay ≤ 3[rank'(x) − rank(x)] + 1. splay 후 x는 루트가 되므로 rank'(x) = log₂ n이고, splay의 분할 상환 비용은 O(log n)이다. ■

4참고 문헌#

• Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652–686.