忽闻寒梅香销晚,一任庭轩,燕子穿云间!~~~
 
俄!!思路断了,还是继续研究算法和windows编程吧!
hehe,左手的程序,右手的诗歌!
 
写点东西吧!
发现多简单的,写红黑树花了一个上午,AVL整整一天!
Treap呵呵!2个小时不到,就打完收工,其实应该15分钟就完了![其中主要去查windows console里面的绘图API了,呵呵]
真的很简单!
维基的这个有点问题,root的调整没有做!应该加上的,也不复杂!
只是要注意k是引用的话,要在向下调用的时候,预先存下先前的父亲节点!
贴下代码:[早晓得就用Treap来做字典了,上次Trie慢了整整100MS]
#ifndef TREAP_H_INCLUDED
#define TREAP_H_INCLUDED
#include <iostream>
//#define verify 1
#ifdef verify
#include <vector>
#endif
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MaxSize=1000;
//refer to wiki’s implementation
//typedef for Treap node
typedef struct{
    int l,r,key,fix;
}node;
class Treap{
public:
    Treap(){
        srand((unsigned)time(NULL));
        root=size=-1;
    }
    int insert(int key);
    int dele(int key);
    int search(const int key);
    #ifdef verify
    void print();
    #endif
private:
    int insert(int &k, int key);
    int dele(int &k, int key);
    void rot_l(int &x);//rotate left
    void rot_r(int &x);//rotate right
    #ifdef verify
    void level();
    #endif
    node t[MaxSize];
    int root,size;//size is the current node number
};
//implementation
//for private rotate logic
void Treap::rot_l(int &x){
    int y=t[x].r;
    t[x].r=t[y].l;
    t[y].l=x;
    x=y;//here modify parent!
}
void Treap::rot_r(int &x){
    int y=t[x].l;
    t[x].l=t[y].r;
    t[y].r=x;
    x=y;//here modify parent!
}
int Treap::insert(int key){
    return insert(root, key);
}
int Treap::insert(int &k, int key){
    int p,r;
    if(k==-1){//not exist for key
        assert(size<MaxSize);
        k=++size;
        t[k].key=key;
        t[k].l=t[k].r=-1;
        t[k].fix=rand();
        if(root==-1) root=k;
        return 0;
    }
    else if(t[k].key>key){
        r=insert(t[k].l, key);
        //k, vs t[k].l
        if(t[ t[k].l ].fix < t[k].fix){
            p=k;
            rot_r(k);
            //root change?
            if(p==root) root=k;
        }
        return r;
    }
    else if(t[k].key<key){
        r=insert(t[k].r, key);
        //k, vs t[k].r
        if(t[ t[k].r ].fix < t[k].fix){
            p=k;
            rot_l(k);
            //root change?
            if(p==root) root=k;
        }
        return r;
    }
    return -1;
}
int Treap::dele(int key){
    return dele(root, key);
}
int Treap::dele(int &k, int key){
    int p;
    if(k==-1) return -1;
    else if(t[k].key>key)
        return dele(t[k].l, key);
    else if(t[k].key<key)
        return dele(t[k].r, key);
    else{//t[k].key==key
        if(t[k].l==-1&&t[k].r==-1){
            k=-1; size–;
            return 0;
        }
        else if(t[k].l==-1){//t[k].r!=-1
            k=t[k].r,size–;//the leaf has no child already
            return 0;
        }
        else if(t[k].r==-1){//t[k].l!=-1
            k=t[k].l,size–;//the leaf has no child already
            return 0;
        }
        else{//t[k].r!=-1&&t[k].l!=-1
            //select fix min part
            p=k;
            if(t[ t[k].l ].fix < t[ t[k].r ].fix){//t[k].l escalate to root
                rot_r(k);
                if(p==root) root=k;//modified number
                return dele(t[k].r, key);
            }
            else{//t[k].r is better
                rot_l(k);
                if(p==root) root=k;
                return dele(t[k].l, key);
            }
        }
    }
}
int Treap::search(const int key){
    if(root==-1) return -1;
    int k=root;
    while(k!=-1&&t[k].key!=key){
        if(t[k].key<key) k=t[k].r;
        else k=t[k].l;
    }
    return k;
}
#ifdef verify
void Treap::print(){
    level();
}
struct no{
    int c,p;
};
void Treap::level(){
    if(root==-1) return;
    vector<no> queue;
    int s=0,e;
    no tn, t1, t2;
    tn.c=root,tn.p=-1;
    queue.push_back(tn);
    while(s<queue.size()){
        e=queue.size();
        while(s<e){
            tn=queue[s];
            cout<<"|k:"<<t[tn.c].key<<" p:"<<tn.p<<" ";
            if(t[tn.c].l!=-1){
                t1.c=t[tn.c].l, t1.p=t[tn.c].key;
                assert(t[tn.c].fix<=t[t1.c].fix);
                queue.push_back(t1);
            }
            if(t[tn.c].r!=-1){
                t2.c=t[tn.c].r, t2.p=t[tn.c].key;
                assert(t[tn.c].fix<=t[t2.c].fix);
                queue.push_back(t2);
            }
            s++;
        }
        cout<<endl;
    }
    cout<<"total size:"<<e<<endl;
}
#endif
#endif // TREAP_H_INCLUDED
Advertisements