(當個日記記錄Treap這一結構,詳細參見http://www.nocow.cn/index.php/Treap, 在這里我著重講一下旋轉)
Treap,它其它就是一個二叉查找樹(BST)+堆(HEAP). 它的數據有兩個:關鍵值(key),優先級(fix).
用struct表示Treap的結點的結構如下:
struct node
{
datatype key;
int fix;
node * left;
node * right;
}
Treap的key值滿足BST的性質:即任一個Treap的結點x,若y是x的左子樹,則y.key<=x.key,若y為x的右子樹,則y.key>=x.key.
同時Treap的fix滿足Heap的性質(在這里以最大堆為例):即任一個Treap的結點x,若y為x的左子樹或右子樹,則x.fix>=y.fix.
如下圖所示則為Treap
Treap的作用:它的作用同BST一樣,引入優先級這一概念是為了防止BST退化成一鏈表(BST的建立依籟于結點的插入順序,當有序的插入時,則BST為一鏈表,其它查找插入的復雜度o(n)),當然我們完全可以隨機的插入結點,但是有時候我們事先并不知道所有結點,在這種情況下我們可以采用Treap,即當需要插入的一個新的key值,我們可以隨機的生成一個優先級(fix),然后通過fix約束Treap,從而達到隨機生成BST的目的.
為了插入和刪除之后仍然保持Treap的兩個性質,在這里Treap提供了兩種旋轉的操作,右旋和左旋
(1)結點右旋:node x,令y=x->left; 先將y的右子樹作為x的左子樹,然后將x作為y的右子樹, 最后將y作為x原父結點的子樹(原x為左子樹,此時y仍然為左子樹,x為右子樹,y也為右子樹)如下圖所示.
(2)結點左旋:同右旋剛好相反.node x,令y=x->right; 先將y的左子樹作為x的右子樹,然后將x作為y的左子樹, 最后將y作為x原父結點的子樹(原x為左子樹,此時y仍然為左子樹,x為右子樹,y也為右子樹)如下圖所示.
由上可見,旋轉操作之后仍然滿足BST的特性,但是改變Heap的性質.
插入操作:有了旋轉操作后,插入變得十分簡單.它只需要將結點(key,fix)按BST插入到Treap,此時若不滿足Heap的性質,若結點x的左子樹的fix大于x的fix,則只需要左旋,若結點y的右子樹的fix值大于x的fix,則左旋.直至滿足Heap的性質.
刪除操作:只需要將刪除的結點旋轉至葉結點,直接插除即可.
對于其它的查找,后繼,最小值等操作均同BST一樣,在這里便不再詳述.附有C++ Treap實現.
using std::ostream;
using std::endl;
using std::cout;
class Treap
{
private:
struct node
{
int key;
int fix;//priority,for heap
node * left,*right;//left child and right child
node(const int &_k):key(_k),left(NULL),right(NULL),fix(rand())
{
}
};
friend std::ostream & operator <<(std::ostream &os,node * const &r)
{
if(r==NULL)
return os;
os<<r->left;
os<<r->key<<std::endl;
os<<r->right;
return os;
}
inline void rol_l(node * &x)//rotate to left on node x
{
node * y=x->right;
x->right=y->left;
y->left=x;
x=y;
}
inline void rol_r(node * &x)//rotate to right on node x
{
node * y=x->left;
x->left=y->right;
y->right=x;
x=y;
}
void insert(node * & r,const int &key)
{
if(r==NULL)
{
r=new node(key);
}else
{
if(key<r->key)
{
insert(r->left,key);
if(r->left->fix>r->fix)
rol_r(r);
}else
{
insert(r->right,key);
if(r->right->fix>r->fix)
rol_l(r);
}
}
}
void remove(node * &r,const int &key)
{
if(r==NULL)
return;
if(key<r->key)
remove(r->left,key);
else if(key>r->key)
remove(r->right,key);
else
{
//remove node r
if(r->left==NULL && r->right==NULL)
{
delete r;
r=NULL;
}else if(r->left==NULL)
{
node * t=r;
r=r->right;
delete r;
}else if(r->right==NULL)
{
node * t=r;
r=r->left;
delete t;
}else
{
if(r->left->fix<r->right->fix)
{
rol_l(r);
remove(r->left,key);
}else
{
rol_r(r);
remove(r->right,key);
}
}
}
}
bool find(node * const & r,const int &key)
{
if(r==NULL)
return false;
if(r->key==key)
return true;
else
if(key<r->key)
return find(r->left,key);
else
return find(r->right,key);
}
void free(node * &r)
{
if(r==NULL)
return;
free(r->left);
free(r->right);
delete r;
r=NULL;
}
node * root;
public:
Treap():root(NULL)
{
}
~Treap()
{
free(root);
}
void insert(const int &key)
{
insert(root,key);
}
void remove(const int &key)
{
remove(root,key);
}
bool find(const int &key)
{
find(root,key);
}
friend std::ostream & operator <<(ostream & os,const Treap &t)
{
os<<t.root;
return os;
}
};
int main()
{
Treap t;
for(int i=0;i<10;i++)
t.insert(i);
std::cout<<t;
t.remove(3);
cout<<"after remove 3"<<endl;
std::cout<<t;
t.remove(5);
cout<<"after remove 5"<<endl;
std::cout<<t;
system("pause");
}
posted on 2009-08-12 21:57
kuramawzw 閱讀(964)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構