“伸展树—一种高效的索引树”教学设计

摘要：数据结构设计的重要目标之一是提高操作速度，特别是检索速度。局部平衡的红黑树、平衡的AVL树等二叉搜索树具有良好的检索性能，非常适合于基于内存的索引，但为防止树形结构退化为线性结构，在插入和删除结点时经常需要旋转，维护数据结构的操作比较复杂。文章阐述伸展树在检索过程中通过自动调整结构，使访问最频繁的结点靠近树结构的根，从而减少访问代价，指出伸展树可以作为各种线性序列的索引组织方法，能在一些需要高效索引的大工程中加以运用。

关键词：数据结构；索引；二叉搜索树；伸展树

1.在数据结构与算法课程中的定位和前测知识点

数据结构涉及逻辑、存储和运算3个维度。数据的存储结构主要有顺序、链接、索引和散列4种方法。数据的运算主要是对单个数据的增、删、查、改，或对整体数据的排序、索引和检索。有效的索引可以加快运算速度，可以说索引是数据结构与算法的重要内容Ⅲ。

二叉搜索树是一种非常有效的内存索引，但可能面临退化为线性结构的情况。改进二叉搜索树比普通二叉树更能提高检索效率，在现实中有广泛的应用。以往的数据结构教材更多地介绍AVL平衡二叉树，目前有不少教材开始介绍更易于实现应用的、更广泛的红黑树。

图灵奖获得者Tarjan和他的学生在1985年发明的伸展树（Splay Tree），作为一种自组织的数据结构，其操作简便，易于编写，统计性能高效，有良好的运用前景。

伸展树是用于索引的一种特殊二叉搜索树，只是改进BST性能的一组规则，而不是一种全新的数据结构。在伸展树中，数据随检索而采用这些操作规则来调整位置，目标是把刚检索的结点调整到根。

伸展树是一种自组织的数据结构，即它能随着检索等操作而发生结构的变化。伸展树中基本操作的均摊代价是O（logn）。

前测知识点要求如下，可以根据需要给学生补充：

（1）二叉搜索树BST的性质：中序遍历下结点关键码有序，左旋、右旋基本操作；

（2）二叉搜索树BST的插入、删除、查找算法；

（3）AVL树、红黑树的简单定义。

2.学习目标

（1）掌握伸展树的概念；

（2）伸展树的索引作用；

（3）伸展树的实现和简单应用；

（4）伸展树的均摊时间效率。

3.知识点和学时分配

理论授课0.5学时。

主讲教师可以根据学生的状况、教师的科研背景等对某些方面进行扩展并引导学生，以适当扩大学生的涉猎面。

4.重点和难点

（1）伸展树的旋转。伸展树旋转分为单旋转（zig右旋、zag左旋）、一字形双旋（zig-zig、zag-zag）和之字形双旋转（zig-zag、zag-zig）。

（2）伸展树的实现。伸展树的实现很简单，最基础的是Splay（x，f）函数，即将一个结点x旋转到其某个祖先f的下面。就是从x结点向上看两个结点（父亲、祖父），如果没有祖父则单旋转，如果有祖父则根据x与父亲、祖父的方向，来判断是一字形还是之字形双旋转。

（3）伸展树的应用。一个简单的应用是求x的前驱y，可以先把x旋转到根，然后顺着根的左子孩子的右链，一直向右走到头，最后那个结点就是所求的y。伸展树可以作为各种线性序列的索引组织方法。

5.授课提示

开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想和比较性能，培养学生的创新意识和创新能力。

伸展树在搜索过程中自动调整结构，但是不能保证树的高度。伸展树旋转的目的是使访问最频繁的结点靠近树结构的根，从而减少访问代价。教师可结合动画进行讲解，并介绍一些实例体现伸展树的特点和用途。

6.练习与扩展

融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合应用型的习题和上机题，帮助学生更好地掌握排序算法的基本原理，训练学生的创新思维能力训练、工程实践能力。

本讲可以安排2道算法类作业题和1道小型综合设计型实习题。

算法类作业有：

（1）通过二叉搜索树的找最大最小操作实现双端队列（http：///problem？id=3481）；

（2）用伸展树实现add，insert，delete，min等操作（http：///problem？id=3580）。

利用伸展树存储文件中单词词频可以作为一个小型综合设计题布置给学生。

图1显示了一个短文件的结点树。扫描一个文本文件，并计算出这一文件中每个词的词频。为简化起见，略去标点符号，按照字典排列的顺序对单词排序，并忽略大小写，如man’s将被当成man和s。类似地，分隔符也被忽略，如pre-existence被当做pre和existence。用一棵BST作为一个文件中单词的存储结构，并用伸展技术对这棵树进行辅助维护，以使输入流中的下一个单词出现在树中接近于根的位置的几率较大。

对于半伸展树、动态伸展树等变种，我们给出如下扩展阅读建议：

（1）Daniel Sleator和Robert Tarian的文章《Self-Adjusting Binary Search Trees》，ACM，1985，32（3）：652-686。

（2）Daniel Sleator和Robe～Tarjan的文章《A Data Structure for Dynamic Trees》，Computre and System Science，1983，26（3）：362-391。

（3）Wiki的伸展树词条（http：//en，wikipedia，org/wiki/Splay tree）。

7.结语

数据结构与算法课程的主要目标是训练学生数据结构设计、算法思想、创新思维能力和工程实践能力，而伸展树在保持数据结构性质、算法操作性能方面起到非常重要的作用，伸展树可以作为各种线性序列的索引组织方法，在一些需要高效索引的大工程中加以运用。