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

伸展树Splay Tree详解目录引言伸展树的基本概念伸展操作伸展树的操作插入操作查找操作删除操作时间复杂度分析伸展树与其他平衡二叉搜索树的比较应用场景代码实现示例总结引言伸展树Splay Tree是一种自调整的二叉搜索树由Daniel Sleator和Robert Tarjan在1985年提出。它通过一种称为伸展splay的特殊操作将最近访问的节点移动到根节点附近从而提高后续访问的效率。与传统的平衡二叉搜索树如AVL树、红黑树不同伸展树不保证树在任何时刻都保持平衡。相反它通过动态调整树的结构使得频繁访问的节点更靠近根节点从而在长期运行中实现良好的平均性能。伸展树的基本概念节点结构伸展树的每个节点包含以下信息键值Key左子节点Left Child右子节点Right Child父节点Parent伸展树的特点自调整性通过伸展操作最近访问的节点会被移动到根节点附近局部性原理利用程序访问的局部性提高频繁访问节点的访问速度摊还时间复杂度虽然单次操作可能较慢但摊还时间复杂度为O(log n)简单性实现相对简单不需要存储平衡因子或颜色信息伸展操作伸展操作是伸展树的核心它通过一系列旋转将目标节点移动到根节点。伸展操作通常分为三种情况1. Zig单旋转当目标节点的父节点是根节点时进行单旋转右旋转Zigy x / \ / \ x C -- A y / \ / \ A B B C左旋转Zagy x / \ / \ A x -- y C / \ / \ B C A B2. Zig-Zig双旋转同向当目标节点、其父节点和祖父节点都在同一方向时进行双旋转左-左情况LLz x / \ / \ y D -- A y / \ / \ x C B z / \ / \ A B C D右-右情况RRz x / \ / \ A y -- y D / \ / \ B x z C / \ / \ C D A B3. Zig-Zag双旋转异向当目标节点、其父节点和祖父节点不在同一方向时进行双旋转左-右情况LRz x / \ / \ y D -- y z / \ / \ / \ A x A B C D / \ B C右-左情况RLz x / \ / \ A y -- z y / \ / \ / \ x D A B C D / \ B C伸展树的操作插入操作伸展树的插入操作分为以下步骤按照二叉搜索树的规则找到插入位置插入新节点对新插入的节点执行伸展操作将其移动到根节点查找操作伸展树的查找操作分为以下步骤按照二叉搜索树的规则查找目标节点如果找到目标节点执行伸展操作将其移动到根节点如果未找到目标节点对最后访问的节点执行伸展操作删除操作伸展树的删除操作分为以下步骤查找要删除的节点如果找到节点执行伸展操作将其移动到根节点删除根节点并将左右子树合并对新的根节点执行伸展操作时间复杂度分析伸展树的时间复杂度分析基于摊还分析查找操作摊还时间复杂度为O(log n)插入操作摊还时间复杂度为O(log n)删除操作摊还时间复杂度为O(log n)虽然单次操作的最坏情况时间复杂度可能达到O(n)但由于伸展操作的自我调整特性频繁访问的节点会被移动到根节点附近从而在长期运行中保持良好的性能。伸展树与其他平衡二叉搜索树的比较特性伸展树AVL树红黑树平衡保证无严格平衡近似平衡插入/删除复杂度简单复杂中等查找性能局部性优化稳定稳定实现复杂度低中等高额外空间无平衡因子颜色信息适用场景频繁访问局部数据通用平衡树通用平衡树应用场景缓存系统利用局部性原理提高热点数据的访问速度文件系统优化频繁访问的文件和目录内存管理管理频繁使用的内存块网络路由优化路由表的查找性能数据库索引优化热点数据的索引访问代码实现示例以下是一个简单的伸展树Python实现classSplayTreeNode:def__init__(self,key):self.keykey self.leftNoneself.rightNoneself.parentNoneclassSplayTree:def__init__(self):self.rootNonedefright_rotate(self,x):yx.left x.lefty.rightify.right:y.right.parentx y.parentx.parentifnotx.parent:self.rootyelifxx.parent.right:x.parent.rightyelse:x.parent.lefty y.rightx x.parentydefleft_rotate(self,x):yx.right x.righty.leftify.left:y.left.parentx y.parentx.parentifnotx.parent:self.rootyelifxx.parent.left:x.parent.leftyelse:x.parent.righty y.leftx x.parentydefsplay(self,x):whilex.parent:ifnotx.parent.parent:ifxx.parent.left:self.right_rotate(x.parent)else:self.left_rotate(x.parent)elifx.parent.leftxandx.parent.parent.leftx.parent:self.right_rotate(x.parent.parent)self.right_rotate(x.parent)elifx.parent.rightxandx.parent.parent.rightx.parent:self.left_rotate(x.parent.parent)self.left_rotate(x.parent)elifx.parent.leftxandx.parent.parent.rightx.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):nodeSplayTreeNode(key)yNonexself.rootwhilex:yxifnode.keyx.key:xx.leftelse:xx.right node.parentyifnoty:self.rootnodeelifnode.keyy.key:y.leftnodeelse:y.rightnode self.splay(node)defsearch(self,key):xself.root lastNonewhilexandx.key!key:lastxifkeyx.key:xx.leftelse:xx.rightifx:self.splay(x)returnxiflast:self.splay(last)returnNonedefdelete(self,key):nodeself.search(key)ifnode:self.splay(node)left_subtreenode.left right_subtreenode.rightifleft_subtree:left_subtree.parentNoneifright_subtree:right_subtree.parentNoneifleft_subtree:self.rootleft_subtree max_leftself.maximum(left_subtree)self.splay(max_left)max_left.rightright_subtreeifright_subtree:right_subtree.parentmax_leftelse:self.rootright_subtreereturnnodereturnNonedefmaximum(self,node):whilenode.right:nodenode.rightreturnnode总结伸展树是一种独特而强大的数据结构它通过自我调整的特性在保持简单实现的同时提供了良好的平均性能。其核心思想是利用程序的局部性原理将频繁访问的节点移动到根节点附近从而提高后续访问的速度。伸展树的主要优势包括实现简单不需要存储额外的平衡信息在频繁访问局部数据的场景下表现优异摊还时间复杂度保证为O(log n)适用于缓存、文件系统等需要优化热点数据访问的场景虽然伸展树在最坏情况下可能表现不佳但在实际应用中由于其自调整特性通常能够提供比传统平衡树更好的性能特别是在具有访问局部性的应用场景中。