作者：Vamei 出處：http://www.cnblogs.com/vamei 歡迎轉載，也請保留這段聲明。謝謝！
伸展樹會在一次搜尋後，對樹進行一些特殊的操作。這些操作的理念與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
zig-zig operation
在伸展樹中，zig-zig操作(基本上)取代了AVL樹中的單旋轉。通常來說，如果上面的樹是失衡的，那麼A、B子樹很可能深度比較大。相對于單旋轉(想一下單旋轉的效果)，zig-zig可以将A、B子樹放在比較高的位置，進而減小樹總的深度。
下面我們用一個具體的例子示範。我們将從樹中搜尋節點2：
Original
zig-zag (double rotation)
zig (single rotation at root)
上面的第一次查詢需要n次操作。然而經過一次查詢後，2節點成為了根節點，樹的深度大減小。整體上看，樹的大部分節點深度都減小。此後對各個節點的查詢将更有效率。
伸展樹的另一個好處是将最近搜尋的節點放在最容易搜尋的根節點的位置。在許多應用環境中，比如網絡應用中，某些固定内容會被大量重複通路(比如江南style的MV)。伸展樹可以讓這種重複搜尋以很高的效率完成。
運作結果:
4
splay tree, m operations: mlog(n)