스플레이 트리

IT 위키

스플레이 트리(splay tree)는 이진 탐색 트리(binary search tree)의 일종으로, 자주 접근하는 노드를 루트에 가깝게 이동시켜 전체적인 접근 효율을 높이는 자기 조정형(self-adjusting) 트리이다. 1985년 Sleator와 Tarjan에 의해 제안되었으며, 평균적으로 효율적인 탐색 성능을 보장한다.

  • 결국 기본 형태는 BST이지만, Look Up, Insert, Delete 등 트리 사용이 있을 때 마다 재조정을 함으로써 평균적인 효율을 개선한 트리이다. AVL 트리처럼 트리 모양 자체의 제약 조건은 없으면서도 높은 효율을 자랑한다.

1 개념[편집 | 원본 편집]

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

스플레이 연산은 다음 세 가지 패턴을 기준으로 회전한다:

  1. Zig (지그)
    • 대상 노드가 루트의 자식일 때 한 번의 회전
  2. Zig-Zig (지그-지그)
    • 대상 노드와 부모가 모두 왼쪽 또는 오른쪽 자식일 때 두 번 연속 같은 방향으로 회전
  3. Zig-Zag (지그-재그)
    • 대상 노드가 왼쪽 자식이고 부모가 오른쪽 자식이거나, 그 반대인 경우 → 교차 방향 회전

슈도 코드로 나타내면 아래와 같다

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)

2 연산[편집 | 원본 편집]

  • 검색(search)
    • 노드를 찾은 후 splay 연산을 통해 해당 노드를 루트로 올림
  • 삽입(insert)
    • 일반적인 BST 방식으로 삽입 후, 그 노드를 루트로 splay
  • 삭제(delete)
    • 삭제할 노드를 splay한 뒤 루트에서 제거 → 두 서브트리를 합치는 과정 필요

3 구현 코드[편집 | 원본 편집]

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

class SplayTree:
    def __init__(self):
        self.root = None

    def _rotate(self, u):
        p = u.parent
        if p is None:
            return
        g = p.parent
        if u == p.left:
            p.left = u.right
            if u.right:
                u.right.parent = p
            u.right = p
        else:
            p.right = u.left
            if u.left:
                u.left.parent = p
            u.left = p
        p.parent = u
        u.parent = g
        if g:
            if g.left == p:
                g.left = u
            else:
                g.right = u
        else:
            self.root = u

    def _splay(self, u):
        while u.parent:
            p = u.parent
            g = p.parent
            if not g:
                self._rotate(u)  # Zig
            elif (u == p.left and p == g.left) or (u == p.right and p == g.right):
                self._rotate(p)  # Zig-Zig
                self._rotate(u)
            else:
                self._rotate(u)  # Zig-Zag
                self._rotate(u)

    def _subtree_min(self, node):
        while node.left:
            node = node.left
        return node

    def _subtree_max(self, node):
        while node.right:
            node = node.right
        return node

    def lookup(self, key):
        u = self.root
        last = None
        while u:
            last = u
            if key == u.key:
                break
            elif key < u.key:
                u = u.left
            else:
                u = u.right
        if last:
            self._splay(last)
        return last if last and last.key == key else None

    def insert(self, key):
        if not self.root:
            self.root = Node(key)
            return
        u = self.root
        p = None
        while u:
            p = u
            if key == u.key:
                self._splay(u)
                return
            elif key < u.key:
                u = u.left
            else:
                u = u.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
        self._splay(new_node)

    def delete(self, key):
        node = self.lookup(key)
        if not node or node.key != key:
            return
        L, R = node.left, node.right
        if L:
            L.parent = None
        if R:
            R.parent = None
        if not L:
            self.root = R
            return
        maxLeft = self._subtree_max(L)
        self._splay(maxLeft)
        maxLeft.right = R
        if R:
            R.parent = maxLeft
        self.root = maxLeft

    def delete_min(self):
        if not self.root:
            return None
        node = self._subtree_min(self.root)
        self._splay(node)
        min_key = node.key
        self.root = node.right
        if self.root:
            self.root.parent = None
        return min_key

    def split(self, key):
        self.lookup(key)
        if not self.root:
            return (None, None)
        if self.root.key <= key:
            right = self.root.right
            if right:
                right.parent = None
            self.root.right = None
            return (self.root, right)
        else:
            left = self.root.left
            if left:
                left.parent = None
            self.root.left = None
            return (left, self.root)

    def merge(self, other):
        if not self.root:
            self.root = other.root
            return
        if not other.root:
            return
        maxLeft = self._subtree_max(self.root)
        self._splay(maxLeft)
        maxLeft.right = other.root
        other.root.parent = maxLeft

4 성능[편집 | 원본 편집]

  • 각 연산의 최악 시간복잡도는 O(n)이지만, 평균적으로는 O(log n)
  • 암시적 캐싱 효과로 인해 자주 쓰이는 데이터는 빠르게 접근 가능
  • 모든 연산이 동일한 splay 연산으로 구성되므로 구현이 단순

예시

노드 20, 10, 30, 5, 15, 25, 35가 삽입된 트리에서 노드 5를 탐색하면, 5는 루트로 올라가고 구조가 재조정된다. 이후 노드 5에 재접근하면 O(1)에 가능할 수 있다.

5 장점[편집 | 원본 편집]

  • 최근에 접근한 노드에 더 빠르게 접근 가능
  • 명시적 균형 정보를 저장하지 않아도 트리가 자동으로 균형 잡힘
  • 삽입, 삭제, 탐색이 동일한 구조의 코드로 구현됨

6 단점[편집 | 원본 편집]

  • 균형 유지가 명시적이지 않아 트리 높이가 불안정할 수 있음
  • 특정 연산에 대해서는 AVL 트리, 레드-블랙 트리보다 느릴 수 있음

7 같이 보기[편집 | 원본 편집]

8 참고 문헌[편집 | 원본 편집]

  • Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652–686
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press
원본 주소 "https://itwiki.kr/index.php?title=스플레이_트리&oldid=40565"