深入理解Splay树（Python语言Splay树实现方法详解）

Splay树的核心操作

Splay树主要有以下几种操作：

• 插入（Insert）：插入新节点后，将其伸展到根。
• 查找（Search）：查找节点后，若存在则伸展到根。
• 删除（Delete）：删除节点前先伸展到根，再进行删除。
• 伸展（Splay）：核心操作，通过旋转将目标节点移到根。

Python实现Splay树

下面我们用Python一步步实现Splay树。首先定义节点类：

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

接下来，我们实现Splay树类及其核心方法：

class SplayTree:    def __init__(self):        self.root = None    def _right_rotate(self, x):        y = x.left        x.left = y.right        y.right = x        return y    def _left_rotate(self, x):        y = x.right        x.right = y.left        y.left = x        return y    def _splay(self, root, key):        if not root or root.key == key:            return root        # Key lies in left subtree        if key < root.key:            if not root.left:                return root            # Zig-Zig (Left Left)            if key < root.left.key:                root.left.left = self._splay(root.left.left, key)                root = self._right_rotate(root)            # Zig-Zag (Left Right)            elif key > root.left.key:                root.left.right = self._splay(root.left.right, key)                if root.left.right:                    root.left = self._left_rotate(root.left)            return root.left if not root.left else self._right_rotate(root)        # Key lies in right subtree        else:            if not root.right:                return root            # Zig-Zig (Right Right)            if key > root.right.key:                root.right.right = self._splay(root.right.right, key)                root = self._left_rotate(root)            # Zig-Zag (Right Left)            elif key < root.right.key:                root.right.left = self._splay(root.right.left, key)                if root.right.left:                    root.right = self._right_rotate(root.right)            return root.right if not root.right else self._left_rotate(root)    def insert(self, key):        if not self.root:            self.root = Node(key)            return        self.root = self._splay(self.root, key)        if self.root.key == key:            return  # Already exists        new_node = Node(key)        if key < self.root.key:            new_node.right = self.root            new_node.left = self.root.left            self.root.left = None        else:            new_node.left = self.root            new_node.right = self.root.right            self.root.right = None        self.root = new_node    def search(self, key):        self.root = self._splay(self.root, key)        return self.root is not None and self.root.key == key    def delete(self, key):        if not self.root:            return        self.root = self._splay(self.root, key)        if self.root.key != key:            return  # Not found        if not self.root.left:            self.root = self.root.right        elif not self.root.right:            self.root = self.root.left        else:            temp = self.root.right            while temp.left:                temp = temp.left            self.root.right = self._splay(self.root.right, temp.key)            self.root.right.left = self.root.left            self.root = self.root.right

使用示例

现在我们来测试一下这个Splay树：

# 创建Splay树st = SplayTree()# 插入元素st.insert(10)st.insert(20)st.insert(30)st.insert(25)# 查找元素print(st.search(25))  # Trueprint(st.search(5))   # False# 删除元素st.delete(20)print(st.search(20))  # False

总结

通过本教程，你已经学会了如何用Python语言实现一个功能完整的Splay树。Splay树作为高效的自调整二叉搜索树，在实际工程中有广泛应用。希望这篇数据结构教程能帮助你打下坚实的基础！

如果你喜欢这类内容，欢迎继续关注更多关于数据结构与算法的深度解析！