Can you summarize the following document?
        
  伸展樹的自我平衡使其擁有良好的效能,因為頻繁訪問的節點會被移動到更靠近根節點,進而獲得更快的訪問速度。

  伸展樹最顯著的缺點是它有可能會變成一條鏈。例如,在以非遞減順序訪問全部n個之後就會出現這種情況。此時樹的高度對應於最壞情況的時間效率,操作的實際時間效率可能很低。然而均攤的最壞情況是對數級的——formula_1。  即使以“只讀”方式(例如通過查詢操作)訪問伸展樹,其結構也可能會發生變化。這使得伸展樹在多執行緒環境下會變得很複雜。具體而言,如果允許多個執行緒同時執行查詢操作,則需要額外的維護和操作。這也使得它們不適合在純粹的函數語言程式設計中普遍使用,儘管用於實現優先順序佇列的方式不多。

  

  當一個節點"x"被訪問過後,伸展操作會將"x"移動到根節點。為了進行伸展操作,我們會進行一系列的旋轉,每次旋轉會使"x"離根節點更近。通過每次訪問節點後的伸展操作,最近訪問的節點都會離根節點更近,且伸展樹也會大致平衡,這樣我們就可以得到期望均攤時間複雜度的下界——均攤formula_1。  每次旋轉操作由三個因素決定:  在每次旋轉操作後,設定"g"的兒子為"x"是很重要的。如果"g"為空,那麼"x"顯然就是根節點了。  共有三種旋轉操作,每種都有左旋(Zig)和右旋(Zag)兩種情況。為了簡單起見,對每種旋轉操作只展示一種情況。這些旋轉操作是:  Zig:當"p"為根節點時進行。Zig通常只在伸展操作的最後一步進行。  Zig-zig和Zag-zag:當"p"不為根節點且"x"和"p"都為左兒子或都為右兒子時進行。下圖為"x"和"p"都為左兒子時的情況(即Zig-zig),需先將"p"右旋到"g"的位置,再將"x"右旋到"p"的位置。  Zig-zag和Zag-zig:當"p"不為根節點且"x"為左兒子而"p"為右兒子時進行,反之亦然。下圖為前述情況(即Zig-zag),需先將"x"左旋到"p"到的位置,再將"x"右旋到"g"的位置。

  給出兩棵樹S和T,且S的所有元素都比T的元素要小。下面的步驟可以把它們連線成一棵樹:

  給出一棵樹和一個元素"x",返回兩棵樹:一棵中所有的元素均小於等於x,另一棵中所有的元素大於"x"。下面的步驟可以完成這個操作:

  插入操作是一個比較複雜的過程,具體步驟如下: 我們假定要插入的值為k。  如果當前樹為空,則直接插入根。  如果當前節點的權值等於k則增加當前節點的大小並更新節點和父親的資訊,將當前節點進行splay操作。  否則按照二叉查詢樹的性質向下找,找到空節點就插入即可,當然在最後還要進行一次splay操作。

  如同一般的查詢樹的查詢方式。

  以下是伸展樹的C++實現(用指標實現)

  m次伸展操作的均攤時間效率 formula_4  實際時間效率 formula_5
伸展樹(英語:Splay Tree)是一種能夠自我平衡的二叉查詢樹,它能在均攤formula_1的時間內完成基於伸展(Splay)操作的插入、查詢、修改和刪除操作。它是由丹尼爾·斯立特(英語:Daniel Sleator)和羅伯特·塔揚在1985年發明的。