学年计算机方向课程大二上数算实习splay

1、数据结构与算法伸展树采用高等教育：，蛟，赵海燕 编写，2008. 6 (“十一五”国家级规划)第十二章高级数据结构伸展树一种自组织数据结构数据随检索而调整位置汉字输入法的词表伸展树不是一个新数据结构，而只是改进 BST性能的一组规则保证的总代价不高，达到最令人满意的性能不能保证最终树高平衡2数据结构与算法第十二章高级数据结构展开(splaying)一次结点 (例如结点 x)，完成一次称为展开的过程入、检索时，把结点 x 移到 BST 的根结点x删除结点 x 时，把结点 x 的父结点移到根结点像在 AVL 树中一样，结点x的一次展开包括一组旋转(roion)调整结点 x、父结点、祖父结点的位置把

2、 x 移到树结构中的更3数据结构与算法第十二章高级数据结构单旋转 (single roion)x 是根结点的直接子结点时把结点 x 与它的父结点交换位置保持 BST 特性xyCABx、y 为结点，不是值大小，有大小顺序A、B、C 代表4数据结构与算法第十二章高级数据结构双旋转(double roion)双旋转涉及到结点 x结点 x 的父结点 (称为 y)结点 x 的祖父结点 (称为 z)把结点 x 在树结构中向上移两层一字形旋转 (zigzig roion)也称为同构调整 (homogeneous configuration)之字形旋转 (zigzag roion)也称为异构调整 (heter

3、ogeneous configuration)5数据结构与算法第十二章高级数据结构一字形旋转图示z结点x是y的结点y是z的结点结点DyxCAB6数据结构与算法一字形旋转图示yzxABCD7数据结构与算法第十二章高级数据结构之字形旋转图示zDyxABC8 数据结构与算法结点x是y的右子结点结点y是z的结点第十二章高级数据结构之字形旋转图示zDxyCBA9数据结构与算法第十二章高级数据结构之字形旋转图示xyzCBDA10 数据结构与算法第十二章高级数据结构之字形旋转图示xyzABCD11 数据结构与算法第十二章高级数据结构第十二章高级数据结构两种旋转的不同作用之字形旋转把新使的向根结点移动结构的高

4、度减1趋向于使树结构更加平衡一字形一般不会降低树结构的高度只是把新的向根结点移动12 数据结构与算法第十二章高级数据结构伸展树的调整过程一系列双旋转直到结点 x 到达根结点或者根结点的子结点如果结点x到达根结点的子结点进行一次单旋转使结点 x 成为根结点这个过程趋向于使树结构重新平衡使最频繁的结点靠近树结构的根层从而减少代价13 数据结构与算法伸展树的调整过程h(a-b-c)一字形旋转gIfHeAdGc(a, c)左转(a, b)左转BbCaDEF数据结构与算法14第十二章高级数据结构伸展树的调整过程hgIfHa-d-e之字形调整eAdGaBbFcECD15 数据结构与算法第十二章高级数据结构

5、伸展树的调整过程h(a-f-g)之字形旋转gI(a, g)右转Hf(a, f)左转eaAdbBGFcECD16 数据结构与算法第十二章高级数据结构伸展树的调整过程(a, h)右转h单旋转IafgeHAdGFBbcECD数据结构与算法17第十二章高级数据结构伸展树的调整过程ahfgIAdeHBbGFEcCD18 数据结构与算法伸展树与 AVL 树的差别伸展树与结点被的频率相关根据、删除、检索而动态地调整树的结构与频率无关AVL只与、删除的顺序有关19 数据结构与算法伸展树的效率n 个结点的伸展树进行一组m次操作mn时，总代价是、删除、查找操作)，当(O(mlogn)伸展树不能保证每一个单个操作是有效率的即每次操作的平均代价为O(logn)不要求掌握证明方法20 数据结