樹：伸展樹

我們知道AVL樹為了保持嚴格的平衡，是以在資料插入上會呈現過多的旋轉，影響了插入和删除的性能，此時AVL的一個變種，伸展樹（Splay）就應運而生了，我們知道萬事萬物都遵循一個“八二原則“，也就是說80%的人隻會用到20%的資料，比如說我們的“xx輸入法”，平常打的字也就那麼多，或許還沒有20%呢。

在伸展樹上的一般操作都基于伸展操作：假設想要對一個二叉查找樹執行一系列的查找操作，為了使整個查找時間更小，被查頻率高的那些條目就應當經常處于靠近樹根的位置。于是想到設計一個簡單方法， 在每次查找之後對樹進行重構，把被查找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉查找樹，它會沿着從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。

它的優勢在于不需要記錄用于平衡樹的備援資訊。

已知重構方法與伸展樹的重構方法

先前，已經存在兩種重構方法：

1、單旋：在查找完位于節點x中的條目i之後，旋轉連結x和其父節點的邊。（除非x就是樹根）

2、搬移至樹根：在查找完位于節點x中的條目i之後，旋轉連結x和其父節點的邊，然後重複這個操作直至x成為樹根。

splay tree的重構方法和搬移至樹根的方法相似，它也會沿着查找路徑做自底向上的旋轉，将被查找條目移至樹根。但不同的是，它的旋轉是成對進行的，順序取決于查找路徑的結構。為了在節點x處對樹進行splay操作，我們需要重複下面的步驟，直至x成為樹根為止：

1、第一種情況：如果x的父節點p(x)是樹根，則旋轉連接配接x和p(x)的邊。（這種情況是最後一步）

2、第二種情況：如果p(x)不是樹根，而且x和p(x)本身都是左孩子或者都是右孩子，則先旋轉連接配接p(x)和x的祖父節點g(x)的邊，然後再旋轉連接配接x和p(x)的邊。

3、第三種情況：如果p(x)不是樹根，而且x是左孩子，p(x)是右孩子，或者相反，則先旋轉連接配接x和p(x)的邊，再旋轉連接配接x和新的p(x)的邊。

在節點x處進行splay操作的時間是和查找x所需的時間成比例的。splay操作不單是把x搬移到了樹根，而且還把查找路徑上的每個節點的深度都大緻減掉了一半。

伸展樹的優勢

可靠的性能——它的平均效率不輸于其他平衡樹。

存儲所需的記憶體少——伸展樹無需記錄額外的什麼值來維護樹的資訊，相對于其他平衡樹，記憶體占用要小。

由于Splay Tree僅僅是不斷調整，并沒有引入額外的标記，因而樹結構與标準紅黑樹沒有任何不同，從空間角度來看，它比Treap、SBT、AVL要高效得多。因為結構不變，是以隻要是通過左旋和右旋進行的操作對Splay Tree性質都沒有絲毫影響，因而它也提供了BST中最豐富的功能，包括快速的拆分和合并，并且實作極為便捷。這一點是其它結構較難實作的。其時間效率也相當穩定，和Treap基本相當，常數較高。

伸展樹的缺點

伸展樹最顯著的缺點是它有可能會變成一條鍊。這種情況可能發生在以非降順序通路n個元素之後。然而均攤的最壞情況是對數級的——O(logn)

參考：

http://www.cnblogs.com/huangxincheng/archive/2012/08/04/2623455.html

http://baike.baidu.com/link?url=HPLz0KKZv3zqYom5uJ_Lxmmzbfx6EDSyR9NjOh_EJOhf3k145NgrHyjp0nQW9y4NiEDp4_s2tMH4HCDWEJlasK