算法合集之《伸展树的基本操作与应用》

《算法合集之《伸展树的基本操作与应用》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2004国家集训队论文杨思雨伸展树的基本操作与应用安徽省芜湖一中杨思雨目录【关键字】.......................................................................................2【摘要】...........................................................................................2【引言】...............................

2、............................................................2【伸展树的基本操作】....................................................................2伸展操作Splay(x,S)....................................................................3伸展树的基本操作.................................

3、.....................................4时间复杂度分析..........................................................................5【伸展树的应用】............................................................................7【总结】.......................................................

4、....................................8【参考书目】...................................................................................9【附录】...........................................................................................9IOI2004国家集训队论文杨思雨【关键字】伸展树基本操作应用【摘要】本文主要介绍

5、了伸展树的基本操作以及其在解题中的应用。全文可以分为以下四个部分。第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高，进而引出了在时间复杂度上更为优秀的伸展树。第二部分介绍了伸展树的基本操作。并给出了对伸展树时间复杂度的分析和证明，指出伸展树的各种基本操作的平摊复杂度均为O(logn)，说明伸展树是一种较平衡的二叉查找树。第三部分通过一个例子介绍了伸展树在解题中的应用，并将它与其它树状数据结构进行了对比。第四部分指出了伸展树的优点，总结全文。【引言】二叉查找树（Bina

6、rySearchTree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n各节点的完全二叉树，这些操作的最坏情况运行时间为O(logn)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为O(n)。而有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、AVL树等等。本文将要介绍的伸展树（SplayTree），也是对二叉查找树的一种改进，虽然它并不能保证树

7、一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(logn)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。【伸展树的基本操作】伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。第2页共9页2IOI2004国家

8、集训队论文杨思雨伸展操作Splay(x,S)伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别处理：情况一：节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig（右旋）操作；如果x是y的右孩子