您的位置： 首页 / 流金岁月 / 信息学奥赛 / 学习Treap

学习Treap

2009-02-27 来自 BillWSY · 一条评论 

其实很久以前就有写这样一篇文章的想法，由于时间问题没有实现。停课集训马上就要开始，时间稍稍充裕，终于有机会写本文。本文不打算介绍Treap的各种细节，你可以在这里找到详细的教程。而本文仅仅列出一个大纲，以日记的方式简单地介绍Treap，作为自己的一个备忘，也希望能给初学者提供一个参考。

Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。

如果您是一个初学者，在读下面的文字的时候，请同时参阅NOCOW上的Treap介绍。

简单的说，Treap通过给予每个节点一个附加的随机优先级，在保证Treap数据域的排序二叉树性质的前提下，使节点的优先级同时满足堆的性质。经过种种的分析证明，在一般情况下这样做可以让Treap维持平衡。

和大多数平衡树一样，Treap的操作用到了旋转。从图（参见NOCOW上的Treap介绍）上看出，右旋即将该节点的左子节点提升到根，左旋则相反。你可以用这样的方法来记住。

插入方法：如果当前节点为空，则新建节点，加入数据，设置特征值。否则若插入数小于当前节点，插入其左子树；如果不是，就插入右子树。插入后，要根据情况旋转，来保证堆的性质。

删除方法：这是比其他平衡树树好写得多的操作。首先找到要删除的节点。如果它没有子节点，则将自己删除。若只有一个子树，那么用这个子树来代替自己。如果有两个子树，那么选择优先级比较大的，将其转到根，然后才删除要删的节点所在的子树。举例来说，如果要删除当前节点，它有两个子树，其中左子树优先级比较大，那么右旋，递归地删除其右子树。

查找：和普通的排序二叉树一样。

分离合并等，都是通过虚拟节点来实现的。由于我没有实践过，所以不敢乱讲。

NOI2004的郁闷的出纳员和2006年的生日快乐是练习平衡树的很好的题目。当然如果您才刚入门，不妨用它来写一个排序，来检验其正确性。

看到有人求代码，我来贴一个吧。很丑很长，不过还算比较好写。

?View Code CPP
 
#include <iostream>
#include <cassert>
 
using namespace std;
 
struct Treap
{
    Treap *lSon , *rSon;
    int key;
    unsigned rank;
};
 
void leftRoutate( Treap*& cur )
{
    assert( cur -> rSon );
    Treap* t = cur -> rSon;
    cur -> rSon = t -> lSon;
    t -> lSon = cur;
    cur = t;
}
 
void rightRoutate( Treap*& cur )
{
    assert( cur -> lSon );
    Treap* t = cur -> lSon;
    cur -> lSon = t -> rSon;
    t -> rSon = cur;
    cur = t;
}
 
void ins( Treap*& cur , int key )
{
    if ( cur == NULL ) {
        cur = new Treap;
        cur -> lSon = cur -> rSon = NULL;
        cur -> key = key;
        cur -> rank = rand();
    } else {
        if ( key <= cur -> key ) {
            ins( cur -> lSon , key );
            if ( cur -> lSon -> rank > cur -> rank ) {
                rightRoutate( cur );
            }
        } else {
            ins( cur -> rSon , key );
            if ( cur -> rSon -> rank > cur -> rank ) {
                leftRoutate( cur );
            }
        }
        // 维护附加域
    }
}
 
bool findKey( Treap*& cur , int key )
{
    if ( cur == NULL ) {
        return false;
    } else {
        if ( key == cur -> key ) return true;
        if ( key < cur -> key ) {
            return findKey( cur -> lSon , key );
        } else {
            return findKey( cur -> rSon , key );
        }
    }
}
 
void del( Treap*& cur , int key )
{
    if ( cur == NULL ) return;
    if ( key < cur -> key ) {
        del( cur -> lSon , key );
        return;
    }
    if ( key > cur -> key ) {
        del( cur -> rSon , key );
        return;
    }
    if ( cur -> lSon == NULL && cur -> rSon == NULL ) {
        delete cur;
        cur = NULL;
        return;
    }
    if ( cur -> lSon == NULL && cur -> rSon != NULL ) {
        Treap* t = cur;
        cur = cur -> rSon;
        delete t;
        return;
    }
    if ( cur -> lSon != NULL && cur -> rSon == NULL ) {
        Treap* t = cur;
        cur = cur -> lSon;
        delete t;
        return;
    }
    if ( cur -> lSon != NULL && cur -> rSon != NULL ) {
        if ( cur -> lSon -> rank > cur -> rSon -> rank ) {
            rightRoutate( cur );
            del( cur -> rSon , key );
        } else {
            leftRoutate( cur );
            del( cur -> lSon , key );
        }
        return;
    }
}
 
void midWalk( Treap* cur )
{
    if ( cur ) {
        midWalk( cur -> lSon );
        cout << cur -> key << " ";
        midWalk( cur -> rSon );
    }
}
 
int minimum( Treap* cur )
{
    while( cur -> lSon ) cur = cur -> lSon;
    return cur -> key;
}
 
int maximun( Treap* cur )
{
    while( cur -> rSon ) cur = cur -> rSon;
    return cur -> key;
}
 
Treap* root;
 
int main()
{
    int opt;
    cout << "1.Insert\n2.midWalk\n3.Delete\n4.Find\n5.getMin\n6.getMax\n0.Exit\n" << endl;
    cin >> opt;
    while ( opt != 0 ) {
        if ( opt == 1 ) {
            int t;
            cin >> t;
            ins( root , t );
        }
        if ( opt == 2 ) {
            midWalk( root );
            cout << endl;
        }
        if ( opt == 3 ) {
            int t;
            cin >> t;
            del( root , t );
        }
        if ( opt == 4 ) {
            int x;
            cin >> x;
            cout << ( findKey( root , x ) ? "Yes" : "No" ) << endl;
        }
        if ( opt == 5 ) {
            cout << minimum( root ) << endl;
        }
        if ( opt == 6 ) {
            cout << maximun( root ) << endl;
        }
        cin >> opt;
    }
}
日志位于 信息学奥赛 · ,

关于 BillWSY

这是一个个人的Blog。我是一名普通的高中生，平时喜欢玩玩电脑，参加信息学奥赛。生活中总有那么一点东西，希望与大家一同分享。欢迎大家来到我的Blog。

评论

一条评论 到 “学习Treap”

引用

看看别人是怎么评论这个日志的...
  1. 贴代码 : BillWSY的生活 说：
    2010年01月5日于3:01 下午

    [...] 平衡树，Treap，见这里。 [...]



说出你的看法

请告诉我们你们有什么看法...
同时如果你想在评论旁边显示一个图片，可以到gravatar申请!