BST

二叉搜索树(BST)，也可以叫做二叉排序树

BST树始终满足四个要求

1. 左结点的值小于父结点
2. 右结点的值大于右结点
3. 没有权值相同的结点
4. 每一个结点的左右子树也满足二叉排序树

BST暴力搜索最坏的情况时间复杂度是O(n ^ 2)

接下来讲的主要是最普遍的二叉搜索树

初始化

先定义一个全局遍历nnum代表每一个结点的下标

在开始之前我们需要为每一个结点定义属性

每一个结点需要值(val)

左孩子(ls)

右孩子(rs)

重复情况使用记录出现次数(cnt)

用来记录排名(siz)

struct node{
	int ls;int rs;int val;int cnt;int siz;
};

插入结点

参数部分

我们既然想要插入一定需要将跟结点传入

从根结点出发去查找合适的位置

接着传入插入的值

判断

三种情况

插入的结点等于当前结点

插入结点大于当前结点

插入结点小于当前结点

完整代码

void add(int now,int v) {
    t[now].siz++;
    if(t[now].val == v) {
        t[now].cnt++;
        return;
    }
    if(t[now].val < v) {
        if(t[now].rs == 0) {
            nnum++;
            t[nnum].cnt = 1;t[nnum].siz = 1;
            t[nnum].val = v;
            t[now].rs = nnum;
        }else {
            add(t[now].rs,v);
        }

        
    }else {
        if(t[now].ls == 0) {
            nnum++;
            t[nnum].val = v;
            t[nnum].cnt = 1;t[nnum].siz = 1;
            t[now].ls = nnum;
            
        }else {
            add(t[now].ls,v);
        }
    }
}

查找元素的前驱结点的值

int findPre(int now,int val,int ans) {
    if(t[now].val >= val) {
        if(t[now].ls == 0) return ans;
        else return findPre(t[now].ls,val,ans);
    }else {
        
        if(t[now].rs == 0) {
            if(ans == -INF) return t[now].val;
            else return ans;
        }

        return findPre(t[now].rs,val,t[now].val);
    }

}

查找元素的后继结点的值

int findLast(int now,int val,int ans) {
    if(t[now].val <= val) {
        if(t[now].rs == 0) return ans;
        else return findLast(t[now].rs,val,ans);
    }else {
        if(t[now].ls == 0) {
            if(ans == INF) return t[now].val;
            else return ans;
        }

        return findLast(t[now].ls,val,t[now].val);
    }
}

按值查排名

int frank(int now,int x) {
    if(x == 0) return 0;
    if(t[now].val == x) return t[t[now].ls].siz;

    if(x < t[now].val) return frank(t[now].ls,x);
    
    return frank(t[now].rs,x) + t[t[now].ls].val + t[now].cnt;
}

按排名查值

int fval(int now,int rank) {
    if(now == 0) return INF;
    if(t[t[now].ls].siz >= rank) {
        return fval(t[now].ls,rank);
    }

    if(t[t[now].ls].siz + t[now].cnt >= rank) {
        return t[now].val;
    }

    return fval(t[now].rs,rank - t[t[now].ls].siz - t[now].cnt);
}