Splay Tree | Notion

Splay 트리는 이진 탐색 트리의 한 종류로, 자주 접근하는 노드를 루트에 가깝게 재배치하는 자가 조정(self-adjusting) 자료구조이다. 기본적인 아이디어는 접근한 노드를 일정한 규칙의 “rotate” 연산인 "splay" 연산을 통해 루트로 끌어올리는 것이다.

Splay 트리의 특징

자가 최적화: 자주 접근하는 요소는 트리의 상단에 위치하게 되어 빠른 접근이 가능하다.
단순한 구현: 복잡한 색상 태그(Red-Black 트리)나 높이 정보(AVL 트리)가 필요 없다.
비대칭 연산: 최악의 경우 시간복잡도는 O(n)이지만, 평균적(amortized)으로는 O(log n)이다.
캐싱 효과: 최근에 접근한 데이터에 다시 접근할 가능성이 높은 경우 효율적이다.

AVL 트리와 레드-블랙 트리와의 비교

특성	Splay 트리	AVL 트리	Red-Black 트리
균형 유지	자가 조정 (엄격한 균형 보장 없음)	엄격한 높이 균형	느슨한 높이 균형
최악의 경우 시간복잡도	O(n)	O(log n)	O(log n)
amortized	O(log n)	O(log n)	O(log n)
추가 저장 공간	없음	노드당 높이 정보	노드당 색상 정보
구현 복잡도	비교적 간단	복잡	매우 복잡
적합한 상황	자주 접근하는 요소가 일정한 패턴을 가질 때	검색이 많고 삽입/삭제가 적을 때	삽입/삭제가 빈번할 때

Splay 트리의 기본 연산

Rotate

rotate 함수는 특정 노드를 자신의 부모 위치로 옮기는 기능을 함
예시)

코드

def _rotate(self, node):
    # 회전할 노드의 부모와 조부모를 가져온다.
    parent = node.parent
    grand_parent = parent.parent

    # node가 parent의 왼쪽 자식인 경우 (Right Rotation)
    if parent.left == node:
        # 1. parent의 왼쪽 자식을 node의 오른쪽 서브트리로 만든다.
        parent.left = node.right
        # 2. node의 오른쪽 서브트리가 존재한다면, 그 서브트리의 부모를 parent로 설정한다.
        if node.right:
            node.right.parent = parent
        # 3. node의 오른쪽 자식을 parent로 만든다.
        node.right = parent
    # node가 parent의 오른쪽 자식인 경우 (Left Rotation)
    else:
        # 1. parent의 오른쪽 자식을 node의 왼쪽 서브트리로 만든다.
        parent.right = node.left
        # 2. node의 왼쪽 서브트리가 존재한다면, 그 서브트리의 부모를 parent로 설정한다.
        if node.left:
            node.left.parent = parent
        # 3. node의 왼쪽 자식을 parent로 만든다.
        node.left = parent

    # parent의 새로운 부모는 node가 된다.
    parent.parent = node
    # node의 새로운 부모는 기존의 grand_parent가 된다.
    node.parent = grand_parent
    
    # grand_parent가 존재하는 경우, 즉 parent가 루트가 아니었던 경우
    if grand_parent:
        # grand_parent와 node를 연결한다.
        if grand_parent.left == parent:
            grand_parent.left = node
        else:
            grand_parent.right = node
    # grand_parent가 없는 경우, 즉 parent가 루트였던 경우
    else:
        # node가 새로운 루트가 된다.
        self.root = node

회전에는 두 가지 유형이 있다: 오른쪽 회전과 왼쪽 회전.
Right Rotate
- Right Rotate는 특정 노드(x)를 기준으로 그 노드의 왼쪽 자식(y)을 위로 올리는 작업이다.
- 결과적으로 x는 y의 오른쪽 자식이 된다.
- 과정:
  1. 노드 x의 왼쪽 자식을 y라고 정의한다.
  2. y를 x의 자리로 올린다. 즉, y가 새로운 부모가 된다.
  3. x는 y의 오른쪽 자식이 된다.
  4. 이때 원래 y의 오른쪽 서브트리는 갈 곳을 잃게 되는데, 이 서브트리는 y보다는 크지만 x보다는 작으므로 x의 새로운 왼쪽 자식으로 완벽히 들어맞게 된다.
Left Rotate
- Left Rotate는 Right Rotate 연산과 대칭적으로 구현되며, 특정 노드(y)를 기준으로 그 노드의 오른쪽 자식을 위로 올리는 작업이다.
- 과정은 Right Rotate와 대칭적으로 구현되므로 생략한다.

Splay

Splay연산은 특정 노드를 루트로 만드는 연산으로 좌우 균형을 맞춰 amortized O(log n)의 연산을 가능토록한다

def _splay(self, node):
    # splay할 노드가 없으면 즉시 종료한다.
    if not node:
        return
        
    # 노드가 루트가 될 때까지 반복한다.
    while node.parent:
        parent = node.parent
        grand_parent = parent.parent
        
        # 부모가 루트인 경우 (Zig step)
        if not grand_parent:
            # node를 한 번만 회전시켜 루트로 만든다.
            self._rotate(node)
        # 조부모가 존재하는 경우
        else:
            # node와 parent가 같은 방향으로 연결된 경우 (Zig-Zig step)
            # (둘 다 왼쪽 자식이거나, 둘 다 오른쪽 자식)
            if (parent.left == node) == (grand_parent.left == parent):
                # 1. parent를 먼저 회전시킨다.
                self._rotate(parent)
                # 2. 그 다음 node를 회전시킨다.
                self._rotate(node)
            # node와 parent가 다른 방향으로 연결된 경우 (Zig-Zag step)
            else:
                # 1. node를 회전시킨다.
                self._rotate(node)
                # 2. node를 한 번 더 회전시킨다.
                self._rotate(node)
                
    # splay가 완료된 후, node를 트리의 새로운 루트로 설정한다.
    self.root = node