对于一颗普通的二叉树构建完成后，对每个节点的访问时间平均为O(logN)，那么对同一个节点的M次访问则需要用时O(M*logN)，但一般对某一个节点的访问具有重复性，即第一次访问后，后续的第二次第三次还会继续访问该节点。那么有无一种操作让第一次访问时O(logN)后，后续的访问这个节点只需要O(1)次的方案呢？这就是这一节需要介绍的伸展树。

伸展树的基本思想就是当一个节点被访问后，它就要经过一系列的AVL树的旋转被放到根上。但伸展树不要求保留树的高度平衡信息。如下图示例，在一个二叉树上，节点在【1，2，3，4，5，6，7】中查找key为6的节点，为了让后续访问节点6的O(1)的时间，在访问后，对节点6进行旋转并推向根节点。该旋转虽然把节点6推到了根节点，但对节点5的访问时间从之前的O(5)变成了O(6)，如果一次对每个节点进行访问一遍，树又回到了原始状态。

图1：

当然，通过对访问节点的向上旋转操作做一下修改，将极大的优化了其他节点的平均访问时间。通过分析并结合AVL平衡树的旋转特点，总结如下情况：

• 如果节点X的父节点是根节点，则只需要对X节点与根节点旋转一次即可。

• 如果节点X有父亲节点P和祖父节点G，那么存在2种情况讨论，分别为一字型（左X-左P-左G，右G-右P-右X）和之字型（左G-左P-右X，右G-右P-左X）

图2：

图3：

根据上面的旋转的修改之后，重新把图1，调整后如下，可以看出，采用一字型或者之字型调整中，树没有以前那么深了。

图4：

那么按照上面说的伸展树的思想，不管是查找还是插入，都需要先沿根节点往下遍历一次，然后再从底向上再做一次遍历把查找到的节点进行一次旋转到根节点。有无存在只需要一次路径访问上执行旋转操作就解决了的？这就是下面要介绍的方案。

可以对旋转操作总结如下3种场景

• 单旋转场景如下图，根为Y的子树，变为中间树的新根，节点X和X的右子树则成为子树R中最小项的左儿子；

• 一字型旋转场景如下图，根为Z的子树，变为中间树的新根，节点Y和X进行一次旋转后挂载右子树R中最小项的左儿子下面；

• 之字型旋转，同理底部节点子树Z成为中间数的新根，并把节点X和节点Y分别附属到右子树R和左子树L上；

对于树T，存在当前节点X，它是子树的根；子树L是树T中不属于X节点且小于X节点的集合，子树R是树T中不属于X且大于X节点的集合。初始情况下，X就是树T的根，子树L和子树R为空树。

以一个具体的如下例子进行讲解，在树中查找value为18的节点，初始化的时候L和R都是空树，中间树的树根为12，由于根节点12->右节点25->左节点20，为之字型场景，通过上图总结的操作进行旋转。依次多次旋转后，value为18的节点成为了根节点，对节点18的左子树放入L的最右子项，把节点18的右儿子放入R的最左子项，并最终得到伸展后的以查询节点18为根节点的新的二叉树。

下面代码实现如下：