posts - 12,  comments - 16,  trackbacks - 0
 

(当个日记记录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;

  }

   Treapkey值满足BST的性质:即任一个Treap的结点x,yx的左子树,y.key<=x.key,yx的右子树,y.key>=x.key.

   同时Treapfix满足Heap的性质(在这里以最大堆为例):即任一个Treap的结点x,yx的左子树或右子树,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大于xfix,则只需要左旋,若结点y的右子树的fix值大于xfix,则左旋.直至满足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 阅读(762) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(5)

随笔分类

随笔档案

文章档案

Algorithm

搜索

  •  

最新评论

阅读排行榜

评论排行榜