一、伸展樹的數(shù)據(jù)結(jié)構(gòu)
typedef struct Node
{
int key;
struct Node *lch,*rch,*parent;
}* Node ,* Tree;
二、伸展樹的基礎(chǔ)操作
下面幾個(gè)函數(shù)中，設(shè)x 的父節(jié)點(diǎn)為 p, p的父節(jié)點(diǎn)為g 。
- zig( t , x )
右旋。當(dāng)p是根節(jié)點(diǎn)，x是p的左孩子，將x右旋。
代碼如下：
Node zig( Tree tree , Node root)
{Node lc = root->lch;Node parent = root->parent;
if( parent ){
if( root == parent->lch ){parent->lch = lc;}
else{parent->rch = lc;}lc->parent = parent;}
else{lc->parent = NULL;}
if( lc != NULL ){root->lch = lc->rch;
if( lc->rch ){lc->rch->parent = root;} lc->rch = root;root->parent = lc;
if( parent ){
return tree;}
else{
return lc; }}
return tree;
}
- zag( t , x )
左旋。當(dāng)p是根節(jié)點(diǎn)，x是p的右孩子，將x左旋
Node zag( Tree tree , Node root)
{Node rc = root->rch;Node parent = root->parent;
if( parent ){
if( root == parent->lch ){parent->lch = rc;}
else{parent->rch = rc;}rc->parent = parent;}
else{rc->parent = NULL;}
if( rc != NULL ){root->rch = rc->lch;
if( rc->lch ){rc->lch->parent = root;} rc->lch = root;root->parent = rc;
if( parent ){
return tree;}
else{
return rc; }}
return tree;
}
- zig_zig( t , x )
右雙旋。x是p的左節(jié)點(diǎn)，當(dāng)p是g的左節(jié)點(diǎn)，先將p右旋，再將x右旋
Node zig_zig( Tree tree , Node root)
{Node lc = root->lch;Node node=zig( tree , root );
return zig( node , lc );
}
- zag_zag( t , x )
左雙旋。x是p的右節(jié)點(diǎn)，當(dāng)p是g的右節(jié)點(diǎn)，先將p左旋，再將x左旋
Node zag_zag( Tree tree , Node root)
{Node rc = root->rch;Node node=zag( tree , root );
return zag( node , rc );
}
- zig_zag( t , x )
右旋再左旋。x是p的左節(jié)點(diǎn)，當(dāng)p是g的右節(jié)點(diǎn)，先將x右旋，再將x左旋
Node zig_zag( Tree tree , Node root)
{Node node=zig( tree , root->rch );
return zag( node , root );
}
- zag_zig( t , x )
左旋再右旋。x是p的右節(jié)點(diǎn)，當(dāng)p是g的左節(jié)點(diǎn)，先將x左旋，再將x右旋
Node zag_zig( Tree tree , Node root)
{Node node
=zag( tree , root
->lch );
return zig( node , root );
}
- zig_zag_manager( t , x)
旋轉(zhuǎn)管理者。 找到x，分析x與父親節(jié)點(diǎn)，父親節(jié)點(diǎn)與祖父節(jié)點(diǎn)的關(guān)系，選擇恰當(dāng)?shù)男D(zhuǎn)方式。
Node zig_zag_manager( Tree tree , Node node )
{ Node parent = node->parent;
if( parent == tree ) {
if( parent->lch == node ){
return zig( tree , parent );}
else{
return zag( tree , parent );}}
else if( parent->lch == node ){ Node grand = parent->parent;
if( grand->lch == parent ){
return zig_zig( tree , grand ); }
else{
return zig_zag( tree , grand );}}
else if( parent->rch == node ){ Node grand = parent->parent;
if( grand->lch == parent ){
return zag_zig( tree , grand ); }
else{
return zag_zag( tree , grand );}}
return tree;
}
- splay( t ,x )
將x調(diào)至根部。循環(huán)調(diào)用zig_zag_manager( t , x) 方法，直到x == t
Node splay(Tree tree , Node node)
{
while( node->parent!=NULL ){zig_zag_manager( tree , node );}
return node;
}
- find( t , x )
找到x。找到x，然后將x旋轉(zhuǎn)到樹根。
Node find( Tree tree , int key )
{Node curr
= tree;
while( curr
!= NULL ){
if( curr
->key
== key ){splay( tree , curr );
return curr; }
else if( curr
->key
> key ){curr
= curr
->lch;}
else{curr
= curr
->rch;}}
return NULL;
}
- spilt( t , x)
以x為界分離t。找到x,將x旋轉(zhuǎn)到樹根，然后將x的左子樹和剩余部分分離
Node spilt( Tree tree , Node node )
{tree
= splay( tree , node ); Node lc
= tree
->lch;tree
->lch
= NULL;
if( lc ) {lc
->parent = NULL;}
return tree;
}
注意這里，要獲得左子樹可以在分離之前獲得。
- join( t1 , t2 )
合并子樹 t1和t2，要求t1所有元素小于t2的任一元素。找到t1的最大元素，并調(diào)整到根部，將t2作為根的右子樹插入
Node
join( Tree tree1, Tree tree2)
{Node temp
= tree1;
while( temp
->rch
!= NULL ){temp
= temp
->rch;} splay( tree1 ,temp );temp
->rch
= tree2;tree2
->parent = temp;
return temp;
}
附件：
1. C-free工程，也可直接打開文件.zip
2. 廣東工業(yè)大學(xué)-計(jì)算機(jī)學(xué)院-伸展樹.pdf
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)
總結(jié)
以上是生活随笔為你收集整理的伸展树的代码实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
