BST二叉搜索树

luckydrawbox · 2021-10-22 17:11:45 · 个人记录

宏定义

• #define BST_T int：以 \text{BST\_T} 为基本类型维护，可根据自己需要定义，这里实现了以 \text{int} 为基本类型的二叉搜索树。
• #define pl a[p].l：二叉搜索树中左子树的简写。
• #define pr a[p].r：二叉搜索树中右子树的简写。
• #define pv a[p].val：a[p].val 的简写。
• #define pc a[p].cnt：a[p].cnt 的简写。
• #define ps a[p].size：a[p].size 的简写。

常量与变量

• \text{int}$ ``a[i].r``：节点 $i$ 的右子节点，没有则为 $0

函数

每次操作的时间复杂度最差为 O(n)，建议用于改成平衡树板子。

#define BST_T int
#define pl a[p].l
#define pr a[p].r
#define pv a[p].val
#define pc a[p].cnt
#define ps a[p].size
struct BST{
    const BST_T MAX=0x7f7f7f7f,MIN=-0x7f7f7f7f;
    int tot,root;
    struct Tree{
        int l,r;
        BST_T val;
        int cnt,size;
    }a[N];
    int compare(BST_T x,BST_T y){
        if(x<y)
            return -1;
        if(x==y)
            return 0;
        if(x>y)
            return 1;
    }
    void update(int p){
        ps=a[pl].size+a[pr].size+pc;
    }
    int get_new(BST_T val){
        a[++tot].val=val;
        a[tot].cnt=a[tot].size=1;
        a[tot].l=a[tot].r=0;
        return tot;
    }
    void build(){
        tot=0;
        get_new(MIN);get_new(MAX);
        a[root=1].r=2;
        update(root);
    }
    int get(int p,BST_T val){
        if(!p)
            return 0;
        if(!compare(val,pv))
            return p;
        return get((compare(val,pv)<0?pl:pr),val);
    }
    void insert(int &p,BST_T val){
        if(!p){
            p=get_new(val);
            return;
        }
        if(!compare(val,pv)){
            pc++;
            update(p);
            return;
        }
        if((compare(val,pv)<0))
            insert(pl,val);
        else
            insert(pr,val);
        update(p);
    }
    void remove(int &p,BST_T val){
        if(p==0)
            return;
        if(!compare(val,pv)){
            if(pc>1){
                pc--;
                update(p);
                return;
            }
            if(!pl)
                p=pr;
            else if(!pr)
                p=pl;
            else{
                int next=pr;
                while(a[next].l)
                    next=a[next].l;
                remove(pr,a[next].val);
                a[next].l=pl;
                a[next].r=pr;
                p=next;
            }
            update(p);
            return;
        }
        if((compare(val,pv)<0)) 
            remove(pl,val);
        else
            remove(pr,val);
        update(p);
    }
    int get_pre(BST_T val){
        int ans=1,p=root;
        while(p){
            if(!compare(val,pv)){
                if(pl){
                    p=pl;
                    while(pr)
                        p=pr;
                    ans=p; 
                }
                break;
            }
            if((compare(pv,val)<0&&compare(pv,a[ans].val)>0))
                ans=p;
            p=(compare(val,pv)<0?pl:pr);
        }
        return ans;
    }
    int get_next(BST_T val){
        int ans=2,p=root;
        while(p){
            if(!compare(val,pv)){
                if(pr){
                    p=pr;
                    while(pl)
                        p=pl;
                    ans=p;
                }
                break;
            }
            if((compare(pv,val)>0&&compare(pv,a[ans].val)<0))
                ans=p;
            p=(compare(val,pv)<0?pl:pr);
        }
        return ans;
    }
    int V_to_R(int p,BST_T val){//val to rank
        if(!p)
            return 0;
        if(!compare(val,pv))
            return a[pl].size;
        if(compare(val,pv)<0)
            return V_to_R(pl,val);
        return V_to_R(pr,val)+a[pl].size+pc;
    }
    BST_T R_to_V(int p,int rank){//rank to val
        if(!p)
            return MAX;
        if(a[pl].size>=rank)
            return R_to_V(pl,rank);
        if(a[pl].size+pc>=rank)
            return pv;
        return R_to_V(pr,rank-a[pl].size-pc);
    }
    void write(int p){
        if(!p)
            return;
        printf("%d  val:%d  lson:%d %d  rson:%d %d\n",p,pv,pl,a[pl].val,pr,a[pr].val);
        write(pl);write(pr);
    }
}tree;