fhq_treap

fhq_treap 是由范浩强大佬 orz 发明的一种 基于 split-merge 的 无旋 treap，不仅好理解，好写，不用转来转去，常数比 Splay 小不少，支持区间操作，还能 持久化（废话，人家都叫函数式 treap 了），我愿称之为最强平衡树 orz again

fhq_treap 的核心就在于 split-merge 操作，其他操作都基于 split-merge

node 定义

struct node{
    int val;
    int cnt;
    int rnd;
    int siz;
    node* lc;
    node* rc;
    node(int _val=0){
        srand((int)time(0));
        val=_val;
        cnt=siz=1;
        rnd=rand()%10000;
        lc=rc=nullptr;
    }
    node* update_siz(){
        siz=cnt;
        if(lc!=nullptr) siz+=lc->siz;
        if(rc!=nullptr) siz+=rc->siz;
        return this;
    }
};

Split

split 操作就是把一棵 treap 划分成两棵 treap，有 按点权划分，和 按子树大小划分 两种方式

按点权划分

代码如下：

void split(node* root,node*& a,node*& b,int pivot){
    if(root==nullptr){
        a=b=nullptr; // 置空多出来的部分
        return;
    }
    if(root->val<=pivot){
        a=root; // 虽然全部拷贝了，但右子树马上就要被覆盖掉，终止时也会置空
        split(root->rc,a->rc,b,pivot);
    }
    if(root->val>pivot){
        b=root;
        split(root->lc,a,b->lc,pivot);
    }
    root->update_siz(); // 递归更新 siz
}

按子树大小划分

Merge

node*& merge(node*& a,node*& b){
    // 注意合并是按 rnd 合并，维护 treap 小根性质
    if(a==nullptr) return b;
    if(b==nullptr) return a;
    // 任一 treap 为空，合并后一定是另一颗 treap
    if(a->rnd<=b->rnd){
        a->rc=merge(a->rc,b);
        // 把 merge(a->rc,b) 看成 a->rc 和 b 合并后的 treap 比较好理解
        a->update_siz();
        return a;
    }else{
        b->lc=merge(a,b->lc);
        b->update_siz();
        return b;
    }
}

找第 k 大

// kth() 是找到排名为 k 的元素
// 排名是 所有比他小的元素的个数 +1
// 不要按定义想，画个简单的树试一下就好了，这样不容易写错等于号
node* kth(node* root,int _k){
    assert(root!=nullptr); // 断言
    int lc_siz=(root->lc==nullptr ? 0 : root->lc->siz);
    // 取得左子树大小，记得要判空，空树 siz=0
    if(lc_siz>=_k) return kth(root->lc,_k);
    // 要找的在左子树里，用原排名在左子树里继续找
    if(lc_siz+root->cnt<_k) return kth(root->rc,_k-lc_siz-root->cnt);
    // 要找的在右子树里，根节点和左子树里所有结点都比要找的小，搜索右子树时排名记得减掉
    return root; // 否则要找的就是当前的根节点
}

插入

node* insert(node*& root,int _val){
    node* a=nullptr;
    node* b=nullptr;
    node* n=nullptr;
    split(root,a,b,_val);
    if(a!=nullptr && (n=kth(a,a->siz))->val==_val){
        // kth(a,a->siz) 找到 a treap 中 val 最大的结点 n
        // 如果 n->val==_val 说明已经存在值为 _val 的结点了
        n->cnt++;
        n->siz++;
        // n 就一个独立的结点，不用 update_siz()，而是直接++
        root=merge(a,b);
        return root;
    }else{
        n=new node(_val);
        root=merge(merge(a,n),b);
        return root;
    }
}

求排名

// 这里仅给出基于 split-merge 的方法，基于 siz 的方法也可用
int rnk(node* root,int _val){
    node* a=nullptr;
    node* b=nullptr;
    split(root,a,b,_val-1);
    // 注意是 val-1 才能保证得到的 a treap 都小于 _val
    int tmp=(a==nullptr ? 1 : a->siz+1);
    root=merge(a,b);
    return tmp;
}

模板类封装模板

用于八数码 A* 算法的模板

// 需要重载 ==、<、>、<=、>=
template<typename T>
struct node{
    T val;
    int rnd,siz;
    node* lc;
    node* rc;
    node(T _val=0){
        val=_val;
        rnd=rand()&32767;
        siz=1;
        lc=rc=nullptr;
    }
    void update_siz();
};

template<typename T>
class fhq_treap{
private:
    node<T>* root;
    void split(node<T>*,node<T>*&,node<T>*&,T);
    node<T>*& merge(node<T>*&,node<T>*&);
    node<T>* kth(node<T>*,int k);
public:
    fhq_treap():root(nullptr){}
    void insert(const T&);
    node<T>* get_min_and_del();
    bool exist();
};

struct state{
    int s[9];
    int f,g,h;
    void operator=(const state&);
    friend bool operator==(const state&,const state&);
    friend bool operator<(const state&,const state&);
    friend bool operator<=(const state&,const state&);
    friend bool operator>(const state&,const state&);
    friend bool operator>=(const state&,const state&);
};

template<typename T>
void node<T>::update_siz(){
    siz=1;
    if(lc!=nullptr) siz+=lc->siz;
    if(rc!=nullptr) siz+=rc->siz;
}

template<typename T>
void fhq_treap<T>::split(node<T>* root,node<T>*& a,node<T>*&b,T pivot){
    if(root==nullptr) return a=b=nullptr,void();
    if(root->val<=pivot){
        a=root;
        split(root->rc,a->rc,b,pivot);
    }else{
        b=root;
        split(root->lc,a,b->lc,pivot);
    }
    root->update_siz();
}

template<typename T>
node<T>*& fhq_treap<T>::merge(node<T>*& a,node<T>*&b){
    if(a==nullptr) return b;
    if(b==nullptr) return a;
    if(a->rnd<=b->rnd){
        a->rc=merge(a->rc,b);
        a->update_siz();
        return a;
    }else{
        b->lc=merge(a,b->lc);
        b->update_siz();
        return b;
    }
}

template<typename T>
node<T>* fhq_treap<T>::kth(node<T>* _root,int k){
    assert(_root!=nullptr); // 断言
    int lc_siz=(_root->lc==nullptr ? 0 : _root->lc->siz);
    if(lc_siz>=k) return kth(_root->lc,k);
    if(lc_siz+1<k) return kth(_root->rc,k-lc_siz-1);
    return _root;
}

template<typename T>
void fhq_treap<T>::insert(const T& _val){
    node<T>* a=nullptr;
    node<T>* b=nullptr;
    node<T>* n=nullptr;
    split(root,a,b,_val);
    if(a!=nullptr && (n=kth(a,a->siz))->val==_val){
        // exist;
        root=merge(a,b);
        return;
    }else{
        n=new node<T>(_val);
        root=merge(merge(a,n),b);
        return;
    }
}

template<typename T>
node<T>* fhq_treap<T>::get_min_and_del(){
    assert(root!=nullptr);
    if(root->lc==nullptr){
        node<T>* tmp=root;
        root=root->rc;
        return tmp;
    }
    node<T>* it;
    for(it=root;root->lc->lc!=nullptr;it=it->lc){}
    node<T>* tmp=it->lc;
    it->lc=nullptr;
    return tmp;
}

评论