文章目录
  1. 展开

伸展树的实现相对AVL树更简单，且不用为每个节点保持平衡因子。虽然在最坏的情况下查找需要的时间是O(N)，但是对伸展树的每次操作的摊还代价为O(logN)。

展开

伸展树在查找操作时，顺便将查找的节点通过旋转操作移到根节点处。对查找的非根节点X，若X的父节点是根节点，则将X与根节点作旋转即可。

否则，X拥有父节点P与祖父节点G，此时分类讨论。

之字型

即(1)X是P的右子节点，P是G的左子节点；(2)X是P的左子节点，P是G的右子节点；此时，使用对应的双旋转进行展开操作。

对于情况(1)，对其进行如下图所示的双旋转。

 

对于情况(2)同理；如此直到X为根节点或X为根的子节点。

一字型

即(1)X是P的左子节点，P是G的左子节点；(2)X是P的右子节点，P是G的右子节点；此时，使用对应的双旋转进行展开操作。

对于”一字型”的情况，展开操作更为复杂，需要三次旋转；如图所示。