伸展樹
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目需要補充更多來源。 (2022年9月18日) |
![]() | 此條目可參照英語維基百科相應條目來擴充。 |
伸展樹 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 樹 | ||||||||||||||||||||
發明時間 | 1985年 | ||||||||||||||||||||
發明者 | 丹尼爾·斯萊托和羅伯特·塔揚 | ||||||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||||||
|
伸展樹(英語:Splay Tree)是一種能夠自我平衡的二叉搜尋樹,它能在均攤的時間內完成基於伸展(Splay)操作的插入、尋找、修改和刪除操作。它是由丹尼爾·斯萊托和羅伯特·塔揚在1985年發明的[1]。
在伸展樹上的一般操作都基於伸展操作:假設想要對一個二叉搜尋樹執行一系列的尋找操作,為了使整個尋找時間更小,被查頻率高的那些條目就應當經常處於靠近樹根的位置。於是想到設計一個簡單方法,在每次尋找之後對樹進行調整,把被尋找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉搜尋樹,它會沿着從某個節點到樹根之間的路徑,通過一系列的旋轉把這個節點搬移到樹根去。
它的優勢在於不需要記錄用於平衡樹的冗餘資訊。
優點
伸展樹的自我平衡使其擁有良好的效能,因為頻繁訪問的節點會被移動到更靠近根節點,進而獲得更快的訪問速度。
缺點
伸展樹最顯著的缺點是它有可能會變成一條鏈。例如,在以非遞減順序訪問全部n個之後就會出現這種情況。此時樹的高度對應於最壞情況的時間效率,操作的實際時間效率可能很低。然而均攤的最壞情況是對數級的——。
即使以「唯讀」方式(例如通過尋找操作)訪問伸展樹,其結構也可能會發生變化。這使得伸展樹在多線程環境下會變得很複雜。具體而言,如果允許多個線程同時執行尋找操作,則需要額外的維護和操作。這也使得它們不適合在純粹的函數式程式設計中普遍使用,儘管用於實現優先級佇列的方式不多。
操作
伸展(splay)
當一個節點x被訪問過後,伸展操作會將x移動到根節點。為了進行伸展操作,我們會進行一系列的旋轉,每次旋轉會使x離根節點更近。通過每次訪問節點後的伸展操作,最近訪問的節點都會離根節點更近,且伸展樹也會大致平衡,這樣我們就可以得到期望均攤時間複雜度的下界——均攤。
每次旋轉操作由三個因素決定:
- x是其父節點p的左兒子還是右兒子;
- p是否為根;
- p是其父節點g(x的祖父節點)的左兒子還是右兒子。
在每次旋轉操作後,設置p的兒子為x是很重要的。如果p為空,那麼x顯然就是根節點了。
共有三種旋轉操作,每種都有右旋(Zig)和左旋(Zag)兩種情況。為了簡單起見,對每種旋轉操作只展示一種情況。這些旋轉操作是:
Zig:當p為根節點時進行。Zig通常只在伸展操作的最後一步進行。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Splay_tree_zig.svg/709px-Splay_tree_zig.svg.png)
Zig-zig和Zag-zag:當p不為根節點且x和p都為左兒子或都為右兒子時進行。下圖為x和p都為左兒子時的情況(即Zig-zig),需先將p右旋到g的位置,再將x右旋到p的位置。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/f/fd/Zigzig.gif)
Zig-zag和Zag-zig:當p不為根節點且x為左兒子而p為右兒子時進行,反之亦然。下圖為前述情況(即Zig-zag),需先將x左旋到p到的位置,再將x右旋到g的位置。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/6/6f/Zigzag.gif)
連接(join)
給出兩棵樹S和T,且S的所有元素都比T的元素要小。下面的步驟可以把它們連接成一棵樹:
- 伸展S中最大的節點。現在這個節點變為S的根節點,且沒有右兒子。
- 令T的根節點變為其右兒子。
分割(split)
給出一棵樹和一個元素x,返回兩棵樹:一棵中所有的元素均小於等於x,另一棵中所有的元素大於x。下面的步驟可以完成這個操作:
- 伸展x。這樣的話x成為了這棵樹的根所以它的左子樹包含了所有比x小的元素,右子樹包含了所有比x大的元素。
- 把x的右子樹從樹中分割出來。
插入(insert)
插入操作是一個比較複雜的過程,具體步驟如下: 我們假定要插入的值為k。
如果當前樹為空,則直接插入根。
如果當前節點的權值等於k則增加當前節點的大小並更新節點和父親的資訊,將當前節點進行splay操作。
否則按照二叉搜尋樹的性質向下找,找到空節點就插入即可,當然在最後還要進行一次splay操作。 [3]
刪除(delete)
令要刪除的節點為x,對x進行一次splay操作將其移動到根節點的位置。
若x的大小大於1,則將x的大小減一然後結束刪除操作。
否則將x刪除然後執行join操作合併x的左右子樹並重新指定根。
尋找(find)
如同一般的尋找樹的尋找方式。
實現
以下是伸展樹的C++實現(用指標實現)
#include <functional>
#ifndef SPLAY_TREE
#define SPLAY_TREE
template< typename T, typename Comp = std::less< T > >
class splay_tree {
private:
Comp comp;
unsigned long p_size;
struct node {
node *left, *right;
node *parent;
T key;
node( const T& init = T( ) ) : left( 0 ), right( 0 ), parent( 0 ), key( init ) { }
} *root;
void left_rotate( node *x ) {
node *y = x->right;
x->right = y->left;
if( y->left ) y->left->parent = x;
y->parent = x->parent;
if( x->parent ) {
if( x == x->parent->left ) x->parent->left = y;
else x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void right_rotate( node *x ) {
node *y = x->left;
x->left = y->right;
if( y->right ) y->right->parent = x;
y->parent = x->parent;
if( x->parent ) {
if( x == x->parent->left ) x->parent->left = y;
else x->parent->right = y;
}
y->right = x;
x->parent = y;
}
void splay( node *x ) {
while( x->parent ) {
if( !x->parent->parent ) {
if( x->parent->left == x ) right_rotate( x->parent );
else left_rotate( x->parent );
} else if( x->parent->left == x && x->parent->parent->left == x->parent ) {
right_rotate( x->parent->parent );
right_rotate( x->parent );
} else if( x->parent->right == x && x->parent->parent->right == x->parent ) {
left_rotate( x->parent->parent );
left_rotate( x->parent );
} else if( x->parent->left == x && x->parent->parent->right == x->parent ) {
right_rotate( x->parent );
left_rotate( x->parent );
} else {
left_rotate( x->parent );
right_rotate( x->parent );
}
}
}
void replace( node *u, node *v ) {
if( !u->parent ) root = v;
else if( u == u->parent->left ) u->parent->left = v;
else u->parent->right = v;
if( v ) v->parent = u->parent;
}
node* subtree_minimum( node *u ) {
while( u->left ) u = u->left;
return u;
}
node* subtree_maximum( node *u ) {
while( u->right ) u = u->right;
return u;
}
public:
splay_tree( ) : root( 0 ), p_size( 0 ) { }
void insert( const T &key ) {
node *z = root;
node *p = 0;
while( z ) {
p = z;
if( comp( z->key, key ) ) z = z->right;
else z = z->left;
}
z = new node( key );
z->parent = p;
if( !p ) root = z;
else if( comp( p->key, z->key ) ) p->right = z;
else p->left = z;
splay( z );
p_size++;
}
node* find( const T &key ) {
node *z = root;
while( z ) {
if( comp( z->key, key ) ) z = z->right;
else if( comp( key, z->key ) ) z = z->left;
else return z;
}
return 0;
}
void erase( const T &key ) {
node *z = find( key );
if( !z ) return;
splay( z );
if( !z->left ) replace( z, z->right );
else if( !z->right ) replace( z, z->left );
else {
node *y = subtree_minimum( z->right );
if( y->parent != z ) {
replace( y, y->right );
y->right = z->right;
y->right->parent = y;
}
replace( z, y );
y->left = z->left;
y->left->parent = y;
}
p_size--;
}
const T& minimum( ) { return subtree_minimum( root )->key; }
const T& maximum( ) { return subtree_maximum( root )->key; }
bool empty( ) const { return root == 0; }
unsigned long size( ) const { return p_size; }
};
#endif // SPLAY_TREE
時間效率分析
m次伸展操作的均攤時間效率
實際時間效率 [4]
參考來源
- ^ Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees (PDF), Journal of the ACM, 1985, 32 (3): 652–686 [2015-03-05], doi:10.1145/3828.3835, (原始內容存檔 (PDF)於2015-03-05) (英語)
- ^ Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael. Data Structures and Algorithms in Java 6. John Wiley & Sons, Inc. 2014: 506. ISBN 978-1-118-77133-4 (英語).
The surprising thing about splaying is that it allows us to guarantee a logarithmic amortized running time, for insertions, deletions, and searches.
- ^ Splay tree - OIwiki. [2019-07-14]. (原始內容存檔於2019-07-14).
- ^ Splay tree - Wikipedia. [2018-06-23]. (原始內容存檔於2018-05-05).
|