Data Structures I - Splay Tree

Self-balancing의 대표적인 사례로 시작합시다!

Posted Aug 18, 2025 Updated May 29, 2026

Splay Tree rotations

By Moonlight_

13 min read

Data Structures I - Splay Tree

안녕하세요, 이번에는 스플레이 트리라는 알고리즘에 대한 소개로 돌아왔습니다. 더불어 파이썬 구현도 같이 소개하면서 진행할 계획입니다! (앞으로 고난도 알고리즘을 파이썬으로 풀어헤치는 프로젝트를 많이 할 예정입니다. Pypy의 속도가 느려서 어느 정도 고난도 문제에서 사장된 문제가 있는데, 파이썬이 익숙한 사람은 이게 더 좋을 수도 있으니까..특히 작성자 본인이..ㅋㅋ)

다음의 글을 작성하는데 다음의 문서/사이트들을 참조함을 밝힙니다.

What is splay tree

우선 평범한 BST에서 출발하자. BST의 고질적인 문제점인 $1,2,..n$으로 넣으면 트리 높이가 $O(n)$가 된다는 문제점이 있기에 balancing이 필요한데, 이를 사용하는 대표적 트리 중 하나에 대해 splay tree에 대해 알아볼 것이다. 그런데 balancing을 관련 정보 없이 계속 balanced되게 유지할 수 있게 있을까?

Why we need splay tree?

File Management: 파일 관리는 일반적으로 tree hierachy 식으로 진행되는데, file이 insert/delete될 때 우리의 file tree 안에 최대한 빠르게 삽입하고 싶다. 또한, access를 자주하는 파일의 경우 tree의 가장 위에 있는 것이 좋기에, 이런 관점에서 splay tree가 사용됨. (실제로 Windows NT에서 사용됨)

Intuition

Splay Tree의 다음 특징이 상당히 아름다운데,

스스로 balance를 함. AVL Tree에서의 정의는 아니고, BST에서 balancing 하는 기능을 추가했다고 보면 된다. (BBST의 일종)
Balance 관련해서 트리에서 노드외 저장해야 하는 정보는 없음. 이는 노드 관련 작업을 할 시에 rotation이라는 과정을 하기 때문.
검색/삽입/삭제의 시간복잡도는 amortized $O(\log n)$. 즉 비싼 operation이 있을 순 있으나 평균적으로 보면 이보다 훨씬 저렴한 operation이 많기에 괜찮다!

Intro

간단하게 요약을 하자면 다음의 과정으로 rotation을 정리할 수 있다.

target이 있다면 우선 BST와 같이 target을 검색함. 있으면 일단 좋은 거고, 없으면 검색에서 가장 마지막으로 도달한 노드를 일단 생각함.
해당 노드를 root로 보내는 rotation 작업을 진행함.

잠시 복습을 위해 rotation의 방향에 대한 diagram을 첨부했다.

Notation: $x$: 현재 다루는 node, $p$: $x$의 parent, $g$: $x$의 grandparent.

Zig

Zig는 $p$가 root일때(즉, $g$가 존재하지 않을 때) 사용된다. 이런 경우는

$x$가 $p$의 왼쪽 자손이면 $p$에 오른쪽으로 회전.
$x$가 $p$의 오른쪽 자손이면 왼쪽으로 회전.

그리고 Zig 후 $x$는 root에 도달하니, 이는 마지막 operation일 것이다.

Zig-Zig

이제는 $x$가 $p$와 $g$ 모두 보유하고 있다고 생각하자. 그렇다면 가능한 배치가 left-left, left-right, right-left, right-right 총 4가지가 있는데, 이 중에서 Zig-Zig는 left-left, right-right에 대한 규칙을 다룬다. 일반적을 잃지 않고 left-left의 사례를 생각해보자. (right-right는 대칭적으로 처리하면 되기 때문)

우선 $g$를 right rotation 시키고, $p$에서 left rotation을 해서 $x$를 위로 올리면 된다.

Zig-Zag

이번에는 left-right, right-left 케이스를 보자. 일반성을 잃지 않고 left-right 케이스만 보자.

우선 $p$에서 left rotation을 하고, $g$에서 right rotation을 진행하면 된다.

3가지 경우 모두 그림으로 정리해보았다.

Implementation

Goals

우리는 특정 node를 splay한다는 걸 그 node가 root가 아니고, root로 옮기는 것을 말한다. 결국에는 다음의 과정을 따를 것이다:

$x$가 root의 자손이면, Zig를 실행한다.
$x$가 left-left, right-right child이면 Zig-Zig를 실행한다.
$x$가 left-right, right-left child이면 Zig-Zag를 실행한다.
$x$가 root인지 확인. 아니다면, 1~3 과정을 반복한다. (물론 1~3은 상호배타적이다)

Setting the Tree: Node

  


    class Node:
        def __init__(self,key=None,left=None,right=None,parent=None):
            self.key = key
            self.left = left
            self.right = right
            self.parent = parent

Setting the Tree: Rotations

  


    def rotate(x):
        p = x.parent #부모노드
        if p == None:
            return # already root
        if x == p.left:
            b = x.right
            p.left = b
            x.right = p
        else:
            b = x.left
            p.right = b
            x.left = p
        # parent restructuring
        x.parent = p.parent
        p.parent = x
        if b != None:
            b.parent = p
        if x.parent != None:
            if p == x.parent.left:
                x.parent.left = x
            else:
                x.parent.right = x
        else:
            root = x       

