伸展樹

伸展樹操作的插入、查詢、修改和刪除操作。它是由丹尼爾·斯立特和羅伯特·塔揚在1985年發明的。在伸展樹上的一般操作都基於伸展操作：假設想要對一個二叉查詢樹執行一系列的查詢操作，為了使整個查詢時間更小，被查頻率高的那些條目就應當經常處於靠近樹根的位置。於是想到設計一個簡單方法，在每次查詢之後對樹進行調整，把被查詢的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉查詢樹，它會沿著從某個節點到樹根之間的路徑，透過一系列的旋轉把這個節點搬移到樹根去。它的優勢在於不需要記錄用於平衡樹的冗餘資訊。優點.伸展樹的自我平衡使其擁有良好的效能，因為頻繁訪問的節點會被移動到更靠近根節點，進而獲得更快的訪問速度。缺點.伸展樹最顯著的缺點是它有可能會變成一條鏈。例如，在以非遞減順序訪問全部n個之後就會出現這種情況。此時樹的高度對應於最壞情況的時間效率，操作的實際時間效率可能很低。然而均攤的最壞情況是對數級的——formula_1。即使以“只讀”方式訪問伸展樹，其結構也可能會發生變化。這使得伸展樹在多執行緒環境下會變得很複雜。具體而言，如果允許多個執行緒同時執行查詢操作，則需要額外的維護和操作。這也使得它們不適合在純粹的函數語言程式設計中普遍使用，儘管用於實現優先順序佇列的方式不多。操作.伸展(splay).當一個節點"x"被訪問過後，伸展操作會將"x"移動到根節點。為了進行伸展操作，我們會進行一系列的旋轉，每次旋轉會使"x"離根節點更近。透過每次訪問節點後的伸展操作，最近訪問的節點都會離根節點更近，且伸展樹也會大致平衡，這樣我們就可以得到期望均攤時間複雜度的下界——均攤formula_1。每次旋轉操作由三個因素決定：在每次旋轉操作後，設定"p"的兒子為"x"是很重要的。如果"p"為空，那麼"x"顯然就是根節點了。共有三種旋轉操作，每種都有右旋兩種情況。為了簡單起見，對每種旋轉操作只展示一種情況。這些旋轉操作是：Zig：當"p"為根節點時進行。Zig通常只在伸展操作的最後一步進行。Zig-zig和Zag-zag：當"p"不為根節點且"x"和"p"都為左兒子或都為右兒子時進行。下圖為"x"和"p"都為左兒子時的情況，需先將"p"右旋到"g"的位置，再將"x"右旋到"p"的位置。Zig-zag和Zag-zig：當"p"不為根節點且"x"為左兒子而"p"為右兒子時進行，反之亦然。下圖為前述情況，需先將"x"左旋到"p"到的位置，再將"x"右旋到"g"的位置。連線(join).給出兩棵樹S和T，且S的所有元素都比T的元素要小。下面的步驟可以把它們連線成一棵樹：分割(split).給出一棵樹和一個元素"x"，返回兩棵樹：一棵中所有的元素均小於等於x，另一棵中所有的元素大於"x"。下面的步驟可以完成這個操作：插入(insert).插入操作是一個比較複雜的過程，具體步驟如下:我們假定要插入的值為k。如果當前樹為空，則直接插入根。如果當前節點的權值等於k則增加當前節點的大小並更新節點和父親的資訊，將當前節點進行splay操作。否則按照二叉查詢樹的性質向下找，找到空節點就插入即可，當然在最後還要進行一次splay操作。刪除(delete).令要刪除的節點為x，對x進行一次splay操作將其移動到根節點的位置。若x的大小大於1，則將x的大小減一然後結束刪除操作。否則將x刪除然後執行join操作合併x的左右子樹並重新指定根。查詢(find).如同一般的查詢樹的查詢方式。實現.以下是伸展樹的C++實現templateclass splay_tree {private:Comp comp;unsigned long p_size;struct node {node *left, *right;node *parent;T key;} *root;void left_rotate( node *x ) {node *y = x-&gt;right;x-&gt;right = y-&gt;left;if( y-&gt;left ) y-&gt;left-&gt;parent = x;y-&gt;parent = x-&gt;parent;if( x-&gt;parent ) {if( x == x-&gt;parent-&gt;left ) x-&gt;parent-&gt;left = y;else x-&gt;parent-&gt;right = y;y-&gt;left = x;x-&gt;parent = y;void right_rotate( node *x ) {node *y = x-&gt;left;x-&gt;left = y-&gt;right;if( y-&gt;right ) y-&gt;right-&gt;parent = x;y-&gt;parent = x-&gt;parent;if( x-&gt;parent ) {if( x == x-&gt;parent-&gt;left ) x-&gt;parent-&gt;left = y;else x-&gt;parent-&gt;right = y;y-&gt;right = x;x-&gt;parent = y;void splay( node *x ) {while( x-&gt;parent ) {if( !x-&gt;parent-&gt;parent ) {if( x-&gt;parent-&gt;left == x ) right_rotate( x-&gt;parent );else left_rotate( x-&gt;parent );} else if( x-&gt;parent-&gt;left == x &amp;&amp; x-&gt;parent-&gt;parent-&gt;left == x-&gt;parent ) {right_rotate( x-&gt;parent-&gt;parent );right_rotate( x-&gt;parent );} else if( x-&gt;parent-&gt;right == x &amp;&amp; x-&gt;parent-&gt;parent-&gt;right == x-&gt;parent ) {left_rotate( x-&gt;parent-&gt;parent );left_rotate( x-&gt;parent );} else if( x-&gt;parent-&gt;left == x &amp;&amp; x-&gt;parent-&gt;parent-&gt;right == x-&gt;parent ) {right_rotate( x-&gt;parent );left_rotate( x-&gt;parent );} else {left_rotate( x-&gt;parent );right_rotate( x-&gt;parent );void replace( node *u, node *v ) {if( !u-&gt;parent ) root = v;else if( u == u-&gt;parent-&gt;left ) u-&gt;parent-&gt;left = v;else u-&gt;parent-&gt;right = v;if( v ) v-&gt;parent = u-&gt;parent;node* subtree_minimum( node *u ) {while( u-&gt;left ) u = u-&gt;left;return u;node* subtree_maximum( node *u ) {while( u-&gt;right ) u = u-&gt;right;return u;public:void insert( const T &amp;key ) {node *z = root;node *p = 0;while( z ) {p = z;if( comp( z-&gt;key, key ) ) z = z-&gt;right;else z = z-&gt;left;z = new node( key );z-&gt;parent = p;if( !p ) root = z;else if( comp( p-&gt;key, z-&gt;key ) ) p-&gt;right = z;else p-&gt;left = z;splay( z );p_size++;node* find( const T &amp;key ) {node *z = root;while( z ) {if( comp( z-&gt;key, key ) ) z = z-&gt;right;else if( comp( key, z-&gt;key ) ) z = z-&gt;left;else return z;return 0;void erase( const T &amp;key ) {node *z = find( key );if( !z ) return;splay( z );if( !z-&gt;left ) replace( z, z-&gt;right );else if( !z-&gt;right ) replace( z, z-&gt;left );else {node *y = subtree_minimum( z-&gt;right );if( y-&gt;parent != z ) {replace( y, y-&gt;right );y-&gt;right = z-&gt;right;y-&gt;right-&gt;parent = y;replace( z, y );y-&gt;left = z-&gt;left;y-&gt;left-&gt;parent = y;p_size--;時間效率分析.m次伸展操作的均攤時間效率 formula_4實際時間效率 formula_5