伸展树（Splay Tree），也叫分裂树或摊平树，是一种自平衡的二叉查找树。它在插入、删除、查找等操作中，通过伸展（Splay）操作保持树的平衡，使得树的高度始终保持在 O(log n)。它具有较高的查找、插入、删除等操作的性能，因此被广泛应用于计算机科学中。
伸展树的操作包括：插入、删除、查找、最大值、最小值等。下面是一个简单的伸展树操作过程：
- 插入：在伸展树中插入一个新节点，首先将节点插入到普通二叉查找树的适当位置。然后，通过旋转和重新伸展操作，使得树重新恢复平衡。
- 删除：在伸展树中删除一个节点，首先在普通二叉查找树中删除节点。然后，通过旋转和重新伸展操作，使得树重新恢复平衡。
- 查找：在伸展树中查找一个节点，通过普通二叉查找树进行查找。由于伸展树的高度始终保持在 O(log n)，因此查找的时间复杂度为 O(log n)。
- 最大值和最小值：在伸展树中获取最大值和最小值，通过遍历树的最左和最右子树得到。
在实际应用中，伸展树主要用于以下场景： - 频繁进行插入、删除、查找等操作的数据结构。
- 需要保持数据有序的数据结构。
- 需要快速找到最大值或最小值的数据结构。
推荐一个使用 Python 实现的伸展树（Splay Tree）的 Demo：
class SplayTreeNode:
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 insert(self, key):
if not self.root:
self.root = SplayTreeNode(key)
else:
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if not node:
return SplayTreeNode(key)
if key < node.key:
node.left = self._insert(node.left, key)
else:
node.right = self._insert(node.right, key)
node.parent = None
return self._splay(node)
def delete(self, key):
if self.root:
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if not node:
return node
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
else:
temp = self._find_min(node.right)
node.key = temp.key
node.right = self._delete(node.right, temp.key)
return self._splay(node)
def _find_min(self, node):
while node.left:
node = node.left
return node
def _splay(self, node):
if node.parent:
if node.parent.left == node:
node.parent.left = self._splay(node.right)
else:
node.parent.right = self._splay(node.right)
node.parent = None
return node
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if not node or node.key == key:
return node
if key < node.key:
return self._search(node.left, key)
else:
return self._search(node.right, key)
def min_value_node(self):
return self._min_value_node(self.root)
def _min_value_node(self, node):
while node.left:
node
