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