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

摘要：

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

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

分类号：G642(高等教育)

在线出版日期：2013-10-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：8-10