首页 > 《计算机教育》 > 2013年17期 > “伸展树——一种高效的索引树”教学设计

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

在线阅读下载PDF 导出详情

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

DOI ojzpwylr45/1266094

作者张铭

机构地区不详

出处《计算机教育》 2013年17期

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

分类 [自动化与计算机技术][计算机科学与技术]

出版日期 2013年12月22日（中国期刊网平台首次上网日期，不代表论文的发表时间）