资源描述：
《论文国家队杨思雨》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、伸展树的基本操作与应用安徽省芜湖一中杨思雨目录【关键字】2【摘要】2【引言】2【伸展树的基本操作】2伸展操作Splay(x,S)3伸展树的基本操作4时间复杂度分析5【伸展树的应用】7【总结】8【参考书冃】9【附录】9【关键字】伸展树基本操作应用【摘要】木文主要介绍了伸展树的基本操作以及其在解题中的应用。全文可以分为以下四个部分。第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高，进而引出了在时间复杂度上更为优秀的伸展树。第二部分介绍了伸展树的基木操作。并给出了对伸展树时
2、间复杂度的分析和证明，指岀伸展树的各种基木操作的平摊复杂度均为0(logn),说明伸展树是一种较平衡的二叉杏找树。第三部分通过一个例子介绍了仲展树在解题屮的应用，并将它与其它树状数据结构进行了对比。第四部分指出了伸展树的优点，总结全文。【引言】二叉查找树(BinarySearchTree)能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n各节点的完全二叉树，这些操作的最坏情况运行时间
3、为O(logn)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为0(n)。而有些二叉査找树的变形，其基木操作在最坏情况下性能依然很好，比如红黑树、AVL树等等。本文将要介绍的伸展树(SplayTree),也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(logn)o所以从某种意义上说，伸展树也是一种平衡的二义查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。【伸展树的基本操作】仲展树是二义查找树的一种
4、改进，与二义查找树一样，伸展树也具有有序性。即伸展树中的每一个节点X都满足：该节点左子树中的每一个元素都小于X,而其右子树中的每一个元素都人于X。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)o伸展操作Splay(x,S)仲展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别处理：情况一：节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig(右旋)操作；如果x是y的右孩子，则我们
5、进行一次Zag£左旋)操作。经过旋转，x成为二叉查找树S的根节点，调整结束。如图1所示图1情况二：节点x的父节点y不是根节点，y的父节点为z,且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。如图2所示图2情况三：节点x的父节点y不是根节点，y的父节点为z,x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次Zig-Zag操、作或者Zag-Zig操作。如图3所示图3如图4所示,执行Splay(l,S),我们将元素1调整到了伸展树
6、s巴聲鸞再枚行Solav(2S)如图5所示，我们从直观上可以看出在经过调整后，伸展树比舌来繆秦為2图而伸展操作的过程并不复杂，只需要根据情况进行旋转就可以了，而三种旋转都是由基本得左旋和右旋组成的，实现较为简单。图4Splay⑴S)图5Splay(2,S)伸展树的基本操作利用Splay操作，我们可以在伸展树S上进行如下运算：(1)Find(x,S)：判断元素x是否在伸展树S表示的有序集屮。首先，与在二叉查找树屮的查找操作一样，在伸展树屮查找元素X。如果X在树中,则再执行Splay(x,S)调整伸展树。(2)Insert(x
7、,S)：将元素x插入伸展树S表示的有序集中。首先，也与处理普通的二叉查找树一样，将x插入到伸展树S中的相应位置上，再执行Splay(x,S)o(3)Delete(x,S)：将元素x从伸展树S所表示的有序集屮删除。首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩了或只有一个孩了，那么直接将X删去，并通过Splay操作，将x节点的父节点调整到伸展树的根节点处。否则，则向下查找x的后继y,用y替代x的位置，最后执行Splay(y,S),将y调整为伸展树的根。(4)Join(Sl,S2)：将两个伸展树S1与S2合并成
8、为一•个伸展树。其中S1的所有元素都小于S2的所有元素。首先，我们找到伸展树S1中最大的一个元素x,再通过Splay(x,Sl)将x调整到伸展树S1的根。然后再将S2作为x节点的右子树。这样，就得到了新的仲展树So如图6所示ZIG-ZIGZAC图6(5)Split(x,S)：以x为界，将伸展树S分离为两
