本文为转载文章
作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！
我们讨论过，树的搜索效率与树的深度有关。二叉搜索树的深度可能为n，这种情况下，每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度，单次搜索的复杂度为log(n) (以上参考纸上谈兵 AVL树)。我们下面看伸展树(splay tree)，它对于m次连续搜索操作有很好的效率。
伸展树会在一次搜索后，对树进行一些特殊的操作。这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度。但伸展树并没有AVL的平衡要求，任意节点的左右子树可以相差任意深度。与二叉搜索树类似，伸展树的单次搜索也可能需要n次操作。但伸展树可以保证，m次的连续搜索操作的复杂度为mlog(n)的量级，而不是mn量级。
具体来说，在查询到目标节点后，伸展树会不断进行下面三种操作中的一个，直到目标节点成为根节点 （注意，祖父节点是指父节点的父节点）
1. zig: 当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。
zig
2. zig-zag: 当目标节点、父节点和祖父节点成"zig-zag"构型时，进行一次双旋转，将目标节点调整到祖父节点的位置。
zig-zag
3. zig-zig：当目标节点、父节点和祖父节点成"zig-zig"构型时，进行一次zig-zig操作，将目标节点调整到祖父节点的位置。
zig-zig
单旋转操作和双旋转操作见AVL树。下面是zig-zig操作的示意图:
zig-zig operation
在伸展树中，zig-zig操作(基本上)取代了AVL树中的单旋转。通常来说，如果上面的树是失衡的，那么A、B子树很可能深度比较大。相对于单旋转(想一下单旋转的效果)，zig-zig可以将A、B子树放在比较高的位置，从而减小树总的深度。
下面我们用一个具体的例子示范。我们将从树中搜索节点2：
Original
zig-zag (double rotation)
zig-zig
zig (single rotation at root)
上面的第一次查询需要n次操作。然而经过一次查询后，2节点成为了根节点，树的深度大减小。整体上看，树的大部分节点深度都减小。此后对各个节点的查询将更有效率。