스플레이 트리 편집하기 (부분)

==개념==
스플레이 트리는 노드에 접근할 때마다 해당 노드를 루트로 올리는 회전 연산(splaying)을 수행한다. 이로 인해 자주 접근하는 노드는 루트 근처에 있게 되어 이후 접근이 빨라진다.

스플레이 연산은 다음 세 가지 패턴을 기준으로 회전한다:
#'''Zig (지그)'''
#*대상 노드가 루트의 자식일 때 한 번의 회전
#'''Zig-Zig (지그-지그)'''
#*대상 노드와 부모가 모두 왼쪽 또는 오른쪽 자식일 때 두 번 연속 같은 방향으로 회전
#'''Zig-Zag (지그-재그)'''
#*대상 노드가 왼쪽 자식이고 부모가 오른쪽 자식이거나, 그 반대인 경우 → 교차 방향 회전
슈도 코드로 나타내면 아래와 같다<syntaxhighlight lang="python3">
splayStep(Node u):
    case 1 (Base Case): u의 조부모가 없음
        → rotate(u)
    
    case 2 (Outer Grandchild):
        → rotate(u.parent)
        → rotate(u)

    case 3 (Inner Grandchild):
        → rotate(u)
        → rotate(u)  # 두 번 연속 회전 (double rotation)
</syntaxhighlight>