数据结构之伸展树（Splay Tree）详解

伸展树（Splay Tree）详解

目录

1. 引言
2. 伸展树的基本概念
3. 伸展操作
4. 伸展树的操作
   • 插入操作
   • 查找操作
   • 删除操作
5. 时间复杂度分析
6. 伸展树与其他平衡二叉搜索树的比较
7. 应用场景
8. 代码实现示例
9. 总结

引言

伸展树（Splay Tree）是一种自调整的二叉搜索树，由Daniel Sleator和Robert Tarjan在1985年提出。它通过一种称为"伸展"（splay）的特殊操作，将最近访问的节点移动到根节点附近，从而提高后续访问的效率。

与传统的平衡二叉搜索树（如AVL树、红黑树）不同，伸展树不保证树在任何时刻都保持平衡。相反，它通过动态调整树的结构，使得频繁访问的节点更靠近根节点，从而在长期运行中实现良好的平均性能。

伸展树的基本概念

节点结构

伸展树的每个节点包含以下信息：

• 键值（Key）
• 左子节点（Left Child）
• 右子节点（Right Child）
• 父节点（Parent）

伸展树的特点

1. 自调整性：通过伸展操作，最近访问的节点会被移动到根节点附近
2. 局部性原理：利用程序访问的局部性，提高频繁访问节点的访问速度
3. 摊还时间复杂度：虽然单次操作可能较慢，但摊还时间复杂度为O(log n)
4. 简单性：实现相对简单，不需要存储平衡因子或颜色信息

伸展操作

伸展操作是伸展树的核心，它通过一系列旋转将目标节点移动到根节点。伸展操作通常分为三种情况：

1. Zig（单旋转）

当目标节点的父节点是根节点时，进行单旋转：

右旋转（Zig）：

y x / \ / \ x C --> A y / \ / \ A B B C

左旋转（Zag）：

y x / \ / \ A x --> y C / \ / \ B C A B

2. Zig-Zig（双旋转，同向）

当目标节点、其父节点和祖父节点都在同一方向时，进行双旋转：

左-左情况（LL）：

z x / \ / \ y D --> A y / \ / \ x C B z / \ / \ A B C D

右-右情况（RR）：

z x / \ / \ A y --> y D / \ / \ B x z C / \ / \ C D A B

3. Zig-Zag（双旋转，异向）

当目标节点、其父节点和祖父节点不在同一方向时，进行双旋转：

左-右情况（LR）：

z x / \ / \ y D --> y z / \ / \ / \ A x A B C D / \ B C

右-左情况（RL）：

z x / \ / \ A y --> z y / \ / \ / \ x D A B C D / \ B C

伸展树的操作

插入操作

伸展树的插入操作分为以下步骤：

1. 按照二叉搜索树的规则找到插入位置
2. 插入新节点
3. 对新插入的节点执行伸展操作，将其移动到根节点

查找操作

伸展树的查找操作分为以下步骤：

1. 按照二叉搜索树的规则查找目标节点
2. 如果找到目标节点，执行伸展操作，将其移动到根节点
3. 如果未找到目标节点，对最后访问的节点执行伸展操作

删除操作

伸展树的删除操作分为以下步骤：

1. 查找要删除的节点
2. 如果找到节点，执行伸展操作将其移动到根节点
3. 删除根节点，并将左右子树合并
4. 对新的根节点执行伸展操作

时间复杂度分析

伸展树的时间复杂度分析基于摊还分析：

• 查找操作：摊还时间复杂度为O(log n)
• 插入操作：摊还时间复杂度为O(log n)
• 删除操作：摊还时间复杂度为O(log n)

虽然单次操作的最坏情况时间复杂度可能达到O(n)，但由于伸展操作的自我调整特性，频繁访问的节点会被移动到根节点附近，从而在长期运行中保持良好的性能。

伸展树与其他平衡二叉搜索树的比较

应用场景

1. 缓存系统：利用局部性原理，提高热点数据的访问速度
2. 文件系统：优化频繁访问的文件和目录
3. 内存管理：管理频繁使用的内存块
4. 网络路由：优化路由表的查找性能
5. 数据库索引：优化热点数据的索引访问

代码实现示例

以下是一个简单的伸展树Python实现：

classSplayTreeNode:def__init__(self,key):self.key=key self.left=Noneself.right=Noneself.parent=NoneclassSplayTree:def__init__(self):self.root=Nonedefright_rotate(self,x):y=x.left x.left=y.rightify.right:y.right.parent=x y.parent=x.parentifnotx.parent:self.root=yelifx==x.parent.right:x.parent.right=yelse:x.parent.left=y y.right=x x.parent=ydefleft_rotate(self,x):y=x.right x.right=y.leftify.left:y.left.parent=x y.parent=x.parentifnotx.parent:self.root=yelifx==x.parent.left:x.parent.left=yelse:x.parent.right=y y.left=x x.parent=ydefsplay(self,x):whilex.parent:ifnotx.parent.parent:ifx==x.parent.left:self.right_rotate(x.parent)else:self.left_rotate(x.parent)elifx.parent.left==xandx.parent.parent.left==x.parent:self.right_rotate(x.parent.parent)self.right_rotate(x.parent)elifx.parent.right==xandx.parent.parent.right==x.parent:self.left_rotate(x.parent.parent)self.left_rotate(x.parent)elifx.parent.left==xandx.parent.parent.right==x.parent:self.right_rotate(x.parent)self.left_rotate(x.parent.parent)else:self.left_rotate(x.parent)self.right_rotate(x.parent.parent)definsert(self,key):node=SplayTreeNode(key)y=Nonex=self.rootwhilex:y=xifnode.key<x.key:x=x.leftelse:x=x.right node.parent=yifnoty:self.root=nodeelifnode.key<y.key:y.left=nodeelse:y.right=node self.splay(node)defsearch(self,key):x=self.root last=Nonewhilexandx.key!=key:last=xifkey<x.key:x=x.leftelse:x=x.rightifx:self.splay(x)returnxiflast:self.splay(last)returnNonedefdelete(self,key):node=self.search(key)ifnode:self.splay(node)left_subtree=node.left right_subtree=node.rightifleft_subtree:left_subtree.parent=Noneifright_subtree:right_subtree.parent=Noneifleft_subtree:self.root=left_subtree max_left=self.maximum(left_subtree)self.splay(max_left)max_left.right=right_subtreeifright_subtree:right_subtree.parent=max_leftelse:self.root=right_subtreereturnnodereturnNonedefmaximum(self,node):whilenode.right:node=node.rightreturnnode

总结

伸展树是一种独特而强大的数据结构，它通过自我调整的特性，在保持简单实现的同时，提供了良好的平均性能。其核心思想是利用程序的局部性原理，将频繁访问的节点移动到根节点附近，从而提高后续访问的速度。

伸展树的主要优势包括：

• 实现简单，不需要存储额外的平衡信息
• 在频繁访问局部数据的场景下表现优异
• 摊还时间复杂度保证为O(log n)
• 适用于缓存、文件系统等需要优化热点数据访问的场景

虽然伸展树在最坏情况下可能表现不佳，但在实际应用中，由于其自调整特性，通常能够提供比传统平衡树更好的性能，特别是在具有访问局部性的应用场景中。