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

== 구현 코드 ==
<syntaxhighlight lang="python3">
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

</syntaxhighlight>