Node의 정의와 $x$가 root인 경우는 이해가 너무 쉬운데, 그 뒤에 코드가 너무 짧다! 일단 우리가 말한 걸 잘 요약하면 저게 되긴 하는데, 설명하자면

$x$가 부모의 왼쪽 자손인 경우, $x$의 오른쪽 자손을 $p$의 왼쪽에 붙여줘야 하며, 그 이후 $x$의 오른쪽 자손을 $p$로 바꿔준다.
$x$가 부모의 오른쪽 자손인 경우, $x$의 왼쪽 자손을 $p$의 오른쪽에 붙여줘야 하며, 그 이후 $x$의 왼쪽 자손을 $p$로 바꿔준다.

이렇게 12번 줄까지의 이해를 완료하였다. 자손쪽 관리는 됐는데, 일단 추가로 고쳐야 하는 게 두 가지가 있다.

$x,p,b$ 부모 관계.

여긴 쉽다. 단순히 $x$의 부모를 $p$의 부모로 업데이트하고, $p$의 부모를 $x$로 바꾸면 된다. 만일 $b$가 존재한다면, $b$의 부모는 $p$로 바뀌는 것이다!

조부모의 left/right 갱신

결국 모든 노드가 가진 트리의 정보가 동일하게 적용되려면, 조부모의 left 혹은 right도 갱신되었으니 이 또한 바꿔줘야 한다. 조부모 노드가 존재한다면, $x$와 $p$의 역할이 바뀐 것이기에 $p$가 있던 left/right의 위치를 $x$의 위치로 변경시켜주면 된다.

만일 현재 위치에서 $x$의 부모(즉, 기존의 $p$의 부모)가 없다면, $x$는 root로 온 것이다!

Setting the Tree: Splay

  


def splay(x):
    while x.parent != None: #x가 root가 될때까지
        p = x.parent #부모 노드
        g = p.parent #조부모 노드
        if g != None:
            if not ((x == p.left)^(p == g.left)):
                rotate(p)
            else:
                rotate(x)
        rotate(x)

나머지 경우가 꽤 깔끔하게 정리되었는데, 왜 그럴까? rotate 함수는 해당 인자를 부모와 바꿔주면서 rotate 해주는 함수이다.

Zig의 경우는 rotate(x) 한 번 하면 끝나며, 이는 Zig의 목적에 부합한다.
Zig-Zig는 $p$와 $g$의 위치를 바꾸면서 rotate하고, 그 후 $x$와 $p$의 위치를 바꾸면서 해결되었다. 판정은 둘 다 왼쪽에 있거나, 오른쪽에 있으면 0인 조건문을 xor로 구현하여 해결하였다.
Zig-Zag는 Zig-Zig가 아닌 경우로, rotate(x)를 두 번 하면 해결 된다.

Q: 어차피 Zig-Zig도 rotate(x)로 해결되는 게 아닌가? 그럼 걍 rotate(x)만 해도 충분한 건 아닌가??

A: 이건 시간복잡도 이슈이긴 한데, 만일 단순 rotate만 할시 O(N)의 시복이 나오기에, Zig-Zig/Zag의 케이스 분할이 필수적이다. 자세한 건 후술.

Basic Operations

드디어 rotation과 splay의 setup이 끝났다! 이제 이진 탐색 트리의 기본 작업에 이들을 엮는 일만 남았다.

  


class SplayTree:
    def __init__(self):
        self.root = None
    def _splay(self,x):
        # we implemented this!
    def insert(self,key):
        #???
    def find(self,key):
        #???
    def delete(self,key):
        #???

Insertion

삽입을 한 후, 중요한 점은 해당 노드를 splay하는 것이다.

  


def insert(self,key):
    p = tree.root
    if not p: #Empty tree
        x = Node(key)
        self.root = x
        return
    while True:
        if key == p.key:
            return # Duplicate, pass
        elif key<p.key:
            if not p.left:
                x = Node(key)
                p.left = x
                x.parent = p
                self._splay(x) #New!
                return
            p = p.left
        else:
            if not p.right:
                x = Node(key)
                p.right = x
                x.parent = p
                self._splay(x)
                return
            p = p.right

Search

마찬가지로 마지막 검색 노드를 splay해준다.

  


def find(self,key):
    p = tree.root
    if not p:
        return False #empty tree
    while p:
        if key == p.key:
            break #Found!
        if key < p.key: # Smaller: look at left subtree
            if not (p.left):
                break #No subtree, get out
            p=p.left
        if key > p.key:
            if not (p.right):
                break
            p=p.right
    self._splay(p) #Splay final search node
    return (key == p.key) # If found, return True

Deletion

순서가 앞과 다른데, 우선 삭제할 노드를 splay해서 root로 보낸 후 삭제를 한다.

  


def delete(self,key):
    p = self._find(key)
    if not p:
        return # No? At least put closest deletion node to root
    if (p.left and p.right):
        self.root = p.left
        self.root.parent = None #Make left child new root
        x = tree.root
        while x.right:
            x = x.right
        x.right = p.right
        p.right.parent = x # Move right subtree to below left subtree
    elif p.left: #only left child
        self.root = p.left
        self.root.parent = None
    elif p.right: #only right child
        self.root = p.right
        self.root.parent = None
    else:
        self.root = None #empty tree

이제 기본적 구현은 모두 끝났다! 다음 시간에는 이를 활용한 여러 구현 및 문제를 해결해보자.

Algorithms, PS

Data Structures

This post is licensed under CC BY 4.0 by the author.